A search space is the set of candidate inputs that might solve a search problem. In Grover’s algorithm, it is represented by basis states for those inputs; if it contains N inputs, its mean state is an equal superposition: |mean⟩ = (1/√N) Σx |x⟩. When no structure is known, the space can be all n-bit strings, with N = 2ⁿ. section 7.2.1
Figure 7.5 The main states used in Grover’s search algorithm. \(\ket{\textrm{mean}}\) is the superposition of all basis states in the search space (that is, states that correspond to bit strings that are potential solutions to the problem). These bit strings can be split in two groups: the ones that are solutions (included in the superposition \(\ket{\textrm{solutions}}\)) and the ones that are not (\(\ket{\textrm{non-solutions}}\)). The angle \(\theta\) is defined by the number of problem solutions and the size of the search space.
The mean state spans all candidate basis states, partitioned into solution and non-solution states. The number of solutions and the search-space size determine the displayed angle. section 7.2.1
Choosing the space is part of designing the algorithm, not merely choosing an input format. Exclude inputs that violate constraints with certainty, while retaining every real solution. A smaller space reduces Grover iterations and can remove checks from the oracle because those invalid states are never prepared. section 8.2 section 8.5
N queens: encode one queen per row
For an N-queens board, bit-per-cell inputs include placements with too few or too many queens and placements with multiple queens in a row. Restricting the space to states with exactly one occupied cell per row encodes the row constraint directly. The mean state becomes a tensor product of N W states, one per row; the oracle can then focus on column and diagonal conflicts. section 8.2.1
A more compact encoding can change representation without changing the reduced space. Represent each row by the column index of its queen, using ⌈log₂ N⌉ bits per row rather than N bits. This still represents Nᴺ one-queen-per-row inputs, but uses N⌈log₂ N⌉ bits instead of N² and changes the mean state and oracle implementation. 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.
Each row is represented by one column-index integer, making the one-queen-per-row constraint part of the encoding rather than an oracle check. section 8.3.1
When selecting a search-space representation, evaluate:
- Which candidate inputs are provably invalid and can be excluded without losing solutions. section 8.2.1
- Whether a different encoding reduces qubits or simplifies evaluating the oracle even when the candidate count is unchanged. section 8.3.1 section 8.5
- Simulator costs: qubit count, program length, and the number of basis states manipulated in superposition. section 8.5
