A Grover iterate repeats two operations: a phase oracle followed by a reflection about the mean. Together, these reflections rotate the state by 2θ toward the solution subspace, increasing the probability of measuring a solution until further iterations overshoot the optimum. section 7.2.2
A complete search procedure uses the iterate in this sequence:
- Prepare the mean state, the equal superposition over the search space. section 7.2.2
- Apply the chosen number of Grover iterates, each combining the phase oracle and mean reflection. section 7.2.2
- Measure the input register and verify the result because the algorithm remains probabilistic. section 7.2.2
Hand-built Qiskit iterate
Construct a phase oracle, append it to an iterate circuit, then implement reflection about the mean with prepare_mean.inverse(), X gates, a controlled Z operation, and prepare_mean. Convert the completed iterate to a gate and apply its n-th power before measurement. Test repeated executions by checking that every measured result is marked. section 7.2.3
Figure 7.7 The overall structure of Grover’s search algorithm. You start by preparing the system in the mean state, the average of all states in the search space. Then you apply several iterations, each com-posed of applying the phase oracle followed by a reflection about the mean. Finally, you measure the system and check whether the result is an answer to the problem.
Use the algorithm structure to trace preparation of the mean state, repeated oracle–reflection pairs, measurement, and result checking. section 7.2.2
Listing 7.3 Qiskit code for Grover’s search algorithm
def grovers_search(n_bits, marking_oracle, prepare_mean, n_iterations):
iter = QuantumCircuit(n_bits + 1) #1
phase_or = phase_oracle(n_bits, marking_oracle) #2
iter.append(phase_or, range(n_bits + 1)) #3
iter.append(prepare_mean.inverse(), range(n_bits))
iter.x(range(n_bits))
iter.append(ZGate().control(n_bits - 1),
range(n_bits))
iter.x(range(n_bits))
iter.append(prepare_mean, range(n_bits)) #4
circ = QuantumCircuit(n_bits + 1, n_bits) #5
circ.append(prepare_mean, range(n_bits)) #6
circ.append(iter.to_gate().power(n_iterations), #7
range(n_bits + 1))
circ.measure(range(n_bits), range(n_bits)) #8
return circ
Inspect the complete hand-built Qiskit circuit, including gate inversion, mean reflection, repeated iteration, and measurement. section 7.2.3
