⚛️ quantum physics

A Quantum Search Approach to Magic Square Constraint Problems with Classical Benchmarking

This paper proposes and validates a hybrid quantum-classical framework for generating magic squares that utilizes classical pre-processing for structured initialization and Grover's algorithm for amplitude amplification, demonstrating a theoretical quadratic speedup over classical search methods on small-scale instances.

Original authors: Rituparna R, Harsha Varthini, Aswani Kumar Cherukuri

Published 2026-04-07

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Rituparna R, Harsha Varthini, Aswani Kumar Cherukuri

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to find a specific, perfect arrangement of numbers in a grid, known as a Magic Square. In this grid, every row, column, and diagonal must add up to the exact same number. It's like a Sudoku puzzle, but with a much stricter rule: every single line must sum to the same total.

For a small 3x3 grid, there are hundreds of thousands of ways to arrange the numbers, but only a handful are "magic." Finding the right one by guessing and checking is like looking for a needle in a haystack.

This paper is about using a Quantum Computer to find that needle much faster than a regular computer can. Here is the breakdown of how they did it, using simple analogies.

1. The Problem: The "Haystack"

Imagine you have a giant library containing every possible way to arrange numbers in a 3x3 grid.

Classical Computers (The Old Way): A regular computer is like a very fast librarian who checks one book at a time. It opens a book, checks if it's a magic square, puts it back, and moves to the next. If there are 362,880 books, it might have to check thousands of them before finding the right one.
The Challenge: As the grid gets bigger (like 4x4 or 5x5), the number of books explodes into the trillions. A classical librarian would take years or even centuries to find the answer.

2. The Solution: The "Quantum Super-Scanner"

The authors used Grover's Algorithm, which is like a magical search tool. Instead of checking books one by one, a quantum computer can look at all the books in the library at the same time.

Think of it like this:

The Superposition: Imagine you have a magical flashlight that shines on every single book in the library simultaneously.
The Oracle (The Magic Filter): This is the most important part. The authors built a special "filter" (called an Oracle). When the flashlight shines on a book, the filter instantly knows if it's a "Magic Square." If it is, the filter gives that book a special "glow" (a phase flip). If it's not, the book stays dark.
Amplitude Amplification: Now, the quantum computer does a special dance (the Diffusion Operator). It takes all the "dark" books and makes them slightly dimmer, while taking the "glowing" book and making it shine brighter.
The Result: If you repeat this dance a specific number of times, the correct book becomes so bright that when you look at the library, you are almost guaranteed to see only the right answer.

3. The "Smart Assistant" (Classical Pre-processing)

Before the quantum computer starts its magic, the authors used a classical computer to do some "homework."

The Analogy: Imagine you are looking for a specific key in a messy room. Instead of searching the entire house, a smart assistant first locks the doors to the rooms you know are empty.
What they did: They used a classic math trick (the Siamese method) to lock down certain numbers that must be in specific spots. This shrinks the "haystack" before the quantum computer even touches it, making the search more efficient.

4. The Experiments: What Did They Find?

The team tested this on a small 3x3 grid using a simulator (a program that acts like a quantum computer on a regular laptop).

The Race: They pitted the Quantum Search against a "Brute-Force" search (checking every single option) and a "Backtracking" search (a smarter way of checking options one by one).
The Catch: Because they were running this on a simulator (a regular computer pretending to be a quantum one), the quantum computer didn't actually win on speed yet. In fact, the simulation was slightly slower because "pretending" to be quantum is very hard work for a regular computer.
The Real Win: The paper proves that the logic works. The quantum computer successfully found the magic square. Theoretically, if they had a real, powerful quantum computer, the speedup would be massive. Instead of checking 362,880 options, the quantum computer would only need to check about 600 options. That is a huge difference!

5. Why Isn't Everyone Using This Yet?

The paper admits there are hurdles, like trying to fly a rocket ship with a toy engine:

Too Many Qubits: To solve bigger puzzles (like 4x4 or 5x5), you need more "quantum bits" (qubits). Current quantum computers are still too small and noisy for these big jobs.
The Noise: Real quantum computers are fragile. The "dance" the computer has to do is very delicate; if the room shakes (noise), the magic spell breaks, and the answer is wrong.
Simulation Limits: You can't simulate a huge quantum computer on a normal laptop because it requires too much memory (like trying to simulate a whole ocean in a bathtub).

The Bottom Line

This paper is a blueprint. It shows that we can translate a difficult math puzzle (Magic Squares) into a language a quantum computer understands.

Classical computers are like a person walking through a maze, hitting walls and turning back.
This Quantum approach is like having a map that highlights the correct path instantly, provided you have a map-maker (the Oracle) and a vehicle (the Quantum Computer) powerful enough to use it.

While we aren't there yet with the hardware to solve massive puzzles instantly, this work proves the path is clear. Once quantum computers get bigger and less noisy, this method could solve complex scheduling, encryption, and logistics problems that are currently impossible for us to crack.

1. Problem Definition

The paper addresses the Magic Square Constraint Satisfaction Problem (CSP). A magic square is an $n \times n$ grid filled with distinct integers from $1$ to $n^2$ such that the sum of every row, every column, and both main diagonals equals a specific "magic constant" ( $M = n(n^2+1)/2$ ).

Challenge: The solution space grows factorially with grid size ( $n^2!$ ). For a $3 \times 3$ grid, there are $9! = 362,880$ permutations, but only 8 valid solutions (up to rotation/reflection). For $n=4$ , the space exceeds $2 \times 10^{13}$ , making exhaustive classical enumeration infeasible.
Goal: To formulate magic square generation as a quantum search problem using Grover's algorithm to achieve a quadratic speedup in query complexity compared to classical unstructured search.

2. Methodology

The authors propose a hybrid pipeline where classical preprocessing reduces the search space, and a quantum engine performs the search. The process involves five sequential stages:

A. Classical Pre-processing

Before quantum encoding, the search space is pruned using:

Siamese Construction: A deterministic rule (De la Loubère method) fixes the center cell for odd-order squares.
Partial Constraint Checks: Early elimination of assignments that violate row/column sums.

Purpose: To create a compact candidate domain, improving the signal-to-noise ratio for the quantum amplitude amplification.

B. Quantum Encoding

State Representation: Each integer $1$ to $n^2$ is encoded in binary. An $n \times n$ grid requires a primary register of $n^2 \times \lceil \log_2(n^2) \rceil$ qubits.
Initialization: Hadamard gates are applied to create a uniform superposition of all candidate permutations.

C. Oracle Construction (The Core Innovation)

A reversible quantum oracle marks valid magic square configurations by applying a phase flip ($-1$) to states satisfying all constraints. The construction involves:

Modular Arithmetic: Quantum adders compute row, column, and diagonal sums stored in ancilla registers.
Comparison: Quantum comparators check if sums equal $M$ and verify element uniqueness.
Multi-Controlled Gates: A target ancilla is flipped only if all constraints are met simultaneously.
Uncomputation: Intermediate calculations are reversed to reset ancilla qubits, ensuring the oracle is reversible and interference-free.

D. Grover Iteration

The algorithm applies the oracle ( $O$ ) followed by the diffusion operator ( $D$ ) iteratively.

Diffusion Operator: Inverts amplitudes about the mean to amplify marked states.
Optimal Iterations: The number of iterations $k$ is calculated as $k \approx \frac{\pi}{4}\sqrt{N/M}$ , where $N$ is the search space size and $M$ is the number of solutions.

E. Measurement & Verification

After $k$ iterations, the register is measured. A classical post-processing step verifies the output. If the result is invalid (due to statistical probability or incorrect $k$ ), the circuit is re-executed.

3. Key Contributions

Formal Encoding: A rigorous mapping of the Magic Square CSP to a quantum search problem using Grover's algorithm.
Reversible Oracle Design: Construction of a constraint oracle using modular arithmetic circuits and multi-controlled gates to handle sum and uniqueness constraints.
Structured Hybrid Pipeline: A clear separation where classical methods (Siamese construction) handle initialization/domain reduction, while the quantum component handles the search, distinct from iterative hybrid solvers.
Comprehensive Benchmarking: Empirical comparison against classical brute-force enumeration and backtracking using the Qiskit framework.
Implementation: A complete end-to-end Qiskit implementation demonstrating multi-register modular arithmetic and oracle logic.

4. Experimental Results

Experiments were conducted on IBM's Qiskit using statevector simulators.

Case 1: Index Search (5x5 Game):
- Task: Find the index of a specific number in a pre-generated $5 \times 5$ square ( $N=25$ ).
- Result: Successfully located the target in 3 iterations using 5 qubits, validating the basic Grover primitive.
Case 2: Constraint Search (3x3 Generation):
- Task: Generate a valid $3 \times 3$ magic square from scratch ( $N = 362,880$ ).
- Query Complexity:
  - Brute-Force: Checked 69,075 permutations (Runtime: 0.0744s).
  - Grover's Algorithm: Theoretical requirement is $\approx 602$ oracle calls ( $\sqrt{N}$ ).
  - Backtracking: Runtime 0.0033s.
- Runtime Comparison: The simulated quantum runtime was 0.0053s (vs. 0.0744s for brute-force).
- Circuit Details: Used a 9-qubit register for the $3 \times 3$ case.
Limitations Observed:
- Simulation Overhead: The observed speedup in runtime is masked by the exponential memory cost of simulating quantum circuits on classical hardware. The 0.0053s runtime reflects classical simulation overhead, not true quantum hardware speed.
- Scalability: Full constraint oracles for $n \ge 4$ require $\approx 30$ qubits, exceeding the memory capacity of standard workstations for statevector simulation.
- Hardware Noise: Current NISQ (Noisy Intermediate-Scale Quantum) devices lack the qubit count and fidelity (due to gate errors and decoherence) to run the deep circuits required for larger grids.

5. Significance and Conclusion

Theoretical Validation: The paper confirms the theoretical quadratic query advantage ( $O(\sqrt{N})$ ) of Grover's algorithm over classical unstructured search ( $O(N)$ ) for CSPs.
Proof of Concept: It demonstrates that complex combinatorial constraints (sums, diagonals, uniqueness) can be faithfully encoded into reversible quantum circuits.
Future Directions: The authors suggest that genuine quantum advantage will only be observable on actual quantum hardware with error correction for grids of size $n \ge 4$ . Future work includes optimizing reversible arithmetic (e.g., carry-lookahead adders), testing on real IBM Quantum hardware, and applying the methodology to other CSPs like Sudoku and Latin squares.

In summary, while current hardware limitations prevent a practical demonstration of speedup on large grids, this work successfully establishes the architectural blueprint for solving Magic Square problems via quantum search, bridging the gap between classical constraint satisfaction and quantum amplitude amplification.