PadhaikoAll subjects

Quantum Algorithms (part 2: 4.4–4.5)

Quantum Computing (ENCT 328)

Open in the Padhaiko app

4.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 .

Architecture of the Grover Iteration

Definition

Grover's Search Algorithm and Operators

Initialize an -qubit register to the uniform superposition state :

Decompose the Hilbert space into two orthogonal unit vectors:

In this two-dimensional plane, the initial uniform state is:

Each Grover iteration applies the unitary Grover operator , consisting of two steps:

  1. Phase Oracle (): Marks solution states by inverting their phase:

Geometrically, reflects the state vector across , mapping .

  1. 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

Theorem

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:

Definition

Factoring via Modular Order-Finding

Given an odd composite integer (not a prime power ):

  1. Pick a random integer with .
  2. Compute classically using Euclid's algorithm. If , then is already a non-trivial factor of .
  3. Otherwise . Find the order of , defined as the smallest positive integer such that:
  1. 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).

Definition

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):

  1. Initialization & Superposition: Prepare and apply to Register 1:
  1. Modular Exponentiation: Apply the unitary :
  1. 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.)

  1. Inverse QFT (): Apply to Register 1. Because has period , constructive interference produces sharp probability peaks at integers satisfying:

with .

  1. 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 ).
AspectGrover's AlgorithmShor's Algorithm
Problem SolvedUnstructured database search ()Integer factorization / discrete logarithm (period finding)
Key MechanismAmplitude amplification (phase oracle + diffusion)Quantum Phase Estimation / Inverse QFT + continued fractions
Quantum Complexity queries gates
Classical Complexity queries (GNFS)
Type of SpeedupQuadratic (provably optimal for black-box search)Exponential (over best known classical algorithms)
Cryptographic ImpactHalves symmetric key security (e.g., AES-256 128-bit equivalent)Breaks RSA, Diffie–Hellman, and ECC completely

Worked Examples

Example 4.4

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:

Answer:

After Grover iteration, the state is , so the target is measured with probability ().

Example 4.5

4.5

In Grover's algorithm for ( qubits) with marked item:

  1. Find the initial rotation angle and the optimal number of iterations .
  2. 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 :
Answer:
  1. , iterations.
  2. Success probabilities: , (peak), and (sharp drop due to over-rotation past ).
Example 4.6

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:

  1. is even, so is an integer.
  2. Check (since ).

Both conditions hold, so we compute the greatest common divisors:

Answer:

The period of is , and Euclid's algorithm yields the prime factors and ().


Practice Exercises

Practice Exercises — Grover's and Shor's Algorithms

Question 1

For an unstructured database of items ( qubits) with marked solution:

  1. Calculate the optimal number of Grover iterations .
  2. Compute the success probability after running iterations.

Calculating and Optimal Iterations : With and :

Computing Success Probability at : At , the total rotation angle is ():

Answer:
  1. Optimal iterations:
  2. Success probability: ()
Question 2

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 .

Answer:
  • After :
  • After :
  • After : (measured with probability )
Question 3

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:

Answer:

Question 4

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:

  1. is even ().
  2. (since ).

Computing the GCDs:

Answer:

The order of is , yielding the prime factors and ().

Question 5

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 .

Answer:

For , the order is (even), but . This yields only the trivial factors and , requiring Shor's algorithm to retry with another random base .

← Quantum Algorithms (part 1: 4.1–4.3)Quantum Hardware and NISQ Era →