Grover’s algorithm searches an unstructured space by increasing the measurement probability of outcomes that satisfy a search criterion. It can provide a quadratic speedup over classical search for suitable problems, including search, optimization, and machine-learning applications. section 6.0 section 6.3
Build the algorithm from a state-preparation operator, an oracle, and repeated amplification:
- Prepare a starting state A, often with equal magnitudes across possible outcomes. section 6.2.4
- Use an oracle O to tag desired outcomes by multiplying their amplitudes by −1. section 6.3
- Apply the inversion operator to increase tagged amplitudes and decrease untagged amplitudes. section 6.3
- Repeat the Grover iterate an appropriate number of times, then measure; the amplified outcomes are more likely to appear. section 6.2.4 section 12.1.2
Three-qubit search
Represent eight items with three qubits and mark outcomes 1, 3, and 7. Prepare a uniform state, construct a phase oracle for those outcomes, and apply the Grover circuit. In this example, one iteration is optimal; reports can inspect amplitude changes after the iteration. section 6.2.4
Searching encoded function values
After encoding f(k) = k + 1, use an oracle that matches the leading 1 in the value register to search for outputs at least 4. One Grover iteration amplifies the qualifying key–value pair. section 10.2
Listing 6.9 Function to create the magnitude amplification circuit
def grover_circuit(A, O, iterations):
n = sum(A.regs)
q = QuantumRegister(n)
qc = QuantumCircuit(q)
qc.append(A, q)
for i in range(1, iterations + 1):
qc.append(grover_iterate_circuit(A, O), q)
qc.report(f'iteration_{i}')
return qc
Use the circuit-building listing to see how state preparation, repeated Grover iterates, and per-iteration reports become executable Python structure. section 6.2.4
