Unit 5: Applications of Quantum Computing

Dr. Venugopal K.

June 26, 2025

1 Order Finding Problem

Input: An integer N ≥ 2, and an element a ∈ Z∗N such that gcd(a, N ) = 1.
Output: The order r of a modulo N , i.e., the smallest positive integer r such that

ar ≡ 1 mod N.

1.1 Mathematical Background

• ZN = {0, 1, . . . , N − 1}
• Z∗N = {a ∈ ZN | gcd(a, N ) = 1}
• Z∗N forms a group under multiplication modulo N .
• Euler’s totient function φ(N ) = |Z∗N | counts the number of integers in ZN that are
coprime to N .
Euler’s Theorem:
aφ(N ) ≡ 1 mod N for all a ∈ Z∗N .
This implies the order r of a must divide φ(N ).
Example: Let a = 4, N = 35. Then,

41 ≡ 4 mod 35
42 ≡ 16 mod 35
43 ≡ 29 mod 35
44 ≡ 11 mod 35
45 ≡ 9 mod 35
46 ≡ 1 mod 35

Hence, the order of 4 modulo 35 is r = 6.

1
1.2 Quantum Approach: Phase Estimation 1 ORDER FINDING PROBLEM

3. Modular Exponentiation Circuit

We implement U j |x⟩ = |aj x mod N ⟩ using repeated squaring:
• Express x ∈ ZN in binary: x = x0 + 2x1 + · · · + 2n−1 xn−1 .
• Compute a2 mod N classically and store in lookup.
i

• Use controlled multipliers for each i, where the control is the i-th bit of the exponent:
Each controlled gate performs modular multiplication conditioned on the respective bit of
the exponent.

1.2 Quantum Approach: Phase Estimation

To find the order r, we define a unitary operator M acting on a Hilbert space of dimension
N:

M |x⟩ = |a · x mod N ⟩ , for x ∈ ZN .

Let ωr = e2πi/r . For k ∈ {0, . . . , r − 1}, define the state:

1 r−1
|ψk ⟩ = √ ω kj |aj ⟩ .
X
r j=0 r

Then, |ψk ⟩ is an eigenvector of M with eigenvalue ωrk :

M |ψk ⟩ = ωrk |ψk ⟩ .

Using Phase Estimation

Apply the quantum phase estimation algorithm to estimate the phase θ = k
r
for a randomly
chosen k ∈ {0, . . . , r − 1}. The algorithm gives an estimate 2jn such that:

j k 1
− < .
2n r 2n+1

1.3 Classical Post-Processing: Continued Fractions

Given an estimate α ≈ kr and a known bound N , use the continued fractions algorithm to
find a rational approximation xy such that:

x 1
α− < .
y 2N

With high probability, y will be the order r or a divisor of it. Repeat the process several
times and take lcm(y1 , y2 , . . . ) to find r.

Department of Mathematics 2 RV College of Engineering

1.4 Complexity 2 DISCRETE LOGARITHM PROBLEM (DLP)

1.4 Complexity
• The quantum part runs in time polynomial in log N .
• The classical post-processing (continued fractions) runs in time O(log N ).

1.5 Connection to Factoring

Order finding is the core subroutine in Shor’s algorithm for integer factorization. Once the
order r of a modulo N is found, it can be used to find nontrivial factors of N with high
probability.

Basic Group Theory

Let:
• Z∗N = {a ∈ ZN | gcd(a, N ) = 1}.
• Euler’s totient function φ(N ) = |Z∗N |.
• Euler’s theorem: aφ(N ) ≡ 1 mod N for all a ∈ Z∗N .
Example: For a = 4, N = 35, we find:

46 ≡ 1 mod 35 ⇒ r = 6.

1.6 Summary
• The order-finding problem is key to Shor’s factoring algorithm.
• It reduces to estimating eigenvalues of modular exponentiation operators.
• Modular exponentiation is done efficiently using controlled multipliers.
• The final result is post-processed classically using continued fractions.

2 Discrete Logarithm Problem (DLP)

The Discrete Logarithm Problem (DLP) is a fundamental problem in number theory
and cryptography. Given a cyclic group G, a generator g ∈ G, and an element h ∈ G, the
DLP is to find an integer x such that:

g x = h mod p,

where p is a prime number.

This problem is believed to be computationally hard for classical computers, particularly for
large primes, and is the basis for the security of several cryptographic protocols, including:
• Diffie–Hellman Key Exchange

Department of Mathematics 3 RV College of Engineering

2.1 Quantum Approach using Shor’s Algorithm
2 DISCRETE LOGARITHM PROBLEM (DLP)

• ElGamal Encryption
• DSA (Digital Signature Algorithm)

2.1 Quantum Approach using Shor’s Algorithm

Quantum computing offers a polynomial-time solution to the DLP using Shor’s algorithm,
which can efficiently solve both:
• Integer factorization
• Discrete logarithm problems
The key idea is that the discrete logarithm problem can be reduced to a problem of period-
finding, which quantum algorithms are well-suited for.

2.2 Steps of Quantum Discrete Logarithm Algorithm (for prime

fields)
Let p be a prime, g a generator of Z∗p , and h = g x mod p. The steps are:
1. Define a function f (a, b) = g a h−b mod p, which is constant on lines a − xb = constant.
2. Use a quantum computer to compute the Fourier transform over Zq × Zq , revealing
information about the line (i.e., the hidden period).
3. Extract the value of x using classical post-processing (e.g., continued fractions).
This allows computation of the discrete logarithm in polynomial time O((log p)3 ), compared
to sub-exponential time for classical methods like the number field sieve.

2.3 Example Problem

Problem: Let p = 23, g = 5, and h = 4. Find the discrete logarithm x such that:

5x ≡ 4 mod 23

Classical Solution (for comparison): Try successive powers of 5 modulo 23:

51 = 5 mod 23,
52 = 25 ≡ 2 mod 23,
53 = 10 mod 23,
54 = 50 ≡ 4 mod 23.

Thus, x = 4 is the solution.

Quantum Perspective: In a real quantum computer:
1. Prepare a superposition over all (a, b) in Z23 × Z23 .

Department of Mathematics 4 RV College of Engineering

2.4 Conclusion 3 QUANTUM COUNTING

2. Compute f (a, b) = 5a · 4−b mod 23.

3. Apply Quantum Fourier Transform to extract the periodicity in a−xb, revealing x = 4.
This illustrates how the discrete logarithm problem is efficiently solvable using quantum
algorithms, threatening the security of cryptographic systems that rely on DLP.

2.4 Conclusion
The discrete logarithm problem is classically hard and forms the basis of several widely-used
cryptosystems. Quantum computing, through Shor’s algorithm, provides a powerful method
to solve DLP efficiently. This breakthrough has profound implications for cybersecurity,
motivating the development of post-quantum cryptographic protocols.

3 Quantum Counting
What is the problem?
Given a Boolean function f : {0, 1}n → {0, 1}, we want to estimate the number of solutions
M such that f (x) = 1. That is, how many inputs x ∈ {0, 1}n satisfy the condition?
Classically, this would require O(2n ) evaluations. Quantum counting estimates M efficiently
using quantum phase estimation (QPE) applied to the Grover operator.

Relationship with Grover’s Algorithm

Grover’s algorithm amplifies the amplitudes of solution states using the Grover operator:
G = D · Uf
where:
• Uf flips the sign of solution states: Uf |x⟩ = (−1)f (x) |x⟩
• D = 2 |s⟩ ⟨s| − I is the diffusion operator with |s⟩ = √1 |x⟩
P
N x

The Grover operator G has eigenvalues e±2πiθ , where:

M
sin2 (πθ) =
N
By estimating θ using QPE, we can estimate M , the number of solutions.

Problem
Let f : {0, 1, 2, 3} → {0, 1} be a Boolean function defined on 2-bit inputs such that:
f (0) = 1, f (1) = 0, f (2) = 1, f (3) = 0

So the solutions are x = 0 and x = 2, hence M = 2, and N = 4. We will apply Quantum

Counting to estimate M .

Department of Mathematics 5 RV College of Engineering

 3 QUANTUM COUNTING

Step 1: Define Grover Operator

Start with the uniform superposition:
1
|s⟩ = (|0⟩ + |1⟩ + |2⟩ + |3⟩)
2

The oracle Uf flips signs of |0⟩ and |2⟩.

Grover operator:
G = D · Uf = (2 |s⟩ ⟨s| − I) · Uf

Step 2: Eigenvalues of G
Grover operator acts on a 2D subspace spanned by:
1 1
|ψgood ⟩ = √ (|0⟩ + |2⟩), |ψbad ⟩ = √ (|1⟩ + |3⟩)
2 2

Let:
M 2 1 π 1
sin2 (πθ) = = = ⇒ πθ = ⇒ θ =
N 4 2 4 4
πi
Then the eigenvalues of G are e±2πi·θ = e± 2 = ±i

Step 3: Apply Quantum Phase Estimation

Use QPE to estimate the phase θ corresponding to the eigenvalue of G. Suppose we obtain
θ ≈ 0.25 as the output.

Step 4: Estimate M
Compute:
√ !2
π 2 1
 
M ≈ N · sin (πθ) = 4 · sin
2 2
=4· =4· =2
4 2 2

So we correctly estimate that there are 2 solutions.

Remarks
• Quantum counting does not find the solutions; it estimates how many exist.
• The algorithm is efficient: requires only O(1) calls to the Grover operator to estimate
M within desired precision.
• This method generalizes Grover’s algorithm and is useful in problems where counting
is more important than searching.

Department of Mathematics 6 RV College of Engineering

 4 BOOLEAN SATISFIABILITY PROBLEM (SAT)

4 Boolean satisfiability problem (SAT)

Introduction to the Boolean Satisfiability Problem
The Boolean Satisfiability Problem (SAT) is a fundamental problem in computer sci-
ence and logic. It asks whether there exists an assignment of Boolean variables that makes
a given Boolean formula evaluate to true.
A Boolean formula is typically expressed in conjunctive normal form (CNF), which is a
conjunction (AND) of one or more clauses, where each clause is a disjunction (OR) of literals
(variables or their negations).

Definition: SAT Problem

Given a Boolean formula Φ(x1 , x2 , . . . , xn ), determine whether there exists an assignment of
truth values to the variables xi ∈ {0, 1} such that Φ evaluates to true.

2-SAT Problem
A special case of SAT is the 2-SAT problem, where each clause in the CNF formula
contains exactly two literals. Although general SAT is NP-complete, the 2-SAT problem can
be solved in polynomial time.

Example
Consider the formula:
Φ(x1 , x2 ) = (¬x1 ∨ x2 ) ∧ (¬x2 )

This formula consists of two clauses:

• (¬x1 ∨ x2 ): satisfied if either x1 = 0 or x2 = 1
• (¬x2 ): satisfied only if x2 = 0
We now analyze all possible assignments to x1 , x2 ∈ {0, 1}:
Assignment Clause 1 Clause 2
x1 = 0, x2 = 0 1 ∨ 0 = 1 ¬0 = 1
x1 = 0, x2 = 1 1 ∨ 1 = 1 ¬1 = 0
x1 = 1, x2 = 0 0 ∨ 0 = 0 ¬0 = 1
x1 = 1, x2 = 1 0 ∨ 1 = 1 ¬1 = 0
Only the assignment x1 = 0, x2 = 0 satisfies both clauses, so the formula is satisfiable.
This section applies Grover’s algorithm to a 2-SAT Boolean formula to demonstrate its
ability to identify a satisfying assignment efficiently.

Department of Mathematics 7 RV College of Engineering

 4 BOOLEAN SATISFIABILITY PROBLEM (SAT)

Question 1
Consider the 2-SAT formula:

Φ′ (x1 , x2 ) = (¬x1 ∨ x2 ) ∧ (¬x2 )

Answer the following:

1. List all possible assignments |00⟩ , |01⟩ , |10⟩ , |11⟩ and identify which assignments satisfy
Φ′ .
2. Construct the oracle matrix Uf that flips the sign of satisfying states.
3. Grover Iteration: Starting with the uniform superposition state |s⟩ = H ⊗2 |00⟩, apply
the oracle Uf , then apply the diffusion operator

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

Write down the final state after one Grover iteration.

4. Calculate the probability of measuring a satisfying state:
(a) Before Grover iteration.
(b) After one Grover iteration.

Solution
(i) Satisfying Assignments
We evaluate Φ′ (x1 , x2 ) = (¬x1 ∨ x2 ) ∧ (¬x2 ) for all 4 possible inputs:
x1 x2 (¬x1 ∨ x2 ) Φ′ (x1 , x2 )
0 0 1 1
0 1 1 0
1 0 0 0
1 1 1 0
Only the assignment |00⟩ satisfies the formula.

(ii) Oracle Matrix Uf

Oracle Uf flips the phase of satisfying states:

−1 0 0 0
 
 0 1 0 0
Uf = I − 2 |00⟩ ⟨00| = 
 
 0 0 1 0


0 0 0 1

Department of Mathematics 8 RV College of Engineering

 4 BOOLEAN SATISFIABILITY PROBLEM (SAT)

(iii) One Grover Iteration

Start with the uniform superposition:

1
|s⟩ = H ⊗2 |00⟩ = (|00⟩ + |01⟩ + |10⟩ + |11⟩)
2

Step 1: Apply Oracle Uf

1
Uf |s⟩ = (− |00⟩ + |01⟩ + |10⟩ + |11⟩)
2

Step 2: Apply Diffusion Operator

D = 2 |s⟩ ⟨s| − I

Let |ψ⟩ = Uf |s⟩. First compute the overlap:

1 1 1
⟨s|ψ⟩ = · (−1 + 1 + 1 + 1) =
2 2 2
Apply diffusion:
1
D |ψ⟩ = 2 · · |s⟩ − |ψ⟩ = |s⟩ − |ψ⟩
2

1 1
⇒ D |ψ⟩ = (|00⟩ + |01⟩ + |10⟩ + |11⟩) − (− |00⟩ + |01⟩ + |10⟩ + |11⟩) = |00⟩
2 2
Final state after one Grover iteration:

|00⟩

(iv) Probability of Satisfying State

(a) Before Grover Iteration:

1 2
1
P (|00⟩) = =
2 4

(b) After One Grover Iteration:

P (|00⟩) = 1

Conclusion
Grover’s algorithm successfully finds the satisfying assignment of the 2-SAT formula by am-
plifying its amplitude from 25% to 100% in a single iteration. This illustrates its effectiveness
for small-scale decision problems with known Boolean structure.

Department of Mathematics 9 RV College of Engineering

 4 BOOLEAN SATISFIABILITY PROBLEM (SAT)

Question 2
Explain how Grover’s algorithm can be applied to solve the Boolean satisfiability problem
(SAT). For a 2-variable 2-clause SAT problem (x1 ∨ ¬x2 ) ∧ (¬x1 ∨ x2 ), construct the or-
acle matrix Uf for the satisfying assignment, apply one Grover iteration to the uniform
superposition state, and compute the probability of measuring a satisfying assignment.

Solution
Grover’s algorithm solves the Boolean satisfiability problem (SAT) by searching for assign-
ments that satisfy a Boolean formula in conjunctive normal form. For a k-SAT problem, the
oracle
q
Uf marks satisfying assignments, and Grover’s iterations amplify their amplitudes in
O( 2n /M ) steps, where n is the number of variables and M is the number of solutions.
Consider the 2-SAT problem (x1 ∨ ¬x2 ) ∧ (¬x1 ∨ x2 ). Evaluate: - x1 = 0, x2 = 0: (0 ∨ 1) ∧
(1 ∨ 0) = 1, satisfies. - x1 = 0, x2 = 1: (0 ∨ 0) ∧ (1 ∨ 1) = 0, does not satisfy. - x1 = 1, x2 = 0:
(1 ∨ 1) ∧ (0 ∨ 0) = 0, does not satisfy. - x1 = 1, x2 = 1: (1 ∨ 0) ∧ (0 ∨ 1) = 1, satisfies.
Solutions: |00⟩, |11⟩ (M = 2).
Oracle: Uf |x⟩ = (−1)f (x) |x⟩, where f (x) = 1 if x = 00 or 11. Matrix:
1 0 0 0 1 0 0 0 −1 0 0 0
     
0 1 0 0 0 0 0 0  0 1 0 0
   
Uf = I − 2(|00⟩⟨00| + |11⟩⟨11|) =   − 2 = .

0 0 1 0 0 0 0 0  0 0 1 0


0 0 0 1 0 0 0 1 0 0 0 −1
Start with |s⟩ = H ⊗2 |00⟩ = 12 (|00⟩ + |01⟩ + |10⟩ + |11⟩). Apply Uf :
1
Uf |s⟩ = (−|00⟩ + |01⟩ + |10⟩ − |11⟩).
2
−1 1 1 1
 
 1 −1 1 1
Diffusion operator: 2|s⟩⟨s| − I = 21  . Apply:
 
 1 1 −1 1 
1 1 1 −1
−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⟩+3|1
2 4 1 1 −1 1   1  4 −1 4


1 1 1 −1 −1 3
Probability of satisfying assignments (|00⟩, |11⟩):
32 32 9 9 18 9
P = + = + = = .
4 4 16 16 16 8
Normalize: ⟨ψ|ψ⟩ = 16 (3 + (−1) + (−1) + 3 ) =
1 2 2 2 2 9+1+1+9
16
= 16 = 54 . Actual probability:
20

9
9 4 36 9
P = 8
= · = = = 0.9.
5
4
8 5 40 10
One iteration amplifies the probability of measuring |00⟩ or |11⟩, solving the SAT problem
efficiently.

Department of Mathematics 10 RV College of Engineering

 5 QUANTUM REPRESENTATION OF GRAPHS

5 Quantum Representation of Graphs

Quantum computing provides novel ways to represent and analyze classical data structures,
including graphs. A simple undirected graph can be encoded using quantum states by
associating vertices with computational basis states and edges with tensor products of these
basis states.
For a graph with vertex set V = {0, 1, 2}, each edge (i, j) can be represented as a 2-qubit
basis state |ij⟩ = |i⟩⊗|j⟩. A superposition of such edge states can then be used as a quantum
encoding of the graph’s structure.
This document analyzes a 3-vertex complete graph (triangle) and performs basic quantum
operations and measurements on its quantum representation.

Problem Statement
Given a 3-vertex undirected graph (triangle) with edges:

(0, 1), (1, 2), (0, 2)

The adjacency matrix is:

0 1 1
 

A = 1 0 1
 

1 1 0

Each edge (i, j) is represented by a 2-qubit state |ij⟩ = |i⟩ ⊗ |j⟩. The initial state is the
uniform superposition of the edges:

1
|ψ0 ⟩ = √ (|01⟩ + |12⟩ + |02⟩)
3

Answer the following:

1. Verify that |ψ0 ⟩ is normalized and confirm the number of edges.
2. Apply the Hadamard gate H to the first qubit of |ψ0 ⟩ and write the resulting state.
3. If the first qubit is measured after applying H, what are the possible outcomes and
their corresponding probabilities?
4. How do these measurement outcomes relate to the graph’s edges?

Department of Mathematics 11 RV College of Engineering

 5 QUANTUM REPRESENTATION OF GRAPHS

Solution
(a) Normalization and Number of Edges
The state is:
1
|ψ0 ⟩ = √ (|01⟩ + |12⟩ + |02⟩)
3

Check normalization:
!2
1 1
⟨ψ0 |ψ0 ⟩ = √ (⟨01|01⟩ + ⟨12|12⟩ + ⟨02|02⟩) = (1 + 1 + 1) = 1
3 3

So |ψ0 ⟩ is normalized.
Number of edges: 3 (since there are 3 terms in the superposition)

(b) Apply Hadamard Gate to First Qubit

Recall:
1 1
H |0⟩ = √ (|0⟩ + |1⟩), H |1⟩ = √ (|0⟩ − |1⟩)
2 2

Apply H ⊗ I to each term:

1 1
H ⊗ I |01⟩ = H |0⟩ ⊗ |1⟩ = √ (|0⟩ + |1⟩) ⊗ |1⟩ = √ (|01⟩ + |11⟩)
2 2
1 1
H ⊗ I |12⟩ = H |1⟩ ⊗ |2⟩ = √ (|0⟩ − |1⟩) ⊗ |2⟩ = √ (|02⟩ − |12⟩)
2 2
1 1
H ⊗ I |02⟩ = H |0⟩ ⊗ |2⟩ = √ (|0⟩ + |1⟩) ⊗ |2⟩ = √ (|02⟩ + |12⟩)
2 2

Adding all contributions:

1 1 1 1
" #
|ψ ′ ⟩ = √ √ (|01⟩ + |11⟩) + √ (|02⟩ − |12⟩) + √ (|02⟩ + |12⟩)
3 2 2 2
1 1
= √ · √ (|01⟩ + |11⟩ + 2 |02⟩)
3 2

So the final state is:

1
|ψ ′ ⟩ = √ (|01⟩ + |11⟩ + 2 |02⟩)
6

Department of Mathematics 12 RV College of Engineering

 5 QUANTUM REPRESENTATION OF GRAPHS

(c) Measurement of First Qubit

We write |ψ ′ ⟩ in terms of first-qubit measurement:

1
|ψ ′ ⟩ = √ (|0⟩ ⊗ |1⟩ + |1⟩ ⊗ |1⟩ + 2 |0⟩ ⊗ |2⟩)
6

Group by first qubit:

• First qubit = 0: states |01⟩ , |02⟩, total amplitude: √1
6
|1⟩ + √2
6
|2⟩
Probability:
2 2
1 2 1 4 5
P (0) = √ + √ = + =
6 6 6 6 6

• First qubit = 1: state |11⟩, amplitude: √1

6

Probability:
2
1 1
P (1) = √ =
6 6

(d) Interpretation of Measurement Outcomes

The first qubit represents the starting vertex of an edge. Measuring it gives information
about which vertex the edge originates from:
• Measuring 0: The edge starts from vertex 0. High probability (5/6) indicates most
edges start at 0.
• Measuring 1: The edge starts from vertex 1. Lower probability (1/6) reflects fewer
edges from 1 in this superposition.
This illustrates how quantum measurement can reveal structural information (like degree or
connectivity) of a graph.

Department of Mathematics 13 RV College of Engineering