A W state on N qubits is an equal superposition of the N computational-basis states containing exactly one 1 and N−1 zeros. In an N queens search, one W state represents one board row. section 8.2.1
Encoding an N queens search space
Prepare one |W_N⟩ state for each row and take their tensor product. Every basis state in the resulting mean state already places exactly one queen in every row, so Grover’s oracle can omit row-validity checks and focus on columns and diagonals. section 8.2.1
Using W states changes the validation workload:
- Exclude placements with zero or multiple queens per row before the search begins. section 8.2.1
- Check column uniqueness through parity rather than counting every column occupancy. section 8.2.1
- Check diagonal conflicts pairwise across rows and combine the results with XOR. section 8.2.1
Figure 8.5 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.
Shows how the row constraint supplied by W states lets the oracle test column validity using odd and even parities. section 8.2.1
