Unit 4: Quantum Algorithms - II

Dr. Venugopal K.

June 18, 2025

1 Grover’s Search Algorithm

These notes provide a detailed, beginner-friendly explanation of Grover’s Search Algorithm,
a quantum algorithm that offers a speedup over classical search methods. We will cover its
purpose, mathematical foundation, quantum circuit, and a step-by-step example, with all
mathematical derivations explained clearly.

1. What is Grover’s Search Algorithm?

Imagine you have a phonebook with N names, and you’re looking for a specific person’s
number, but the names aren’t sorted. Classically, you’d need to check each entry one by
one, taking up to N checks in the worst case, or about N/2 checks on average. Grover’s
Search Algorithm, developed
√ by Lov Grover in 1996, is a quantum algorithm that can find
the target in roughly N steps—a quadratic speedup!
In quantum computing terms, Grover’s algorithm searches an unstructured database (or
solves a search problem) where we have N = 2n items (since n qubits can represent 2n
states), and exactly one item satisfies a condition (e.g., the “target” state). It’s like finding
a marked card in a deck, but faster than classical methods.

Circuit

Figure 1: Grover’s Algorithm

1
 1 GROVER’S SEARCH ALGORITHM

2. The Problem Setup

Suppose we have N = 2n items, labeled as quantum states |0⟩, |1⟩, . . . , |N − 1⟩. Each state
is a binary string of n qubits (e.g., for n = 2, the states are |00⟩, |01⟩, |10⟩, |11⟩, so N = 4).
One of these states, say |w⟩, is the “winner” (the target we’re looking for). We don’t know
w in advance, but we have a function (called an oracle) that can tell us if a given state is
the target. The oracle acts as a black box:

1 if x = w (the target state),
f (x) =
0 otherwise.

Our goal is to find |w⟩ with as few queries to the oracle as possible.

3. How Grover’s Algorithm Works

Grover’s algorithm uses quantum superposition to check all items at once, then amplifies
the probability of the target state through repeated steps. Think of it like a game of “guess
who” with a twist: - You start with all possible guesses (all states in superposition). - Each
round, you use the oracle to√ slightly highlight the correct guess and dim the wrong ones. -
After a few rounds (about N ), the correct guess stands out, and you can measure it with
high probability.
The algorithm has two main steps that repeat: 1. Oracle Step: Marks the target state by
flipping its sign. 2. Diffusion Step: Amplifies the target state’s amplitude (probability) by
“reflecting” the state around the average amplitude.

Figure 2:

Department of Mathematics 2 RV College of Engineering

 1 GROVER’S SEARCH ALGORITHM

4. Mathematical Setup
Start with n qubits, all in the |0⟩ state: |0⟩⊗n . Apply a Hadamard gate (H) to each qubit
to create an equal superposition of all N = 2n states:
−1
1 NX
H ⊗n |0⟩⊗n = √ |x⟩.
N x=0

This state, often called |s⟩, gives each state an amplitude of √1 . The probability of measuring
N
any state |x⟩ is:
2
1 1
√ = .
N N
1
Since |s⟩ is a superposition, it includes the target state |w⟩, but its probability is only N
—too
small to find efficiently by measuring now.
Let’s break |s⟩ into two parts: - |w⟩: The target state. - |s⊥ ⟩: The superposition of all
non-target states.
First, define |s⊥ ⟩ as the sum of all states except |w⟩, normalized:
N −1
1
|s⊥ ⟩ = √
X
|x⟩.
N − 1 x=0
x̸=w

We can write |s⟩ as a combination of |w⟩ and |s⊥ ⟩. The amplitude of |w⟩ in |s⟩ is √1N , since
all states have equal amplitude. The inner product ⟨w|s⟩ = √1N , so we decompose:

|s⟩ = ⟨w|s⟩|w⟩ + ⟨s⊥ |s⟩|s⊥ ⟩.

- ⟨w|s⟩ = √1N . - The component in |s⊥ ⟩: Since ⟨w|s⊥ ⟩ = 0 (they’re orthogonal), the ampli-
tude of |s⊥ ⟩ is: s s
q 1 N −1
⟨s⊥ |s⟩ = 1 − |⟨w|s⟩|2 = 1 − = .
N N
Thus: s
1 N −1 ⊥
|s⟩ = √ |w⟩ + |s ⟩.
N N
  q
√1 , √1 N −1
Let’s define: - sin θ = N
so θ = arcsin N
. - cos θ = N
.
Then:
|s⟩ = sin θ|w⟩ + cos θ|s⊥ ⟩.
This geometric view helps us understand Grover’s algorithm as a rotation in a 2D plane
spanned by |w⟩ and |s⊥ ⟩.

Department of Mathematics 3 RV College of Engineering

 1 GROVER’S SEARCH ALGORITHM

5. Step 1: The Oracle Operator

The oracle operator O “marks” the target state by flipping its sign. Mathematically:

O|x⟩ = (−1)f (x) |x⟩.

- If x = w, f (w) = 1, so O|w⟩ = (−1)1 |w⟩ = −|w⟩. - If x ̸= w, f (x) = 0, so O|x⟩ = |x⟩.

Applying O to |s⟩:
 s  s
1 N −1 ⊥  1 N −1 ⊥
O|s⟩ = O  √ |w⟩ + |s ⟩ = − √ |w⟩ + |s ⟩.
N N N N

This is a reflection of |s⟩ across the |s⊥ ⟩-axis in the |w⟩-|s⊥ ⟩ plane.

6. Step 2: The Diffusion Operator

The diffusion operator D amplifies the target state’s amplitude. It’s defined as:

D = 2|s⟩⟨s| − I,

where I is the identity operator. This operator reflects the state around the vector |s⟩.
Let’s compute its effect. First, apply D to a general state |ψ⟩:

D|ψ⟩ = (2|s⟩⟨s| − I)|ψ⟩ = 2|s⟩⟨s|ψ⟩ − |ψ⟩.

For our state after the oracle, |ψ⟩ = O|s⟩, the diffusion step reflects O|s⟩ around |s⟩, increas-
ing the amplitude of |w⟩.
Each Grover iteration (oracle + diffusion) rotates the state vector by 2θ toward |w⟩: - Initial
angle: θ, where sin θ = √1N . - After one iteration, the angle becomes 3θ. - After k iterations,
the angle is (2k + 1)θ.
We want the state to be close to |w⟩, which happens when the angle is near π2 :
!
π 1 π
(2k + 1)θ ≈ =⇒ (2k + 1) arcsin √ ≈ .
2 N 2

For large N , θ ≈ √1 , so:

N

1 π π√
(2k + 1) √ ≈ =⇒ k ≈ N.
N 2 4
√ √
Thus, we need about π4 N ≈ 0.785 N iterations.

Department of Mathematics 4 RV College of Engineering

 1 GROVER’S SEARCH ALGORITHM

7. Example: Grover’s Algorithm with n = 2 Qubits

Let’s apply Grover’s algorithm for n = 2, so N = 4, and suppose the target state is |w⟩ = |10⟩.
Start with |00⟩, apply Hadamard gates:
1 1
|s⟩ = H ⊗2 |00⟩ = √ (|00⟩ + |01⟩ + |10⟩ + |11⟩) = (|00⟩ + |01⟩ + |10⟩ + |11⟩).
4 2
    √
- θ = arcsin √14 = arcsin 12 = π6 . - Number of iterations: k ≈ π4 4 = π4 · 2 = π2 . Since
(2k + 1) π6 ≈ π2 , 2k + 1 ≈ 3, so k = 1.
The oracle flips the sign of |10⟩:
1
O|s⟩ = (|00⟩ + |01⟩ − |10⟩ + |11⟩).
2

Compute D = 2|s⟩⟨s| − I. First, ⟨s| = 21 (⟨00| + ⟨01| + ⟨10| + ⟨11|), so:

1 1 1 1
− 21 1 1 1
 
4 4 4 4 2 2 2
1 1 1 1  1
− 12 1 1 
|s⟩⟨s| = D = 2|s⟩⟨s| − I = 
4 4 4 4 2 2 2
, .
 
1 1 1 1 1 1
4 4 4 4
  2 2
− 12 1
2

1 1 1 1 1 1 1
4 4 4 4 2 2 2
− 12

Apply D to O|s⟩:

− 12 1 1 1  1 
0
  
2 2 2 2
1
 − 12 1 1  1  0
2 2 2 = |10⟩.
 2 
D(O|s⟩) = =
  
1 1
− 21 1   1
 − 2  1
  
2 2 2

1 1 1
2 2 2
− 12 1
2
0

After one iteration, the state is |10⟩, the target! Measuring now gives |10⟩ with probability
1.

8. Why Does It Work?

Grover’s algorithm works because each√ iteration increases the amplitude of |w⟩ by rotating
the state vector closer to |w⟩. After N iterations, the probability of measuring |w⟩ is close
to 1, compared to the classical N1 .

9. Limitations
- Multiple
q Solutions: If there are M target states, the optimal number of iterations adjusts
to N/M .
- Quantum Hardware: Requires a quantum computer and a way to implement the oracle.
- Probabilistic Nature: The result is probabilistic, though the success probability is high
after the right number of iterations.

Department of Mathematics 5 RV College of Engineering

 2 SHOR’S QUANTUM FACTORING ALGORITHM: A BEGINNER’S GUIDE

Question
Explain the purpose of Grover’s Search Algorithm and its quantum advantage. For a 2-
qubit search space with one marked state |11⟩, compute the state after one iteration of the
Grover operator, starting from the uniform superposition state, and verify the probability
of measuring the marked state.

Solution
Grover’s
√ Search Algorithm finds a marked item in an unsorted database of N items in
O( N ) queries, compared to O(N ) classically, offering a quadratic speedup. For N =
22 = 4, the search space is {|00⟩, |01⟩, |10⟩, |11⟩}, with |11⟩ marked. The Grover operator
G = (2|s⟩⟨s| − I)Uf , where Uf |x⟩ = (−1)f (x) |x⟩ (f (x) = 1 if x = 11, else 0), and |s⟩ is the
uniform superposition.
Start with |s⟩ = H ⊗2 |00⟩ = 21 (|00⟩ + |01⟩ + |10⟩ + |11⟩). Apply Uf :
1
Uf |x⟩ = (−1)f (x) |x⟩, Uf |s⟩ = (|00⟩ + |01⟩ + |10⟩ − |11⟩).
2
Apply the diffusion operator 2|s⟩⟨s| − I:
1 1 1 1 1 1 1 1 1 0 0 0 −1 1 1 1
       

1 1
 1 1 1 1 1
 1 1 1 0
  1 0 0 1  1 −1 1
  1
|s⟩⟨s| =  ,

2|s⟩⟨s|−I =  − =  .

4 1 1 1 1 2 1 1 1 1 0 0 1 0 2  1 1 −1 1 
 

1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 −1
Compute:
−1 1 1 1 1 3
    

1 1  1 −1 1
 1  1  1  1 
    1
(2|s⟩⟨s|−I) (|00⟩+|01⟩+|10⟩−|11⟩) =  =   = (3|00⟩+|01⟩+|10⟩−5|11⟩

4 1 1 −1 1   1  4  1  4

2
1 1 1 −1 −1 −5
2
Probability of measuring |11⟩: Coefficient is − 45 , so probability is − 54 = 16
25
. Normalize the
state’s norm:
1 9 + 1 + 1 + 25 36 9
⟨ψ|ψ⟩ = (32 + 12 + 12 + (−5)2 ) = = = .
16 16 16 4
25
Actual probability: 169 = 25 16
· 49 = 25
36
≈ 0.694. After one iteration, the marked state’s
4
probability is significantly amplified, demonstrating Grover’s amplification process.

2 Shor’s Quantum Factoring Algorithm: A Beginner’s

Guide
These notes provide a detailed, beginner-friendly explanation of Shor’s Quantum Factoring
Algorithm, a quantum algorithm that efficiently factors large integers, offering an exponential

Department of Mathematics 6 RV College of Engineering

 2 SHOR’S QUANTUM FACTORING ALGORITHM: A BEGINNER’S GUIDE

speedup over the best classical algorithms. We will cover its purpose, classical preliminar-
ies, quantum components, and a step-by-step example, with all mathematical derivations
explained clearly.

1. What is Shor’s Algorithm?

Shor’s Algorithm, developed by Peter Shor in 1994, is a quantum algorithm that solves
the integer factorization problem: given a composite number N , find its prime factors. For
example, if N = 15, the factors are 3 and 5. Classically, the best algorithms (like the General
Number Field Sieve) take time exponential in the number of digits of N , making factoring
large numbers (e.g., 2048-bit numbers used in RSA encryption) impractical. Shor’s algorithm
runs in polynomial time, roughly O((log N )3 ), which is a game-changer for cryptography.
The algorithm combines classical number theory with quantum computing, using the Quan-
tum Fourier Transform (QFT) to find the period of a function, which leads to the factors of
N.

Circuit

Figure 3: Shor’s Algorithm

2. The Problem Setup

We want to factor a composite number N , assumed to be odd and not a prime power (e.g.,
N = 15). The idea is to reduce factorization to finding the period of a function, then use
quantum computing to find that period efficiently.
Shor’s algorithm starts with a classical step: reduce factorization to period finding. 1. Pick a
random integer a < N such that gcd(a, N ) = 1 (i.e., a and N are coprime). If gcd(a, N ) ̸= 1,
we’ve already found a factor (e.g., for N = 15, a = 6, gcd(6, 15) = 3, so 3 is a factor). 2.

Department of Mathematics 7 RV College of Engineering

 2 SHOR’S QUANTUM FACTORING ALGORITHM: A BEGINNER’S GUIDE

Define the function f (x) = ax mod N . This function is periodic: there exists a smallest
integer r (called the period or order) such that ar ≡ 1 mod N . 3. If r is even, compute ar/2
mod N . If ar/2 ̸≡ −1 mod N , then gcd(ar/2 − 1, N ) and gcd(ar/2 + 1, N ) are non-trivial
factors of N .
For example, if N = 15, a = 2: - Compute f (x) = 2x mod 15: f (0) = 1, f (1) = 2, f (2) = 4,
f (3) = 8, f (4) = 1, so the period r = 4. - Since r = 4 is even, compute ar/2 = 22 = 4. -
Check: 4 ̸≡ −1 mod 15. - Compute gcd(ar/2 − 1, N ) = gcd(4 − 1, 15) = gcd(3, 15) = 3, and
gcd(ar/2 + 1, N ) = gcd(4 + 1, 15) = gcd(5, 15) = 5. - The factors of 15 are 3 and 5!
The hard part is finding r. Classically, this takes exponential time, but Shor’s algorithm
uses a quantum computer to find r in polynomial time.

3. Quantum Part: Overview

Shor’s algorithm uses a quantum computer to find the period r of f (x) = ax mod N . The
steps are: 1. Prepare two quantum registers: - First register: n qubits to store x, where
n ≈ 2 log2 N to ensure accuracy. - Second register: ⌈log2 N ⌉ qubits to store f (x). 2. Create
a superposition of all x values in the first register. 3. Compute f (x) in the second register
using an oracle. 4. Apply the Quantum Fourier Transform (QFT) to the first register to
extract the period r. 5. Use classical post-processing to deduce r and find the factors.

4. Steps
We need n qubits for the first register, where N 2 ≤ 2n < 2N 2 (so n ≈ 2 log2 N ). For
N = 15, N 2 = 225, so choose n = 8 (since 28 = 256 ≥ 225). The second register needs
m = ⌈log2 15⌉ = 4 qubits to store numbers up to 15.
Start with both registers at zero:

|0⟩⊗n |0⟩⊗m = |0⟩⊗8 |0⟩⊗4 .

Apply Hadamard gates to the first register:

n −1
⊗n ⊗n 1 2X
H |0⟩ =√ n |x⟩.
2 x=0

For n = 8, 2n = 256, so the state is:

255
1 X
√ |x⟩|0⟩.
256 x=0

The oracle computes f (x) = ax mod N in the second register:

|x⟩|0⟩ → |x⟩|f (x)⟩.

Department of Mathematics 8 RV College of Engineering

 2 SHOR’S QUANTUM FACTORING ALGORITHM: A BEGINNER’S GUIDE

For a = 2, N = 15, the state becomes:

255
1 X
√ |x⟩|2x mod 15⟩.
256 x=0

Since f (x) has period r = 4, the values of 2x mod 15 repeat: 1, 2, 4, 8, 1, 2, ..., every 4
steps.
Apply the QFT to the first register. The QFT transforms |x⟩ into:
n −1
1 2X n
QFT|x⟩ = √ n e2πixy/2 |y⟩.
2 y=0

So the state becomes:

 
255 255
1 X 1 X
√ √ e2πixy/256 |y⟩ |2x mod 15⟩.
256 x=0 256 y=0

Swap the sums:

255 X
255
!
1 X
e2πixy/256 |x⟩|2x mod 15⟩ .
256 y=0 x=0
Group terms by the value of f (x). Since f (x) has period 4, let’s write x = qr + k, where q
is the quotient (0 ≤ q < 256/r), and k is the remainder (0 ≤ k < r). For r = 4, there are 64
full periods (256/4 = 64). So:
255 3 X
63
e2πixy/256 |x⟩|f (x)⟩ = e2πi(q·4+k)y/256 |q · 4 + k⟩|f (k)⟩.
X X

x=0 k=0 q=0

The exponent: (q · 4 + k)y/256 = q · 4y/256 + ky/256. The inner sum over q:

63 63
e2πiq(4y/256) = e2πiq(y/64) .
X X

q=0 q=0

This sum is large when y/64 is an integer, i.e., y = 64ℓ for ℓ = 0, 1, 2, 3 (since 256/4 = 64).
Otherwise, it cancels out (geometric series). The state has large amplitudes when y = 64ℓ,
so measuring the first register yields y = 0, 64, 128, 192.
Each y = 64ℓ corresponds to a fraction of the period: y/2n = ℓ/r. So:
y ℓ 64ℓ ℓ
= =⇒ = .
256 r 256 4
This suggests r = 4, which we already knew, but in general, we use the continued fraction
algorithm to find ℓ/r. For y = 64, 64/256 = 1/4, so ℓ = 1, r = 4.
Now that we have r = 4: - r is even, so r/2 = 2. - Compute ar/2 = 22 = 4. - Check: 4 ̸≡ −1
mod 15. - Compute factors: gcd(4 − 1, 15) = gcd(3, 15) = 3, gcd(4 + 1, 15) = gcd(5, 15) = 5.
- Factors of 15 are 3 and 5.

Department of Mathematics 9 RV College of Engineering

 2 SHOR’S QUANTUM FACTORING ALGORITHM: A BEGINNER’S GUIDE

5. Why Does It Work?

The QFT extracts the period because f (x) = ax mod N is periodic, and the QFT converts
periodicity in the input (x) into peaks in the output (y). The peaks occur at multiples of
2n /r, allowing us to deduce r.

6. Complexity and Speedup

1/3 2/3
- Classical factoring (e.g., General Number Field Sieve): O(ec(log N ) (log log N ) ), sub-exponential.
- Shor’s algorithm: O((log N )3 ), polynomial time, an exponential speedup. - Quantum part:
The QFT takes O((log N )2 ) gates, and we repeat a few times for high probability.

7. Limitations
- Quantum Hardware: Requires a fault-tolerant quantum computer, which doesn’t yet exist
at scale (as of May 2025).
- Error Correction: Noise in current quantum computers can affect the QFT and oracle.
- Applicability: Works best for numbers like N = pq (two prime factors), less efficient if N
has many small factors.

Question
Describe the role of the Quantum Fourier Transform (QFT) in Shor’s Quantum Factoring
Algorithm. For factoring N = 15, consider the period-finding step for a = 2. If the QFT
output state for a 3-qubit register is |010⟩, estimate the period r using continued fractions.

Solution
Shor’s Quantum Factoring Algorithm factors a composite number N in polynomial time by
finding the period r of the function f (x) = ax mod N , where a is coprime with N . The
QFT is used in the period-finding subroutine to extract r. For a t-qubit register, QFT maps
P t −1 2πijk/2t
|j⟩ to √12t 2k=0 e |k⟩, revealing multiples of 2t /r.
For N = 15, a = 2, compute f (x) = 2x mod 15: - x = 0: 20 = 1, - x = 1: 21 = 2, -
x = 2: 22 = 4, - x = 3: 23 = 8, - x = 4: 24 = 16 ≡ 1 mod 15. Period r = 4. For a
3-qubit register (t = 3), 2t = 8. The period-finding circuit produces a state with peaks at
k ≈ m · 2t /r = m · 8/4 = 2m. Possible measurements include |010⟩ = |2⟩.
Estimate ϕ = k/2t = 2/8 = 1/4. Use continued fractions to find ϕ = s/r: - 1/4 = 0 + 41 ,
continued fraction: [0; 4]. - Convergent: 14 , so s = 1, r = 4. Verify: 24 = 16 ≡ 1 mod 15,
and r = 4 is correct. The QFT enables efficient period extraction, allowing Shor’s algorithm
to factor N = 15 by computing gcd(ar/2 ± 1, N ), e.g., gcd(22 − 1, 15) = gcd(3, 15) = 3.

Department of Mathematics 10 RV College of Engineering

 3 HARROW-HASSIDIM-LLOYD (HHL) ALGORITHM

3 Harrow-Hassidim-Lloyd (HHL) Algorithm

These notes provide a detailed, beginner-friendly explanation of the Harrow-Hassidim-Lloyd
(HHL) algorithm, a quantum algorithm for solving linear systems of equations. We will
cover its purpose, mathematical setup, quantum components, a step-by-step breakdown,
and a simple example,

1. What is the HHL Algorithm?

The HHL algorithm, developed by Aram Harrow, Avinatan Hassidim, and Seth Lloyd in
2009, is a quantum algorithm that solves linear systems of equations Ax = b, where A is an
N × N Hermitian matrix, b is a known vector, and x is the unknown vector we want to find.
Classically, solving this takes O(N 3 ) operations using methods like Gaussian elimination.
The HHL algorithm offers an exponential speedup, solving it in O(log N · poly(1/ϵ)) time,
where ϵ is the desired precision, provided A is well-conditioned (i.e., its condition number
κ = |λmax /λmin | is not too large, where λmax and λmin are the largest and smallest eigenvalues
of A).
This algorithm has applications in fields like machine learning, physics simulations, and
optimization, but it requires a quantum computer and specific conditions on A.

2. Problem Setup
We need to solve:
Ax = b,
where: - A is an N × N Hermitian matrix (i.e., A = A† , meaning A’s conjugate transpose
equals itself). - b is a known N -dimensional vector. - x is the N -dimensional vector we want
to find.
Example Setup For simplicity, let’s consider a 2x2 system (N = 2):
" # " #
2 1 1
A= , b= .
1 2 0
" #
x
We want to find x = 1 .
x2
First, verify A is Hermitian:
" #† " #
† 2 1 2 1
A = = = A.
1 2 1 2

Next, compute the eigenvalues of A:

" #
2−λ 1
det(A − λI) = det = (2 − λ)2 − 1 = λ2 − 4λ + 3 = 0.
1 2−λ

Department of Mathematics 11 RV College of Engineering

 3 HARROW-HASSIDIM-LLOYD (HHL) ALGORITHM

Solve the quadratic equation:

√
4 ± 16 − 12 4±2
λ= = =⇒ λ1 = 3, λ2 = 1.
2 2
" # " #
−1 1 1
The eigenvectors are: - For λ1 = 3: A−3I = , so the eigenvector is , normalized
1 −1 1
" # " # " # " #
1 1 1 1 1 1 1
to √2 . - For λ2 = 1: A − I = , so the eigenvector is , normalized to √2 .
1 1 1 −1 −1
λmax 3
The condition number is κ = λmin
= 1
= 3, which is reasonable.

3. How HHL Works

The HHL algorithm uses quantum computing to solve the system by: 1. Encoding b as a
quantum state |b⟩. 2. Using quantum phase estimation (QPE) to extract the eigenvalues of
A. 3. Performing controlled rotations to encode the inverse eigenvalues into an ancilla qubit.
4. Uncomputing auxiliary states to produce a state proportional to A−1 |b⟩, which represents
|x⟩.
The output is a quantum state |x⟩, and measuring it gives the components of x, up to a
normalization factor.

4. Mathematical Steps of the HHL Algorithm

We’ll use three registers: - Register 1: t qubits for phase estimation, where 2t ≥ κ/ϵ. -
Register 2: n = log2 N qubits to store the state (for N = 2, n = 1). - Register 3: 1 ancilla
qubit for controlled rotations.
For our example, κ = 3, let’s choose ϵ = 0.1, so 2t ≥ 3/0.1 = 30, thus t = 5 (since 25 = 32).
" #
1
Step 1: Prepare the Input State |b⟩ Express b = in the eigenbasis of A:
0
N
X
|b⟩ = βj |uj ⟩,
j=1
" #
√1
1
where |uj ⟩ are the eigenvectors of A, and βj = ⟨uj |b⟩. - |u1 ⟩ = , β1 = ⟨u1 |b⟩ =
2 1
" #
√1 (1 √1 . √1
1 √1 (1 √1 .
· 1 + 1 · 0) = - |u2 ⟩ = , β2 = ⟨u2 |b⟩ = · 1 + (−1) · 0) =
2 2 2 −1 2 2

So:
1 1
|b⟩ = √ |u1 ⟩ + √ |u2 ⟩.
2 2
" # " #
1 0
In the computational basis (|0⟩ = , |1⟩ = ):
0 1
1 1
|u1 ⟩ = √ (|0⟩ + |1⟩), |u2 ⟩ = √ (|0⟩ − |1⟩),
2 2

Department of Mathematics 12 RV College of Engineering

 3 HARROW-HASSIDIM-LLOYD (HHL) ALGORITHM

! !
1 |0⟩ + |1⟩ 1 |0⟩ − |1⟩ 1
|b⟩ = √ √ +√ √ = (|0⟩ + |1⟩ + |0⟩ − |1⟩) = |0⟩.
2 2 2 2 2
The initial state is:
|0⟩⊗t |b⟩|0⟩ = |0⟩⊗5 |0⟩|0⟩.

Step 2: Quantum Phase Estimation (QPE) Apply QPE with the unitary U = eiAt0 , where t0
scales the eigenvalues to [0, 1). Since A = j λj |uj ⟩⟨uj |, we have U |uj ⟩ = eiλj t0 |uj ⟩. Choose
P

t0 = 2π/λmax = 2π/3, so λj t0 ∈ [0, 2π).

QPE estimates λj t0 /2π, so the first register stores λ̃j ≈ λj . The state becomes:
N
X
βj |λ̃j ⟩|uj ⟩|0⟩.
j=1

For our example: - λ1 = 3, λ̃1 ≈ 3 · 2π · 1 = 1, but in binary with t = 5 bits, λ̃1 ≈ 1 · 25 = 32.
3 2π
- λ2 = 1, λ̃2 ≈ 1 · 2π
3
1
· 2π = 13 , so λ̃2 ≈ 31 · 25 ≈ 10.67 ≈ 11.
The state is approximately:
1 1
√ |32⟩|u1 ⟩|0⟩ + √ |11⟩|u2 ⟩|0⟩.
2 2

Step 3: Controlled Rotation Apply a controlled rotation on the ancilla qubit, conditioned
on the first register. If the first register is |λ̃j ⟩, rotate the ancilla to:

C
|0⟩ + |1⟩,
λ̃j

where C is a normalization constant (choose C = 1/κ = 1/3). The state becomes:

N
!
X C
βj |λ̃j ⟩|uj ⟩ |0⟩ + |1⟩ .
j=1 λ̃j

1/3
For our example: - For j = 1, λ̃1 = 32, ancilla is |0⟩ + 32
|1⟩. - For j = 2, λ̃2 = 11, ancilla is
|0⟩ + 1/3
11
|1⟩.
Step 4: Uncompute with Inverse QPE Apply the inverse QPE to uncompute the first register,
leaving the second register in a state proportional to j βj λCj |uj ⟩, which is proportional to
P

|x⟩ = A−1 |b⟩. The final state, when the ancilla is |1⟩, is:
N
X 1
C βj |uj ⟩.
j=1 λj
√ √
β1 1/ 2 1 √1 (|0⟩ β2 1/ 2 √1 ,
Compute: - j = 1: λ1
= 3
= √
3 2
, |u1 ⟩ = 2
+ |1⟩). - j = 2: λ2
= 1
= 2
|u2 ⟩ = √12 (|0⟩ − |1⟩).

Department of Mathematics 13 RV College of Engineering

 3 HARROW-HASSIDIM-LLOYD (HHL) ALGORITHM

1 1 1 1 1 1 2 1
|x⟩ ∝ √ · √ (|0⟩ + |1⟩) + √ · √ (|0⟩ − |1⟩) = (|0⟩ + |1⟩) + (|0⟩ − |1⟩) = |0⟩ − |1⟩.
3 2 2 2 2 6 2 3 3
√
r 
2  2 q
2
Normalize: Norm = 3
+ − 13 = 5
9
= 3
5
, so:
" #
1 2
|x⟩ = √ .
5 −1

Step 5: Verify the Solution Check A|x⟩ = b:

" # " # " # " #
2 1 1 2 1 4−1 1 3
A|x⟩ = √ =√ =√ .
1 2 5 −1 5 2−2 5 0
" #
1
This is proportional to b = , confirming the solution (the HHL algorithm outputs a
0
normalized state).

5. Why Does It Work?

The HHL algorithm works because: - QPE extracts the eigenvalues of A, allowing us to
compute A−1 in the eigenbasis. - Controlled rotations encode 1/λj , effectively applying A−1 .
- The quantum state |x⟩ encodes the solution vector, which can be measured to obtain x.

6. Complexity and Speedup

- Classical methods: O(N 3 ) for Gaussian elimination. - HHL: O(log N · κ · poly(1/ϵ)),
exponential speedup if κ is small. - Caveat: The output is a quantum state, not a classical
vector, so extracting all components requires O(N ) measurements.

7. Limitations
- Matrix Conditions: A must be Hermitian and well-conditioned.
- Quantum Hardware: Requires a fault-tolerant quantum computer (not yet available at
scale as of May 2025).
- Output: Gives a quantum state |x⟩, not x, so it’s best for tasks like computing expectation
values ⟨x|M |x⟩.

Question
Outline
" the # HHL"Algorithm
# for solving a linear system Ax = b. For a 2x2 system with
2 1 1
A= ,b= , and 1-qubit register for phase estimation, compute the eigenvalues of
1 2 0
A (assuming Hermitian) and describe how phase estimation contributes to solving for x.

Department of Mathematics 14 RV College of Engineering

 3 HARROW-HASSIDIM-LLOYD (HHL) ALGORITHM

Solution
The HHL Algorithm solves Ax = b for a Hermitian matrix A using quantum phase estima-
tion and controlled rotations, achieving exponential speedup for sparse systems. It encodes
b as |b⟩, uses phase estimation to approximate A−1 , and outputs |x⟩ ∝ A−1 |b⟩.
" # " #
2 1 1
Given A = ,b= . Verify A is Hermitian: A† = A. Compute eigenvalues:
1 2 0
" #
2−λ 1
det(A − λI) = det = (2 − λ)2 − 1 = λ2 − 4λ + 3 = 0.
1 2−λ
" #" #
√ −1 1 x
4± 16−12 4±2
Solve: λ = = ,
so λ1 = 3, λ2 = 1. Eigenvectors: - For λ = 3: =
2 2 1 −1 y
" # " #" #
1 1 1 x
0 =⇒ x = y, so |u1 ⟩ = √12 . - For λ = 1: = 0 =⇒ x = −y, so
1 1 1 y
" #
1
|u2 ⟩ = √12 .
−1
" #
1
Express |b⟩ = = 2j=1 bj |uj ⟩:
P
0
" # " # " # " #
1 1 1 1 1 b1 + b2 1
|b⟩ = b1 √ + b2 √ =√ = .
2 1 2 −1 b
2 1 − b 2 0
√ √
2
√
2
√
2
Solve: b1 + b2 = 2, b1 − b2 = 0 =⇒ b1 = b2 = 2
. Thus, |b⟩ = 2
|u1 ⟩ + 2
|u2 ⟩.
Phase estimation approximates eigenvalues λj . For a 1-qubit register, apply controlled-eiAt .
Since A = 3|u1 ⟩⟨u1 | + 1|u2 ⟩⟨u2 |, eiAt |uj ⟩ = eiλj t |uj ⟩. The phase for λj is ϕj = λj t/2π. With 1
qubit, precision is limited, but ideally, phases encode λ1 = 3, λ2 = 1. After phase estimation,
the state is:
2
X
bj |λ̃j ⟩|uj ⟩,
j=1

C
where |λ̃j ⟩ approximates λj . Controlled rotation applies λj
to an ancilla, yielding:

2
√ √
X bj 2 1 2 1
|x⟩ ∝ |uj ⟩ = · |u1 ⟩ + · |u2 ⟩.
j=1 λj 2 3 2 1

This approximates A−1 |b⟩, solving the system. Phase estimation is critical for extracting λj ,
enabling the inversion.

Department of Mathematics 15 RV College of Engineering