Your objective
Understand the problem Grover’s algorithm solves, the amplification of amplitude via the Grover iterate, and implement a simple 2‑qubit Grover search.
6.1 Search Problem
Define the oracle that marks the solution and the need for amplitude amplification.
Oracle: |x⟩ → (-1) if x = ω else |x⟩
6.2 Grover Iterate
Each Grover iteration consists of an oracle call followed by the diffusion operator, rotating the state toward the marked item.
|ψ⟩ → Oracle → Diffusion → |ψ'⟩
6.3 Optimal Number of Iterations
For a single marked item, approximately π/4·√N iterations maximize the success probability.
Iterations ≈ π/4·√N
Put it together
Worked example
Search in a 4‑item database (2 qubits) with marked item |11⟩. With one marked item, one Grover iteration (oracle + diffusion) rotates the equal superposition to |11⟩ with certainty in the ideal circuit.
Key takeaways
• Grover’s algorithm finds a marked item in O(√N) queries. • The algorithm uses phase inversion and diffusion to amplify the marked amplitude. • It works for any number of marked items, scaling accordingly.
Knowledge check / 3 questions