L17 Grover's Algorithm I

Overview

Hiu-Yung Wong introduces Grover's search algorithm for an unstructured database of N entries, contrasting the classical average of N/2 queries with Grover's approximately (π/4)√N oracle queries. The lecture develops the oracle using a five-qubit example with target 10010, then defines the target and uniform-superposition states and derives the two reflections that underpin Grover's search, including a Hadamard-based implementation of the diffusion operator.

Key takeaways

For an unstructured database with N entries and one marked item, Grover's search uses approximately (π/4)√N oracle queries instead of the classical average of N/2.
The reversible query oracle U_f|x,y⟩ = |x, y ⊕ f(x)⟩ evaluates a Boolean search predicate while preserving the index register.
The phase-oracle form V|x⟩ = (−1)^{f(x)}|x⟩ marks the desired basis state by a sign change, equivalent to reflecting across the subspace of non-target states.
The uniform state |φ⟩ = H⊗ⁿ|0⟩⊗ⁿ and the marked-state decomposition define the two-dimensional geometry in which Grover's reflections can be understood.
The diffusion operator W = 2|φ⟩⟨φ| − I is implemented as H⊗ⁿ(2|0⟩⟨0| − I)H⊗ⁿ, reducing its construction to Hadamard gates and a zero-state phase operation.

Chapters

0:00 Unstructured Search: Classical N/2 Queries Versus Grover's √N

Binary search takes O(log N) only when a database is structured, such as entries sorted by student ID.
For an unstructured database with N entries, a classical linear scan needs N/2 queries on average.
Grover's algorithm needs approximately (π/4)√N queries, a quadratic speedup; for N = 1,000,000, that is about 1,000 queries.

8:33 Representing the Search Target as a Boolean Function

The search is encoded by a Boolean function f(x), with f(a) = 1 for the desired index a and f(x) = 0 for every other index.
The index x represents a database location; evaluating f(x) checks whether the content at that location satisfies the search condition.
The approach applies to different predicates, such as matching a student ID or identifying an image that meets a specified criterion.

10:09 The XOR Oracle and Its Five-Qubit Search Example

The reversible oracle is U_f|x,y⟩ = |x, y ⊕ f(x)⟩, preserving x while XORing the function result into an output qubit.
For the example x = 10010, five qubits encode 32 database indices, and the target index is decimal 18.
Because f(x) is one bit, the oracle uses five index qubits and one output qubit.

12:44 Implementing and Interpreting the Marked-Item Oracle

The circuit example uses a multi-controlled NOT that flips the output qubit only when the input matches the marked bit string 10010.
With x = 10010 and y = 0, the oracle outputs x = 10010 and y = 1; other indices leave the output bit unchanged.
The oracle depends on the search predicate, so changing the target or condition requires changing the function encoded by the oracle.
The gate-level example illustrates the oracle's action; constructing an efficient oracle for a real search problem is a separate challenge.

19:48 Encoding Database Indices as Quantum Basis States

A database of N = 2ⁿ entries can be indexed using n qubits, whose computational basis states represent indices from 0 through N − 1.
The five-qubit example has 32 basis states, and the desired index is represented by the basis state |10010⟩.
The target state |a⟩ is one of the central vectors used to describe Grover's search geometrically.

24:00 Constructing the Uniform Superposition of Non-Targets

The state |a⊥⟩ is defined as the normalized sum of every computational basis state except the target |a⟩.
For n qubits, this state contains 2ⁿ − 1 terms and has normalization factor 1/√(2ⁿ − 1).
When N = 32 and a = 18, |a⊥⟩ includes all indices from 0 to 31 except 18, with normalization 1/√31.

25:07 Proving the Target and Non-Target States Are Orthogonal

The inner product ⟨a|a⊥⟩ is zero because |a⊥⟩ contains no component along the target basis state |a⟩.
Using ⟨a|x⟩ = δₐₓ makes the result explicit: every term in the sum has x ≠ a and therefore contributes zero.
The pair |a⟩ and |a⊥⟩ provides a two-dimensional plane for describing the algorithm's state changes.

32:53 The Uniform State and Grover's Two Reflection Operators

The state |φ⟩ is the equal superposition of all N = 2ⁿ basis states, normalized by 1/√N.
Applying H⊗ⁿ to |0⟩⊗ⁿ prepares |φ⟩, giving every database index equal measurement probability.
The lecture introduces V, a reflection about |a⊥⟩, and W, a reflection about |φ⟩, as the two geometric operations used in Grover's method.

36:56 The Phase Oracle Marks the Target with a Sign Flip

The phase oracle acts as V|x⟩ = (−1)^{f(x)}|x⟩, leaving each basis state in place while changing its phase when f(x) = 1.
For the marked state |a⟩, f(a) = 1, so V|a⟩ = −|a⟩; every non-target state remains unchanged.
The oracle embeds the search predicate into the quantum state as a phase rather than storing f(x) in an extra output qubit.

40:29 Why the Phase Oracle Reflects About the Non-Target State

Any state in the span of |a⟩ and |a⊥⟩ can be written as β₀|a⟩ + β₁|a⊥⟩.
Applying V changes this to −β₀|a⟩ + β₁|a⊥⟩, reversing only the target component.
Geometrically, that sign change reflects the state across the |a⊥⟩ axis, yielding V = I − 2|a⟩⟨a|.

48:26 Deriving the Diffusion Reflection About the Uniform State

The second operator is W = 2|φ⟩⟨φ| − I, with |φ⟩ the normalized equal superposition of all database indices.
Writing a general state as γ₀|φ⟩ + γ₁|φ⊥⟩ shows that W preserves γ₀ and reverses the sign of γ₁.
That component change makes W a reflection about |φ⟩, distinct from the oracle's reflection about |a⊥⟩.

54:17 Implementing the Diffusion Operator with Hadamard Gates

Since |φ⟩ = H⊗ⁿ|0⟩⊗ⁿ, the projector |φ⟩⟨φ| can be expressed using Hadamard gates around the all-zero-state projector.
The resulting implementation is W = H⊗ⁿ(2|0⟩⟨0| − I)H⊗ⁿ.
The central zero-state phase operation can be built from NOT gates and controlled-Z operations, while the surrounding H⊗ⁿ gates change into and out of the computational basis.

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Quantum Computing, TCAD, Semicond by Hiu-Yung Wong.