8 Solve N queens puzzle using Grover’s algorithm

This chapter applies Grover’s algorithm to a substantive constraint-satisfaction task: the N queens puzzle. It walks through the full workflow for turning a classical “yes/no” specification into a quantum search: choose an input encoding, define the Boolean predicate f(x) capturing the constraints, implement a reversible marking oracle, prepare the mean state that spans the intended search space, and compose these into Grover iterations. Beyond the algorithmic ideas, the chapter emphasizes writing and testing oracles carefully, and shows end-to-end, hybrid implementations with both Qiskit and Q#, illustrating how to build, run, and evaluate quantum programs in practice.

The chapter first analyzes a naive encoding with one bit per board cell and a predicate that rejects any placement with two queens sharing a row, column, or diagonal. Although straightforward, this explodes resource use: even for N=4 the reversible oracle can require on the order of 100 qubits, and the 2^(N^2) search space (65,536 states for 4×4) implies roughly 142 Grover iterations—impractical for simulators. An improved approach encodes part of the constraints into the search space itself by preparing, per row, a W state that guarantees exactly one queen per row. This dramatically reduces the search space to N^N and simplifies the oracle: columns can be checked via parity and diagonals via per–row-pair XOR aggregation. For N=4 this uses about 26 qubits, a search space of 256 states, and around 9 optimal iterations, making simulation feasible; the chapter provides Qiskit and Q# code and targeted tests for the oracle.

A second, more compact encoding represents each row by the integer column index of its queen, requiring only ⎡log2 N⎤ qubits per row. The mean state becomes an equal superposition over 0…N−1 for each row, and the oracle merges column and diagonal checks by subtracting row-pair indices and ruling out differences of 0 and ±Δ (the row offset). Implemented with reversible adders/subtractors (using adjoints) and recycled ancillas, this variant further lowers qubit count (about 17 for N=4) while keeping the same N^N search size and ~9 optimal iterations. The chapter also outlines a further refinement: restrict the search to permutations (size N!), which cuts iterations substantially but raises state-preparation complexity. Throughout, the trade-offs between encoding, oracle cost, state preparation, and simulator limits are made explicit, with guidance on rigorous testing and performance evaluation.

Solving a search problem using Grover’s algorithm starts with deciding on the representation of the function input \(x\) and the way to calculate the function \(f(x)\) based on it. Then, we implement the marking oracle for this function and the operation that prepares the state \(\ket{\textrm{mean}}\) based on that decision. Finally, these building blocks are used in Grover’s search to get the end-to-end solution.

Valid and invalid placements of queens on a \(4 \times 4\) chessboard. The middle placement is valid: all queens are in different rows, columns, and diagonals. The left placement has two queens in the same column, and the right placement has two queens on the same diagonal, so they are invalid.

The naive input encoding uses one bit per board cell. This bit is 1 if there is a queen in this cell, or 0 if the cell is empty.

To improve on our naive solution, we can count the number of queens in each row and each column and check that there is exactly one. We can do the same for the diagonals, checking that the number of queens in each diagonal is zero or one.

Check that each column has exactly one queen, knowing that each row has exactly one queen. We can count the parity of the number of queens in each column and check that it’s odd. Any placement for which this constraint is not satisfied will have at least one empty column with even parity.

To check that no two queens share a diagonal, we check each pair of rows separately. For each pair of rows, we go through all pairs of cells within them that are on the same diagonal. Since each row has exactly one queen, at most one of these pairs of cells will have two queens in them at once, so we can combine the results of all checks for a pair of rows in the same bit using XOR.

The new input encoding relies on the fact that only inputs in which each row has exactly one queen can be solutions to the puzzle. We represent each row of the board as just one integer, the column index of the queen in that row.

To check that no two queens share a column or a diagonal, we need to check each pair of rows separately. For each pair of rows, we calculate the difference of the indices of queens within them. This difference cannot be equal to zero or to the difference between the indices of these rows.

• A search problem usually has multiple ways to describe it as the input \(x\) and the function \(f(x)\). Different descriptions can lead to solutions of different efficiency.
• The best way to speed up the solution to a search problem is reducing the search space size by analyzing the constraints and encoding part of them in the search space representation. This can lead to both simpler oracle implementation and fewer algorithm iterations necessary.
• If reducing search space size is not practical, it might be possible to change the encoding of the inputs within the search space to allow for simpler function evaluation and more efficient oracle implementation.
• When you implement a quantum algorithm to run on a quantum simulator, it is important to consider the total number of qubits used in the program, the length of the program, and, if running on a sparse simulator, the number of basis states in superposition states that are manipulated during the program execution.
• Sparse simulators are more efficient compared to full-state simulators for programs that act on a large number of qubits but only use a small subset of all basis states.

FAQ