An input encoding represents each queen’s position in a row as the integer index of its occupied column. Because every candidate has exactly one queen per row, the representation removes row-conflict checks from the oracle. section 8.3.1
For an N×N queens search, the encoding has these properties:
- Use ⌈log₂ N⌉ qubits for each row, requiring N⌈log₂ N⌉ qubits instead of N². section 8.3.1
- Keep N^N possible inputs: compact encoding does not reduce the search-space size by itself. section 8.3.1
- Prepare each row independently in an equal superposition of the N basis states representing integers 0 through N−1. section 8.3.1
- Evaluate column and diagonal conflicts by comparing column-index differences for pairs of rows. section 8.3.1
Four-queens encoding
For N = 4, each row stores one of the column indices 0, 1, 2, or 3 using two qubits. Each row therefore occupies an equal superposition of four basis states. section 8.3.1
Figure 8.7 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.
Visualize the board as one integer per row rather than one bit per cell. section 8.3.1
