The non-solution state is the normalized superposition of every search-space basis state x for which f(x) = 0: |non-solutions⟩ = 1/√(N−M) Σ₍f(x)=0₎ |x⟩. With M solutions among N states, it contains N−M basis states. It is orthogonal to the solution state because each basis state belongs to exactly one group. section 7.2.1
Grover’s search algorithm treats all non-solutions identically, allowing the evolving state to be represented using only the solution and non-solution axes. The phase oracle reflects the state about the non-solution axis before reflection about the mean rotates it toward the solution state. 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.
Use the state-space diagram to compare the mean, solution, and non-solution superpositions and relate their amplitudes to N and M. section 7.2.1
