A solution state is the normalized superposition of basis states whose input bit strings satisfy the problem condition, f(x) = 1. Grover’s algorithm separates these states from non-solutions within the search space. section 7.2.1
The state is characterized by its role in the search space:
- It contains exactly the basis states representing problem solutions. section 7.2.1
- Its solution count is denoted M, while the full search space has size N. section 7.2.1
- It forms one of the two groups used to describe Grover’s main quantum states; the other contains non-solutions. 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.
Figure 7.5 places the solution state alongside the mean and non-solution states, showing how candidate bit strings divide according to the problem condition. section 7.2.1
