L18 Grover's Algorithm II
Overview
Grover's algorithm searches an unstructured database of N entries by encoding the marked index as a basis state and repeatedly applying a phase oracle and diffusion operator. In the two-dimensional space spanned by the marked state and its orthogonal complement, each Grover iteration rotates the state by about 2/√N, so roughly (π/4)√N oracle iterations amplify the marked item; an XOR oracle can implement the phase change using an ancilla in the |−⟩ state.
Key takeaways
- For one marked item among N = 2ⁿ possibilities, the uniform state's marked amplitude is 1/√N, which sets the small rotation angle underlying Grover's speedup.
- The combination of phase oracle V and diffusion operator W rotates the search state by 2θ per iteration in the plane spanned by the marked state and its orthogonal complement.
- About (π/4)√N Grover iterations amplify one marked item, compared with order N queries for classical unstructured search.
- The optimal Grover measurement point is not always reached exactly; checking each measured candidate with the search function supports practical retries.
- An XOR oracle produces the phase-oracle action through phase kickback when its target qubit is prepared in |−⟩, adding an ancilla while leaving that ancilla unchanged.
- Quantum search performance depends on more than query count: gate time, coherence, fidelity, readout, and error-correction overhead vary across superconducting, spin, trapped-ion, and neutral-atom architectures.
Chapters
- The search problem is represented by a Boolean function with f(a) = 1 for the target index a and f(x) = 0 for all other indices.
- For n qubits, the search space contains N = 2ⁿ basis states, from |0⟩ through |2ⁿ − 1⟩.
- The uniform state |φ⟩ is prepared with Hadamard gates and has amplitude 1/√N on each basis state.
- The state |a⊥⟩ is the normalized superposition of the N − 1 basis states other than the marked state |a⟩.
- Its normalization factor is 1/√(N − 1), while |φ⟩ is normalized by 1/√N.
- For large N, |a⊥⟩ and |φ⟩ are close because they differ mainly by the contribution of one basis state.
- The overlap of the marked state with the uniform state is ⟨a|φ⟩ = 1/√N, since exactly one term in the uniform sum matches |a⟩.
- Writing θ for the small angle between |φ⟩ and |a⊥⟩ gives sin θ = 1/√N, so θ is approximately 1/√N for large N.
- The inverse-square-root angle foreshadows Grover's quadratic query advantage.
- The phase oracle V reflects a state across the subspace perpendicular to the marked state, equivalently rotating a vector by twice its angle to |a⊥⟩.
- The diffusion operator W reflects across the uniform state |φ⟩, producing a rotation of twice the angle to |φ⟩.
- The lecture relates these geometric reflections to the operators used in Grover's algorithm.
- Applying V first and W second yields the combined operation WV, which rotates vectors in the search plane by 2θ toward |a⟩.
- The rotation angle depends on the separation between |φ⟩ and |a⊥⟩, not on the starting vector's position within the plane.
- Each iteration increases the marked-state component, making measurement more likely to return the target.
- A state close to |a⊥⟩ has very little amplitude on |a⟩, so an immediate measurement is unlikely to find the target.
- Repeated WV operations transfer amplitude toward |a⟩; measurement after the appropriate number of iterations can return the marked index with high probability.
- The result can be checked against f, allowing a failed measurement to be rejected and the algorithm run again.
- The initial angle from |φ⟩ to |a⟩ is approximately π/2, and each WV iteration advances the state by 2θ.
- The estimated iteration count is π/(4θ), which becomes approximately (π/4)√N because θ ≈ 1/√N.
- This reduces unstructured search from order N classical queries to order √N oracle queries.
- The small-angle approximation is most useful when N is large; for a small database, classical search may be more practical.
- The iteration count may undershoot or overshoot the best measurement point, so Grover search does not always guarantee a 100% success probability.
- A candidate can be tested using the search condition f, making retries useful when verification is inexpensive.
- The circuit applies Hadamard gates to |0⟩ to create |φ⟩, then repeats the phase oracle V and diffusion operator W before measurement.
- For a database of one trillion entries, the approximate query count is one million, while increasing the number of entries primarily increases the required qubit count logarithmically.
- Gate durations and error-correction overhead depend on architecture: superconducting and spin-qubit gates may take tens of nanoseconds, while trapped-ion or neutral-atom gates can be slower but offer different coherence properties.
- The XOR oracle is defined by U_f|x,y⟩ = |x, y ⊕ f(x)⟩, where ⊕ denotes exclusive OR.
- Preparing the output ancilla in |−⟩ = (|0⟩ − |1⟩)/√2 gives phase kickback: U_f|x⟩|−⟩ = (−1)^{f(x)}|x⟩|−⟩.
- The ancilla remains in |−⟩ and unentangled, while the index register receives the same phase marking as the phase oracle V.
- The XOR-oracle circuit prepares the index register with Hadamard gates and prepares the ancilla with X followed by H to create |−⟩.
- After each U_f call, the index register undergoes the diffusion step and the oracle-diffusion sequence is repeated to amplify the marked state.
- Whether the XOR or phase-oracle implementation is preferable depends on the available gates, circuit size, fidelity, and hardware architecture.
Transcript excerpt
0:12 We will continue on Grover's algorithm, but let me remind you what what is the background and what is the picture. We try to search for something in an unstructured database. And uh uh this one And uh goal is that in this database you have indices and we know that if you find what you want, that one will give you one for a complex function, yeah. >> So, we should >> So, uh we have f of a equal to 1, right? And then for the rest is f of x not equal to a equal to 0, right?
0:59 So, we say that there are three very important vector. Of course, the first is a. We encode it as the basis vector of this system. This is called basis encoding. And then we have another vector, which is a perpendicular. This is not any arbitrary vector that that is perpendicular to a. It is a superposition of all bases except a, right? And then um one more important vector is phi. Phi is the superposition of all basis vector, right? Maybe you can tell me what is phi as a review. Anyone remember? It's the superposition of all basis vector.
1:47 Okay, good. At least he remembered that you can construct it by Hadamard gate on zero, right? And then but what is the result? >> 0 + 1 So 0 + 1 + 2 and then I'm going to use this summation. Is it N or what? All the way to what? Huh? Is it okay, capital N minus 1? What if I have small n cubit? What would that be? 2 to the power small n minus 1. Makes sense? Yeah. So this is X. But this vector is not normalized, right? How do we normalize it?
This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.
In this course
Related notes
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.