Horizon Tech.

Services

——————————–

Quantum Aproximation Optimization Algorithm

Author
Arslan Anwar

January 23, 2025

1 Introduction
Recently, Chinese researchers claimed to have cracked RSA, that is, they solved 48-bit RSA en-
cryption as an example. I started reading their paper to understand how they did it. In the
paper, the authors used the Quantum Approximate Optimization Algorithm (QAOA) and lattice
reduction to break down RSA. Then my mentor gave me the task of understanding QAOA and
seeing how it works.
Quantum computing has the potential to revolutionize the way complex problems are solved. This
technology is based on the principles of quantum mechanics, which helps us to find solutions to
problems that are extremely difficult or impossible for traditional computers. QAOA is an algo-
rithm specifically designed to solve problems that are called optimization problems in computer
science and engineering. This algorithm helps faster solutions using the power of quantum com-
puting.
QAOA is a quantum algorithm designed to solve computational problems, especially those that are
more difficult or complex, such as combinational optimization. The main purpose of this algorithm
is to find solutions to problems that are time-consuming or not possible for traditional computers.
The specialty of QAOA is that it works by combining quantum and classical computing, which
is called hybrid approach. This algorithm uses the principles of quantum mechanics, such as
superposition and interference. So that the best solution can be found quickly.
This is important because it can help us solve future problems that are difficult to solve with
today’s computers, such as network optimization, logistics, and cryptographic security challenges.
QAOA is a step that leads to using the power of quantum computing in practice.
This project will primarily focus on understanding the QAOA and how it works. As a starting
point, we will look at QAOA through the lens of the Max-Cut problem, which serves as an ideal
example to demonstrate the principles and applications of the algorithm.

2 Background
In this section we will describe the basic concepts that are required to understand QAOA. We
will first discuss the importance of optimization problems and their challenges, then review the
fundamentals of quantum computing, and finally introduce the Variational Quantum Algorithms
(VQAs) linking the two, which are the foundation of QAOA.

2.1 Optimization Problems

Optimization problems are a fundamental part of many real-world challenges. These problems
involve choosing the best solution from a range of possibilities while meeting certain conditions or
limitations. For example,

• A company might want to maximize its profits while minimizing costs.

• A city planner might need to design an efficient transportation system.
• In machine learning, algorithms often require optimization to improve their accuracy.

The difficulty arises as the size and complexity of these problems grow. Some optimization prob-
lems, especially combinatorial ones, can quickly become very hard to solve. The number of potential
solutions increases exponentially with the problem size, making it challenging to find the best one
within a reasonable time.
One well-known example is the Max-Cut problem, which asks how to divide the nodes of a graph
into two groups so that the number of edges between the groups is maximized. Solving this problem
exactly becomes increasingly time-consuming as the graph grows larger.
Quantum computing offers exciting possibilities for addressing such complex problems. With its
unique principles, quantum computing can potentially provide solutions faster or more efficiently
than classical methods. This makes it a powerful tool for tackling optimization challenges like the
Max-Cut problem.

2
2.2 Quantum Computing Basis
Quantum computing is a revolutionary approach to computation that leverages the principles of
quantum mechanics. Unlike classical computers, which use bits to represent data as 0s or 1s,
quantum computers use qubits. Qubits can exist in a state of 0, 1, or both simultaneously, a
property known as superposition.

2.2.1 Qubits and Superposition

A qubit (quantum bit) is the fundamental unit of quantum information. Unlike a classical bit that
can exist only in one of two states (0 or 1), a qubit can exist in a linear combination of both states
simultaneously. This property is called superposition. Mathematically, the state of a single qubit
can be represented as:
|ψ⟩ = α|0⟩ + β|1⟩
where:
   
1 0
• |0⟩ = and |1⟩ = are the basis states (like 0 and 1 in classical computing).
0 1
• α and β are complex numbers called amplitudes, which satisfy the normalization condition:
|α|2 + |β|2 = 1

This means the probabilities of measuring the qubit in state |0⟩ or |1⟩ are |α|2 and |β|2 , respectively.

Superposition Superposition allows the qubit to encode more information than a classical bit.
For example, a classical bit must be either 0 or 1, but a qubit can be |0⟩, |1⟩, or any weighted
combination of the two.

Example State: For a qubit in the state:

1 1
|ψ⟩ = √ |0⟩ + √ |1⟩
2 2
 2
• The probability of measuring |0⟩ is |α|2 = √1
2
= 12 .

• Similarly, the probability of measuring |1⟩ is 12 .

This is a balanced superposition of |0⟩ and |1⟩, which is a fundamental feature of quantum com-
puting.

2.2.2 Entanglement

Entanglement is a uniquely quantum phenomenon where two or more qubits become correlated
in such a way that the state of one qubit is dependent on the state of the other(s), regardless of
the physical distance between them. This property plays a crucial role in quantum computing and
quantum communication.
Mathematically, an entangled state cannot be expressed as the product of individual qubit states.
For example, consider two qubits in the entangled state:

1

|ψ⟩ = √ |00⟩ + |11⟩
2
Here:

• |00⟩ = |0⟩ ⊗ |0⟩ and |11⟩ = |1⟩ ⊗ |1⟩ are the basis states of two qubits.
• The state |ψ⟩ cannot be factored into separate states of the individual qubits, demonstrating
entanglement.

3
Non-Local Correlation When the qubits are measured:

• If the first qubit is measured to be |0⟩, the second qubit will instantaneously collapse to |0⟩.
• Similarly, if the first qubit is measured to be |1⟩, the second qubit will collapse to |1⟩.

This correlation exists even if the qubits are separated by large distances.

Example: Bell State The state |ψ⟩ = √12 |00⟩ + |11⟩ is one of the four maximally entangled

Bell states. It illustrates the perfect correlation between the two qubits, making it a cornerstone
of quantum protocols like quantum teleportation and superdense coding.
Entanglement enables quantum systems to process and transmit information in ways that are
impossible in classical systems, giving quantum computing its unparalleled power.

2.2.3 Quantum Gates Used in QAOA

Quantum gates are the fundamental building blocks of quantum algorithms, acting on qubits
to perform operations. In the Quantum Approximate Optimization Algorithm (QAOA), specific
quantum gates are used to construct and evolve the quantum states. Below, we describe the key
gates employed in QAOA:

a. Pauli-X Gate: The Pauli-X gate, also known as the quantum NOT gate, flips the state of
a qubit:
X|0⟩ = |1⟩, X|1⟩ = |0⟩
Mathematically, the Pauli-X gate is represented by the matrix:
 
0 1
X=
1 0

b. Pauli-Z Gate: The Pauli-Z gate applies a phase of −1 to the |1⟩ state while leaving |0⟩
unchanged:
Z|0⟩ = |0⟩, Z|1⟩ = −|1⟩
Its matrix form is:  
1 0
Z=
0 −1

c . Hadamard Gate (H): The Hadamard gate creates a superposition of states:

|0⟩ + |1⟩ |0⟩ − |1⟩

H|0⟩ = √ , H|1⟩ = √
2 2
Its matrix form is:  
1 1 1
H=√
2 1 −1

d. Controlled-Z Gate (CZ): The Controlled-Z gate introduces entanglement between two
qubits. It applies the Z gate to the target qubit only if the control qubit is in the |1⟩ state:
(
−|ab⟩, if a = b = 1
CZ|ab⟩ =
|ab⟩, otherwise

The matrix representation is:  

1 0 0 0
0 1 0 0
CZ = 
0

0 1 0
0 0 0 −1

4
These gates form the building blocks of QAOA. The Hadamard gate initializes the superposition,
while the UC (γ) and UB (β) gates alternately evolve the state under the cost and mixer Hamilto-
nians. Controlled-Z gates create entanglement, and Pauli gates manipulate individual qubits as
needed.

2.2.4 Measurements

Measurements are the final step in any quantum computation. In this process, the quantum state
of a qubit is projected onto one of the classical basis states, typically |0⟩ or |1⟩, collapsing the
superposition into a definite outcome. The probability of each outcome is determined by the
squared amplitude of the corresponding state in the quantum system.
If the quantum state of a qubit is represented as:

|ψ⟩ = α|0⟩ + β|1⟩,

where α and β are complex numbers satisfying |α|2 + |β|2 = 1, the probabilities of measuring the
qubit in the states |0⟩ and |1⟩ are given by:

P (0) = |α|2 , P (1) = |β|2 .

Measurement is often denoted by a meter-like symbol or the operator M . For example:

M |ψ⟩ → Classical Outcome (0 or 1).

In QAOA, measurements are performed after applying the parameterized gates to the quantum
state. The resulting bitstrings represent potential solutions to the optimization problem. By
repeating the process multiple times, we can estimate the probabilities of different solutions and
identify the optimal one.

• Measurement collapses the quantum state to a classical outcome.

• Multiple measurements are required to approximate probabilities of different outcomes.

• In the computational basis, the possible outcomes are |0⟩ and |1⟩ for each qubit.

Example: For a 2-qubit system with state:

1
|ψ⟩ = √ (|00⟩ + |11⟩),
2
a measurement in the computational basis can yield either |00⟩ or |11⟩, each with a probability of
P (00) = P (11) = 21 .
Measurements bridge the quantum and classical worlds by extracting information from quantum
states. In QAOA, they are vital for interpreting the quantum system’s output and refining the
optimization process.

5
3 Quantum Approximate Optimization Algorithm (QAOA)
3.1 Overview of QAOA
The Quantum Approximate Optimization Algorithm (QAOA) is a hybrid quantum-classical algo-
rithm designed to solve complex combinatorial optimization problems. It combines the principles
of quantum mechanics with classical optimization to efficiently explore the solution space of hard
problems.
The core idea of QAOA is to encode the optimization problem into quantum operators, known as
Hamiltonians, and iteratively refine the solution by alternating between two key components:

• Cost Hamiltonian (UC (γ)): Encodes the objective function of the optimization problem,
assigning lower energy states to better solutions.
• Mixer Hamiltonian (UB (β)): Facilitates transitions between different states, enabling the
algorithm to explore the solution space.

The algorithm starts with an initial quantum state where all possible solutions are in superposition.
It then applies alternating layers of the cost Hamiltonian and mixer Hamiltonian, controlled by
two tunable parameters, γ and β. These parameters are optimized classically to maximize the
probability of measuring the optimal solution after multiple iterations.
QAOA takes advantage of quantum superposition, interference, and entanglement to explore the
solution space efficiently. Its iterative nature and hybrid design make it a powerful tool for tackling
NP-hard problems, such as the MAX-CUT problem.

3.2 Components of QAOA

The Quantum Approximate Optimization Algorithm (QAOA) consists of several key components
that work together to solve optimization problems. Below, we explain these components step by
step.

3.2.1 Objective Function and Its Transformation

The first step in QAOA is to define the objective function, which represents the optimization
problem. This function, denoted as C, assigns a numerical value to each solution z from the set of
all possible solutions. The goal is to find z that maximizes C(z):
m
X
C(z) = Ck (z),
k=1

where:

• z = z1 z2 · · · zn represents a bitstring of n variables, with zk ∈ {0, 1},

• Ck (z) represents individual constraints or terms of the objective function.

3.2.2 Objective Function as a Diagonal Operator

To represent the objective function in a quantum system, C is treated as a diagonal operator acting
on quantum states in the computational basis. For a quantum state |z⟩, the operator C acts as:
C|z⟩ = f (z)|z⟩,
Pm
where f (z) = k=1 Ck (z) is the value of the objective function for the bitstring z.

• The eigenstates of C are the computational basis states |z⟩,

• The eigenvalues are the corresponding function values f (z).

The set of eigenvalues {f (z) : z ∈ {0, 1}n } represents all possible values of the objective function.

6
3.2.3 General Quantum State Representation

A general quantum state is a superposition of all computational basis states:

X
|ψ⟩ = az |z⟩,
z∈{0,1}n

where az are complex coefficients satisfying the normalization condition:

X
|az |2 = 1.
z∈{0,1}n

Applying the operator C to this state gives:

X
C|ψ⟩ = f (z)az |z⟩.
z∈{0,1}n

3.2.4 Expectation Value of the Objective Function

The expectation value of C for the quantum state |ψ⟩ is given by:
X
⟨C⟩ = ⟨ψ|C|ψ⟩ = f (z)|az |2 .
z∈{0,1}n

This value represents the weighted average of f (z) over all possible states z, where the weights
are the probabilities |az |2 . If the state |ψ⟩ is optimized, ⟨C⟩ approaches its maximum value,
corresponding to the optimal solution z ′ .

3.2.5 Cost Hamiltonian with Unitary Operator

The Cost Hamiltonian (HC ) in QAOA is responsible for encoding the optimization problem into
the quantum system. It maps the objective function f (z) directly to the eigenvalues of a diagonal
operator in the computational basis. The evolution of the quantum state under this Hamiltonian
is governed by the unitary operator:

U (C, γ) = e−iγHC ,

where:

• γ is a tunable parameter (a variational parameter) that controls the evolution time, and
• HC is the diagonal Cost Hamiltonian representing the objective function.

Action of U (C, γ) on a General Quantum State Suppose the quantum system is initialized
in a general state: X
|ψ⟩ = az |z⟩,
z∈{0,1}n

where az are the amplitudes of the computational basis states |z⟩.

The operator U (C, γ) applies a phase e−iγf (z) to each computational basis state, transforming the
quantum state as follows: X
U (C, γ)|ψ⟩ = az e−iγf (z) |z⟩.
z∈{0,1}n

Here:

• f (z) is the value of the objective function for the bitstring z,

• The phases e−iγf (z) depend on γ, which is adjusted iteratively during the QAOA process.

This operation encodes the structure of the optimization problem into the quantum system by
associating a phase with each basis state proportional to its objective function value.

7
Properties of U (C, γ)

• U (C, γ) is diagonal in the computational basis, meaning it only modifies the phases of the
basis states |z⟩.
• It preserves the norm of the quantum state, ensuring the system remains valid for further
quantum operations.

By applying U (C, γ), the QAOA algorithm encodes the problem’s objective function into the
quantum state, which is essential for steering the system towards the optimal solution.

3.2.6 Mixer Hamiltonian with Unitary Operator

The Mixer Hamiltonian (HB ) is the second key component of QAOA. It is responsible for
introducing transitions between quantum states, allowing the algorithm to explore the solution
space. The goal of the mixer is to ensure that the algorithm does not get trapped in a local
minimum of the objective function.
The evolution of the quantum state under HB is governed by the unitary operator:
U (B, β) = e−iβHB ,
where:

• β is a tunable parameter controlling the strength of the mixing operation, and

• HB is the Mixer Hamiltonian, typically defined to encourage exploration of all possible solu-
tions.

The domain of β is restricted to β ∈ [0, π], ensuring meaningful phase rotations during the mixing
process.

Form of the Mixer Hamiltonian For QAOA, the Mixer Hamiltonian HB is commonly defined
as:
n
X
HB = Xi ,
i=1
where Xi is the Pauli-X operator acting on the i-th qubit.
The Pauli-X operator has the following action on a single qubit:
X|0⟩ = |1⟩, X|1⟩ = |0⟩,
which effectively flips the state of the qubit.
When applied across all qubits, HB drives transitions between computational basis states, enabling
the exploration of different solutions in the solution space.

Action of U (B, β) on a Quantum State Suppose the quantum system is in a general state:
X
|ψ⟩ = az |z⟩.
z∈{0,1}n

The operator U (B, β) evolves the state as:

n
Y
U (B, β)|ψ⟩ = e−iβXi |ψ⟩.
i=1

For a single qubit, the operator e−iβX has the matrix form:
e−iβX = cos(β)I − i sin(β)X,
where I is the identity operator.
Thus, the application of U (B, β) introduces rotations in the solution space, facilitating the explo-
ration of alternative solutions.

8
Properties of U (B, β)

• U (B, β) ensures that the quantum state does not get trapped in a single configuration.

• It expands the search space by creating superpositions of basis states.

• The parameter β is tuned to balance the exploration of the solution space with the optimiza-
tion of the objective function.

By applying U (B, β), the QAOA algorithm enables a more comprehensive search for the optimal
solution through controlled exploration of the solution space.

3.2.7 Initial State in QAOA

The QAOA algorithm starts with an initial quantum state |s⟩, which is a uniform superposition of
all computational basis states. This state ensures that all possible solutions are equally weighted
at the beginning of the algorithm.
The initial state is prepared by applying the Hadamard gate H to each qubit in the initial |0⟩⊗n
state:
|s⟩ = H ⊗n |0⟩⊗n ,
where |0⟩⊗n represents the state of all n qubits initialized in |0⟩, and H ⊗n is the tensor product of
n Hadamard gates.

Action of Hadamard Gate on |0⟩⊗n : For a single qubit, the Hadamard gate acts as:

1
H|0⟩ = √ (|0⟩ + |1⟩).
2

When applied to n qubits, the resulting state is:

1 X
|s⟩ = H ⊗n |0⟩⊗n = √ |z⟩,
2n z∈{0,1}n

where:

• |z⟩ represents each computational basis state (bitstring) of n qubits,

• The coefficient √1
2n
ensures normalization of the quantum state.

Properties of |s⟩:

• Uniform Superposition: |s⟩ assigns equal probability amplitudes to all computational

basis states.

• Unbiased Start: The uniform superposition ensures that no solution is preferred initially,
enabling fair exploration of the solution space.

3.2.8 Angle-Dependent Quantum State

For any integer p ≥ 1, QAOA defines a quantum state parameterized by 2p angles, denoted as
γ1 , . . . , γp (γ) and β1 , . . . , βp (β). These angles control the evolution of the quantum state through
p alternating applications of the Cost and Mixer Hamiltonians.
The angle-dependent quantum state is represented as:

|ψp (γ, β)⟩ = UB (βp )UC (γp ) · · · UB (β1 )UC (γ1 )|s⟩,

where:

9
 • |s⟩ is the initial uniform superposition state,

• UC (γk ) = e−iγk HC is the unitary operator generated by the Cost Hamiltonian HC ,

• UB (βk ) = e−iβk HB is the unitary operator generated by the Mixer Hamiltonian HB , and
• k ∈ {1, . . . , p} indexes the layers.

Iterative Evolution The state |ψp (γ, β)⟩ is constructed by applying alternating layers of UC (γk )
and UB (βk ) to the initial state |s⟩. At each step:

1. UC (γk ) applies a problem-specific phase to each basis state.

2. UB (βk ) explores the solution space by driving transitions between basis states.

This iterative process allows QAOA to evolve the quantum state toward one that encodes high-
probability solutions to the optimization problem.

Properties:

• Dependence on Parameters: The quality of the solution depends on the choice of param-
eters γ = (γ1 , . . . , γp ) and β = (β1 , . . . , βp ), which are optimized classically.
• Layered Structure: Increasing p (number of layers) improves the approximation quality
but also increases computational complexity.

• Hybrid Nature: The variational parameters are tuned using a classical optimization algo-
rithm based on measurements of the quantum system.

10