Quantum Algorithms (part 2: 4.4–4.5)
Open in the Padhaiko app4.4 Grover’s algorithm
Grover's algorithm (Lov Grover, 1996) solves the unstructured search problem: given a search space of elements and a black-box oracle function that marks target solutions ( if is a solution and otherwise, with ), find a marked item .
- Classical Lower Bound: Without structure in the database, a classical algorithm must inspect items one by one, requiring queries on average and queries in the worst case for ().
- Quantum Speedup: Grover's algorithm locates a marked element with high probability using only oracle queries—a provable quadratic speedup that is asymptotically optimal for any quantum unstructured search algorithm (Bennett, Bernstein, Brassard, and Vazirani).
Architecture of the Grover Iteration
Grover's Search Algorithm and Operators
Initialize an -qubit register to the uniform superposition state :
Decompose the Hilbert space into two orthogonal unit vectors:
- Good (marked) subspace state:
- Bad (unmarked) subspace state:
In this two-dimensional plane, the initial uniform state is:
Each Grover iteration applies the unitary Grover operator , consisting of two steps:
- Phase Oracle (): Marks solution states by inverting their phase:
Geometrically, reflects the state vector across , mapping .
- Diffusion Operator (, Inversion About the Mean): Amplifies the marked amplitudes:
Geometrically, reflects the state vector across the initial state . Algebraically, for any state with mean amplitude , maps every amplitude to:
Geometric Rotation and Optimal Iteration Count
Amplitude Amplification and Optimal Query Count
Because the composition of two reflections in a plane separated by angle is a rotation by angle , each application of the Grover operator rotates the state vector toward by . After iterations:
The probability of measuring a marked solution after iterations is:
To maximize , we set , giving the optimal integer number of Grover iterations:
4.5 Shor’s algorithm
Shor's algorithm (Peter Shor, 1994) finds the prime factors of a large composite integer in polynomial time —an exponential speedup over the fastest known classical algorithm (the General Number Field Sieve), which runs in sub-exponential time . Because the security of RSA public-key encryption relies on the classical hardness of integer factorization, Shor's algorithm has major cryptographic significance.
Classical Reduction: Factoring to Order-Finding
Shor's algorithm does not factor directly on the quantum computer; instead, it uses a classical number-theoretic reduction to the order-finding problem, solving only the order-finding step quantum mechanically:
Factoring via Modular Order-Finding
Given an odd composite integer (not a prime power ):
- Pick a random integer with .
- Compute classically using Euclid's algorithm. If , then is already a non-trivial factor of .
- Otherwise . Find the order of , defined as the smallest positive integer such that:
- Check two conditions on :
- must be even ().
- (i.e., does not divide ). If both hold, then is divisible by , yet neither factor alone is a multiple of (since is minimal so , and ). Therefore:
are guaranteed to yield non-trivial factors of . (For random coprime to , these conditions succeed with probability , where is the number of distinct odd prime factors of .)
The Quantum Fourier Transform (QFT) and Quantum Period-Finding
To find the period of the modular exponentiation function efficiently, Shor's algorithm uses the Quantum Fourier Transform (QFT).
Quantum Fourier Transform (QFT)
On an -qubit register of dimension , the Quantum Fourier Transform maps each computational basis state () to a superposition with Fourier phase factors:
Its inverse () reverses the sign in the exponent:
Using Hadamard gates and controlled phase rotation gates , the QFT requires only quantum gates, compared to operations for the classical Fast Fourier Transform (FFT).
Step-by-Step Execution of Shor's Quantum Subroutine
Let be chosen such that (giving counting qubits in Register 1, plus qubits in Register 2):
- Initialization & Superposition: Prepare and apply to Register 1:
- Modular Exponentiation: Apply the unitary :
- Register 2 Measurement (Conceptual): Measuring Register 2 yields some value and projects Register 1 into a periodic superposition of indices spaced by :
(Note: in practice, Register 2 does not even need to be measured.)
- Inverse QFT (): Apply to Register 1. Because has period , constructive interference produces sharp probability peaks at integers satisfying:
with .
- Continued Fractions Post-Processing: Measure Register 1 to obtain . Because , the fraction is a convergent in the continued fractions expansion of , allowing classical extraction of (if , which happens frequently; otherwise a few repetitions or taking the LCM of candidates recovers ).
| Aspect | Grover's Algorithm | Shor's Algorithm |
|---|---|---|
| Problem Solved | Unstructured database search () | Integer factorization / discrete logarithm (period finding) |
| Key Mechanism | Amplitude amplification (phase oracle + diffusion) | Quantum Phase Estimation / Inverse QFT + continued fractions |
| Quantum Complexity | queries | gates |
| Classical Complexity | queries | (GNFS) |
| Type of Speedup | Quadratic (provably optimal for black-box search) | Exponential (over best known classical algorithms) |
| Cryptographic Impact | Halves symmetric key security (e.g., AES-256 128-bit equivalent) | Breaks RSA, Diffie–Hellman, and ECC completely |
Worked Examples
4.4
Execute Grover's search algorithm for ( qubits) where the single marked target state is . Trace the amplitudes of all four basis states through one Grover iteration , and find the probability of measuring .
Initial Uniform Superposition (): For , applying to gives:
Every basis state starts with amplitude .
Applying the Phase Oracle (): The oracle flips the sign of the marked state and leaves all other basis states unchanged:
So the amplitudes become .
Computing the Mean Amplitude and Applying Diffusion ():
Compute the mean amplitude of :
Thus . Applying to each component:
Hence, after Grover iteration:
After Grover iteration, the state is , so the target is measured with probability ().
4.5
In Grover's algorithm for ( qubits) with marked item:
- Find the initial rotation angle and the optimal number of iterations .
- Compute the success probability for and iterations, and demonstrate the effect of over-rotation at .
Finding and : With and :
Using the optimal iteration formula:
Evaluating Success Probability for : Using :
- For : Angle is . Using :
- For (optimal): Angle is . Since :
- For (over-rotated): Angle is (far past ). Since :
- , iterations.
- Success probabilities: , (peak), and (sharp drop due to over-rotation past ).
4.6
Trace Shor's factoring algorithm to factor using the randomly chosen coprime base . Compute the period of and extract the non-trivial prime factors of .
Checking Coprimality: Compute , so is coprime to and we proceed to order-finding.
Finding the Period of : Evaluating powers of modulo :
The sequence repeats every steps (), so the quantum period-finding subroutine outputs .
Verifying Evenness and Non-Triviality Condition:
- is even, so is an integer.
- Check (since ).
Both conditions hold, so we compute the greatest common divisors:
The period of is , and Euclid's algorithm yields the prime factors and ().
Practice Exercises
Practice Exercises — Grover's and Shor's Algorithms
For an unstructured database of items ( qubits) with marked solution:
- Calculate the optimal number of Grover iterations .
- Compute the success probability after running iterations.
Calculating and Optimal Iterations : With and :
Computing Success Probability at : At , the total rotation angle is ():
- Optimal iterations:
- Success probability: ()
Trace one iteration of Grover's algorithm on qubits () when the marked state is . Write down the state vector after , after the oracle , and after the diffusion operator .
Initial Superposition and Oracle Action: After :
Applying flips the phase of :
Applying Diffusion Operator (Inversion About the Mean): The mean of the four amplitudes is:
Applying :
Thus .
- After :
- After :
- After : (measured with probability )
Using the -qubit Quantum Fourier Transform definition , compute (the state corresponding to computational basis ) explicitly in the computational basis .
Substituting and : From the QFT formula with and :
since .
Expanding Each Basis Term:
- ():
- ():
- ():
- ():
Combining the terms:
Apply the classical post-processing steps of Shor's algorithm to factor using base . Compute the powers to determine the order , verify that satisfies the required conditions, and compute the factors of .
Checking Coprimality and Finding Order : . Computing successive powers :
Thus, the order is .
Verifying Conditions and Extracting Factors:
- is even ().
- (since ).
Computing the GCDs:
The order of is , yielding the prime factors and ().
In Shor's factoring algorithm for , suppose the random base chosen is . Find the order of , and explain why this choice of fails to produce non-trivial factors of even though is even.
Computing the Order of : Evaluating powers of (noting ):
Hence, the order is , which is even ().
Checking the Non-Triviality Condition: Evaluating :
Because , divides completely, while :
- (trivial)
- (trivial)
Thus, when , the algorithm simply discards and picks a new random base .
For , the order is (even), but . This yields only the trivial factors and , requiring Shor's algorithm to retry with another random base .