# A Survey of Quantum Computing Algorithms for Mathematical Optimization: State-Of-The-Art in Research & Exploration of Further Possibilities

Sambuddha Chakrabarti, Satyasaran Changdar, Rajat Khanda

► To cite this version:

Sambuddha Chakrabarti, Satyasaran Changdar, Rajat Khanda. A Survey of Quantum Computing Algorithms for Mathematical Optimization: State-Of-The-Art in Research & Exploration of Further Possibilities. 2026. hal-05487965v2

HAL Id: hal-05487965

https://hal.science/hal-05487965v2

Preprint submitted on 8 Feb 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# A Survey of Quantum Computing Algorithms for Mathematical Optimization: State-Of-The-Art in Research & Exploration of Further Possibilities

Sambuddha Chakrabarti<sup>a,*</sup>, Satyasaran Changdar<sup>b</sup>, Rajat Khanda<sup>c</sup>

<sup>a</sup>Princeton University, Princeton, New Jersey, USA

<sup>b</sup>University of Copenhagen, Copenhagen, Denmark

<sup>c</sup>Supermicro, San Jose, USA

## Abstract

This paper presents a comprehensive review and systematic coverage of foundational quantum optimization algorithms-QAOA, Quantum Annealing, VQE, VQLS, and HHL-tracing their development all the way from Schrödinger's equation through gate-based quantum computing (Deutsch, Deutsch-Jozsa, Bernstein-Vazirani, QFT, Shor's, and Grover's algorithms) to hybrid quantum-classical approaches for NISQ-era hardware. We also present the transverse field Ising model's role in quantum annealing as well as practical hardware implementations with the Chimera, Pegasus, and Zephyr topologies of the D-Wave quantum annealer, addressing key challenges including barren plateaus, circuit trainability, and noise resilience.

In the simulations section, quantum computing applications to collaborative filtering and social network optimization have been presented. We introduce two original contributions: (1) a quantum collaborative filtering model based on VQE principles that leverages quantum entanglement to represent user-item relationships, requiring logarithmically fewer parameters than classical embedding methods while accessing exponentially larger state spaces, and demonstrating test RMSE of 0.85 on synthetic data; and (2) a Quantum Social Network (QSN) framework modeling belief dynamics through superposition and entanglement, revealing emergent consensus and polarization phenomena validated via Qiskit simulations.

By demonstrating that variational quantum algorithms can tackle real-world recommendation and network optimization problems on current hardware, we bridge theoretical quantum computing with practical machine learning applications and identify concrete pathways toward quantum advantage beyond traditional combinatorial optimization.

**Keywords:** Quantum Mechanics, Bloch Sphere, Gate-based Quantum Computing, Quantum Annealing, Quantum Collaborative Filtering

<footnote>*I am the corresponding author</footnote>

<footnote>Email address: schakrabarti@utexas.edu (Sambuddha Chakrabarti)</footnote>
# 1. Introduction & Literature Survey

Since the dawn of computing, numerous attempts have been made throughout history to enhance the speed of computing machines while minimizing the use of resources such as memory and processor hardware. Equally important are advancements in computing architectures. Within the classical Von Neumann architecture, many distributed and parallel computing algorithms (see, for example, distributed algorithms applied to power network optimization problems in [MDS+17], [KMG+18], [CKC+14], [Cha17], [CB20])—and their supporting hardware—have been developed and implemented. Nevertheless, certain classes of computational problems, particularly those involving combinatorial complexity, high-dimensional search spaces, or non-convex optimization, remain intractable for classical approaches.

The quest for alternative computational paradigms has led to increasing interest in quantum computing—a model of computation rooted in the principles of quantum mechanics. Among the earliest and most influential formulations of quantum theory is Schrödinger's *wave mechanics*. Introduced in 1926, it describes the time evolution of a quantum system's state vector in terms of the “wave function,” $|\psi(t)\rangle$ via the time-dependent Schrödinger equation:

$$i\hbar \frac{\partial}{\partial t} |\psi(t)\rangle = \hat{H} |\psi(t)\rangle, \qquad (1)$$

where $\hat{H}$ is known as the “Hamiltonian” operator representing the total energy of the system, $\hbar = \frac{\hbar}{2\pi}$ is the reduced Planck constant, and $|\psi(t)\rangle$ is a complex valued vector of “wave function” for the different quantum mechanical states of a quantum system or a quantum particle. It belongs to a complex Hilbert space $\mathcal{H}$. A Hilbert space is a complete vector space equipped with an inner product, generalizing Euclidean space to potentially infinite dimensions [GS18], [Hal93]. In quantum mechanics, it serves as the state space in which vectors represent quantum states and operators describe observables [NC02]. The Hamiltonian not only encodes the system's energy but also governs its time evolution. As a Hermitian operator, its eigenvalues correspond to measurable energy levels, and its eigenstates represent physically meaningful configurations of the system.

This linear partial differential equation governs the deterministic evolution of the quantum state, with probabilities emerging from the squared magnitudes of inner products in $\mathcal{H}$.

To represent quantum states and operations more concisely, Paul Dirac introduced the *bra-ket* notation [Dir30]. In this formalism, a state vector is written as a “ket” $|\psi\rangle$, and its dual (complex conjugate transpose) as a “bra” $\langle\psi|$. The inner product between two states $|\psi\rangle$ and $|\phi\rangle$ is written as $\langle\psi|\phi\rangle$, yielding a complex number that encodes transition amplitudes. Operators $\hat{O}$ act linearly on kets: $\hat{O}|\psi\rangle$, and expectation values are expressed as $\langle\psi|\hat{O}|\psi\rangle$.

This notation elegantly captures the linear and probabilistic structure of quantum theory. It has become the standard language for describing quantum algorithms, quantum circuits, and the evolution of quantum systems. The abstraction it provides is indispensable in quantum optimization, where manipulating quantum states through parameterized operations lies at the heart of algorithm design [Fre23].
The idea of making use of quantum mechanics for computation can be traced back to the seminal 1953 paper [MRR+53] by Metropolis et al. where the authors, for the very first time, hinted at what later came to be known as “Quantum Annealing (QA).” After a long pause of four and half decades, arrived the next highly influential and foundational paper in 1998 by Kadowaki-Nishimori [KN98], which laid the unquestioned and rigorous groundwork for QA. This was followed by seminal papers by Kaminsky-Lloyd [KL04] and Brooke et al. [BBR01] which delved further into and explored the different aspects of QA for solving the “Quadratic Unconstrained Binary Optimization (QUBO)” for “Ising models,” which is a very hard problem from physics, related to alignment of magnetic domains embedded within an external impressed magnetic field. In 2014, Lucas presented a compilation of some of the NP problems, that can be transformed to Ising model and solved vis QA [Luc14]. The trend has gained significant momentum in recent times led by researchers from Los Alamos National Laboratory, D-Wave, etc. [TAM+24], [CV20] etc. Along with the developments on QA, the other major sub-field of QC, namely, the gate-based QC in which the states of qubits are endowed with much more control than in QA have also been advanced substantially, with some fo the early pivotal works by David Deutsche in 1985 [Deu85], where he explored the connection between the physics of QC and the classical Turing machine based architecture of computing machines, as well as, introduced the early signs of the Deutsche’s algorithm, which showed the possibility of achieving quantum supremacy with an “Oracle”, the paper by David Deutsche and Richard Josza in 1992 [DJ92], where the authors established the speedup with multi-qubit Deutsche-Josza algorithm. This closely followed the groundbreaking work by Umesh Vazirani and Ethan Bernstein in 1997 [BV97], where the authors explored the computational complexity of QC and extended the earlier works of Deutsche on quantum Turing machine much further, thereby introducing the “Bernstein-Vazirani” algorithm. The seminal work on “An Approximate Fourier Transform Useful in Quantum Factoring” by Don Coppersmith in 2002 [Cop94] provided a computationally simpler approximation for quantum factoring, useful in the context of Peter Shor’s algorithm. Based on this, the seminar work by Peter Shor in 1994 [Sho94] introduced quantum algorithms for factoring large numbers and finding discrete logarithms, problems that are central to classical cryptography and the other seminal paper by Lov Grover in 1996 [Gro96], in which the author presented an algorithm that provides a quadratic speedup over classical algorithms for searching an unstructured (unsorted) database. However, it has come to notice that in the NISQ era, these algorithms are too idealistic to be implemented. So, researchers came up with hybrid classical-quantum algorithms like the Quantum Approximate Optimization Algorithm (QAOA) [FGG14], Variational Quantum Eigensolver (VQE) [P+14], Harrow-Hassidim-Lloyd (HHL) Algorithm [HHL09], Variational Quantum Linear Solver (VQLS) [BPLC+23] etc. The recent paper [AAA+24] from 2024 presents a summary of the different types of QC approaches and algorithms and the merits and challenges of those. Among the application areas, some recent works on the area of power systems optimization are [AK25a], [HK25a], [HK25b], [HRK26], [AK25b] etc.

Quantum computers change computational complexity by introducing the BQP (Bounded-error Quantum Polynomial time) class, solving problems intractable for classical computers in polynomial time, like factoring or quantum simulation, through quantum phenomena like
superposition and entanglement, offering speedups for specific tasks but not all, challenging
the Church-Turing thesis.

1.1. Key Concepts

1.1.1. BQP (Bounded-error Quantum Polynomial time)

The class of problems solvable by a quantum computer in polynomial time with high
probability, analogous to the classical BPP class.

1.1.2. Quantum Advantage

Quantum computers can solve certain problems (like simulating molecules or factoring large numbers with Shor's algorithm) exponentially faster than the best-known classical algorithms.

1.1.3. Quantum-Specific Operations

Gates like the Hadamard gate and CNOT gate enable different computational paradigms, leveraging quantum properties.

1.2. How Quantum Computers Change Complexity

1.2.1. Algorithm Design

Quantum algorithms exploit quantum mechanics (superposition, entanglement) to explore
vast solution spaces simultaneously, leading to more efficient steps for specific problems.

1.2.2. New Complexity Classes

Quantum complexity theory studies these new classes (like BQP) and their relationships to
classical ones (P, NP).

1.2.3. Challenging the Church-Turing Thesis

Quantum computers pose a challenge to the idea that any physical computer can simulate
another with only polynomial slowdown, as they offer exponential speedups for some problems.

1.3. Examples of Quantum Speedups

1.3.1. Factoring Integers

Shor's algorithm provides an exponential speedup over classical factoring algorithms.
<figure><img src="image_2.png" /><figcaption>Figure 1: Quantum Complexity (Based On: Wikipedia)</figcaption></figure>

### 1.3.2. Quantum Simulation

Simulating quantum systems (like molecules) becomes naturally efficient on quantum computers, whereas it's exponentially hard classically.

In essence, quantum computers shift problems from “intractable” (exponential time) to “tractable” (polynomial time) for a specific set of problems, not all of them.

The rest of the paper is organized as follows: After the gentle introduction in this section 1, we will take a deeper dive into the details of quantum mechanics in section 2. This will form the foundation, based on which in section 3, we will introduce the basic principles of primarily gate-based quantum computing, but also elements of quantum annealing and the visual representation of quantum bits (or “qubits”) with the help of the “Bloch Sphere.” Thereafter, in section 4, we will introduce some of the most widely used and popular algorithms starting with “Deutsch’s Algorithm” and going all the way to the quantum-classical hybrid algorithms like the “Variational Quantum Linear Solver (VQLS).” Section 5 presents the “Transverse Field Ising Model” and the Quantum Annealing (QA) to solve “Quadratic Unconstrained Binary Optimization (QUBO)” problems. Finally, in section 6 we will be presenting some parting thoughts and numerical simulations of applications of quantum computing to quantum collaborative filtering and to social network optimization problems.
## 2. Schrödinger Equation

The Schrödinger equation governs the quantum behavior of particles. For a single non-relativistic particle of mass $m$ moving in one spatial dimension under potential $V(x, t)$, the time-dependent Schrödinger equation is [Cha09]:

$$i\hbar\frac{\partial}{\partial t}|\Psi(t)\rangle = \hat{H}|\Psi(t)\rangle, \qquad (2)$$

where the Hamiltonian operator, $\hat{H}$ in position representation is given by:

$$\hat{H} = -\frac{\hbar^2}{2m} \frac{\partial^2}{\partial x^2} + V(x, t).$$

Projecting onto the position eigenstate $|x\rangle$, we obtain the coordinate-space form:

$$i\hbar\frac{\partial}{\partial t}\langle x|\Psi(t)\rangle = \left[-\frac{\hbar^2}{2m}\frac{\partial^2}{\partial x^2} + V(x,t)\right]\langle x|\Psi(t)\rangle, \qquad (3)$$

After Substituting in Eqn. 2, we arrive at the position-space Schrödinger equation for a single nonrelativistic particle in one dimension

$$i\hbar\frac{\partial}{\partial t}\Psi(x,t) = -\frac{\hbar^2}{2m}\frac{\partial^2\Psi(x,t)}{\partial x^2} + V(x,t)\Psi(x,t). \qquad (4)$$

where $\Psi(x,t) \equiv \langle x|\Psi(t)\rangle$ is a wave function, a function that assigns a complex number to each point $x$ at each $t$. In other words, the wave function $\Psi(x,t)$ is the position-space representation of the abstract state vector $|\Psi(t)\rangle$, obtained by projecting it onto position eigenstates $|x\rangle$.

### 2.1. Solution using Separation of Variables

If the potential $V(x, t)$ is independent of time, we may write the total state as:

$$|\Psi(t)\rangle = f(t)|\psi\rangle, \qquad (5)$$

and hence in the position representation:

$$\langle x|\Psi(t)\rangle = f(t)\langle x|\psi\rangle = \psi(x)f(t), \qquad (6)$$

where $\psi(x) = \langle x|\psi\rangle$ is the spatial component and $f(t)$ the temporal one.

Substitute into the Schrödinger equation:

$$i\hbar\frac{\partial}{\partial t}\langle x|\Psi(t)\rangle = i\hbar\psi(x)\frac{df(t)}{dt}$$

and

$$\hat{H} \langle x|\Psi(t)\rangle = \left[-\frac{\hbar^2}{2m}\frac{d^2}{dx^2} + V(x)\right] \psi(x)f(t).$$
Equating both sides and dividing by $\psi(x)f(t)$, we get:

$$i\hbar \frac{1}{f(t)} \frac{df(t)}{dt} = -\frac{\hbar^2}{2m} \frac{1}{\psi(x)} \frac{d^2\psi(x)}{dx^2} + V(x). \quad (7)$$

Since the left side is time-dependent and the right side is space-dependent, both must be equal to a constant $E$ (total energy):

$$E = i\hbar \frac{1}{f(t)} \frac{df(t)}{dt} = -\frac{\hbar^2}{2m} \frac{1}{\psi(x)} \frac{d^2\psi(x)}{dx^2} + V(x). \quad (8)$$

This yields the two separated equations:

$$\frac{df(t)}{dt} = -\frac{iE}{\hbar}f(t), \quad (9)$$

$$\hat{H} |\psi\rangle = E |\psi\rangle, \quad \text{or in position basis:} \quad -\frac{\hbar^2}{2m} \frac{d^2\psi(x)}{dx^2} + V(x)\psi(x) = E\psi(x). \quad (10)$$

## 2.2. The Infinite Potential Well (Particle in a Box)

Consider a particle in a 1D box of length $L$ with:

$$V(x) = \begin{cases} 0, & 0 < x < L, \\ \infty, & \text{otherwise.} \end{cases}$$

The wavefunction must vanish at the walls. The boundary conditions are

$$\psi(0) = \psi(L) = 0.$$

Inside the box:

$$-\frac{\hbar^2}{2m} \frac{d^2\psi(x)}{dx^2} = E\psi(x) \Rightarrow \frac{d^2\psi(x)}{dx^2} + \frac{2mE}{\hbar^2}\psi(x) = 0. \quad (11)$$

Let $k = \sqrt{\frac{2mE}{\hbar^2}}$, giving:

$$\psi(x) = A \cos(kx) + B \sin(kx).$$

Apply boundary conditions:

$$\psi(0) = 0 \Rightarrow A = 0 \text{ and } \psi(L) = 0 \Rightarrow B \sin(kL) = 0 \Rightarrow kL = n\pi, \text{ where } n \in \mathbb{Z}^{+}$$

Thus:

$$k = \frac{n\pi}{L}, \quad E_n = \frac{\hbar^2 k^2}{2m} = \frac{n^2 \pi^2 \hbar^2}{2mL^2}.$$
## 2.3. Normalized Eigenfunctions

Each stationary state $|\psi_n\rangle$ satisfies:

$$ \langle\psi_n|\psi_n\rangle = 1 \Rightarrow \int_0^L |\psi_n(x)|^2dx = 1. $$

Hence:

$$ \psi_n(x) = \langle x|\psi_n\rangle = \begin{cases} \sqrt{\frac{2}{L}} \sin\left(\frac{n\pi x}{L}\right), & 0 < x < L, \quad n = 1, 2, 3, \dots \\ 0, & \text{otherwise,} \end{cases} $$

These eigenfunctions are orthonormal:

$$ \langle\psi_n|\psi_m\rangle = \delta_{nm}. $$

where $\delta_{nm}$ is the Kronecker delta (1 if $n = m$, 0 otherwise).

## 2.4. Time-Dependent Wavefunctions

The time evolution of energy eigenstates is given by:

$$ |\psi_n(t)\rangle = e^{-iE_n t/\hbar} |\psi_n\rangle. $$

In position space:

$$ \Psi_n(x, t) = \langle x|\psi_n(t)\rangle = e^{-iE_n t/\hbar} \langle x|\psi_n\rangle = e^{-iE_n t/\hbar} \psi_n(x), $$

which becomes:

$$ \Psi_n(x, t) = \begin{cases} \sqrt{\frac{2}{L}} \sin\left(\frac{n\pi x}{L}\right) e^{-iE_n t/\hbar}, & 0 < x < L, \\ 0, & \text{otherwise.} \end{cases} $$

This describes a stationary quantum state in a 1D infinite potential well. While the spatial profile $\psi_n(x)$ remains fixed (stationary), the overall phase evolves in time, leading to observable interference patterns when superpositions of such states are considered. In the next section, while defining the “qubit” and thereby laying the foundation of quantum computing algorithms, we will look at a special situation, in which $\psi_n(x)$ can only assume just two states and is also invariant with respect to time, $t$.

# 3. Quantum Computing Foundation

Quantum computation fundamentally differs from classical computation in the representation and manipulation of information. While classical bits can exist only in definite states 0 or 1, quantum bits or qubits can exist in superpositions of both. This section introduces the foundational concepts necessary for understanding quantum optimization, including qubit representation, the Bloch sphere, quantum gates, measurement, and multi-qubit systems.
## 3.1. Qubits and the Bloch Sphere Representation

A qubit is a unit vector in a two-dimensional complex Hilbert space $\mathbb{C}^2$. The general form of a pure qubit state is:

$$|\psi\rangle = \alpha|0\rangle + \beta|1\rangle, \quad \text{with } \alpha, \beta \in \mathbb{C}, \quad |\alpha|^2 + |\beta|^2 = 1. \qquad (12)$$

Every pure qubit state can be uniquely represented (up to a global phase) on the surface of a unit 3D sphere, known as the Bloch Sphere [NC02]. By parameterizing $\alpha$ and $\beta$ as:

$$|\psi\rangle = \cos\left(\frac{\theta}{2}\right)|0\rangle + e^{i\phi}\sin\left(\frac{\theta}{2}\right)|1\rangle, \qquad (13)$$

with $\theta \in [0, \pi]$ and $\phi \in [0, 2\pi)$, each state corresponds to a point on the Bloch Sphere with spherical coordinates $(\theta, \phi)$.

<figure><img src="image_3.png" /><figcaption>Figure 2: The Bloch Sphere: Geometric representation of pure qubit states.</figcaption></figure>

In this representation:

* $|0\rangle$ lies at the north pole ($\theta = 0$),

* $|1\rangle$ lies at the south pole ($\theta = \pi$),

* Superpositions such as $\frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$ lie on the equator.

Quantum gates can be understood as rotations on this sphere, making the Bloch representation essential for visualizing qubit dynamics in variational algorithms [Pre18].

## 3.2. Quantum Gates and Unitary Operations

Quantum gates are unitary operators acting on qubit states, preserving norm and enabling reversible computation. Common single-qubit gates include [NC02]:

* Pauli-X (bit-flip):

$$X = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}$$
• Pauli-Y:

$$Y = \begin{bmatrix} 0 & -i \\ i & 0 \end{bmatrix}$$

• Pauli-Z (phase-flip):

$$Z = \begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix}$$

• Hadamard:

$$H = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}$$

Parameterized gates such as rotations are central in quantum optimization:

$$R_x(\theta) = e^{-i\theta X/2} = \cos\left(\frac{\theta}{2}\right) I - i \sin\left(\frac{\theta}{2}\right) X,$$

$$R_y(\theta) = e^{-i\theta Y/2},$$

$$R_z(\theta) = e^{-i\theta Z/2}.$$

These gates rotate the qubit state around the corresponding axis of the Bloch Sphere by angle $\theta$, and are widely used in variational quantum algorithms such as QAOA and VQE [FGG14, P$^{+}$14].

## Multi-Qubit Gates

Multi-qubit gates operate on entangled states and are essential for building complex quantum circuits:

**Controlled-NOT (CNOT):** A two-qubit gate where the second qubit (target) is flipped if the first qubit (control) is $|1\rangle$. Matrix form:

$$CNOT = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix}$$

Circuit:

<figure><img src="image_4.png" /></figure>

**Toffoli (CCNOT):** A three-qubit gate with two control qubits and one target. The target is flipped only if both controls are $|1\rangle$. Matrix form (8×8 omitted for brevity). Circuit:

<figure><img src="image_5.png" /></figure>
**SWAP Gate:** Interchanges the states of two qubits. Matrix form:

$$SWAP = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}$$

Circuit:

<figure><img src="image_6.png" /></figure>

**Controlled Rotations (CRx, CRy, CRz):** Apply a rotation to the target qubit around the chosen axis only if the control qubit is $|1\rangle$. Example (CRz):

<figure><img src="image_7.png" /></figure>

Together, single-qubit and multi-qubit gates form a **universal gate set**, enabling the realization of any quantum algorithm. Their decomposition into hardware-native operations is critical for practical execution on quantum devices.

### 3.3. Quantum Measurement

Measurement in quantum mechanics collapses a superposition to one of its basis states. For a qubit state $|\psi\rangle = \alpha|0\rangle + \beta|1\rangle$, a measurement in the computational basis yields the following.

* Outcome 0 with probability $|\alpha|^2$,

* Outcome 1 with probability $|\beta|^2$.

Post-measurement, the qubit collapses into the corresponding eigenstate. Measurement is a non-unitary, probabilistic operation and constitutes the final step in most quantum optimization protocols [NC02].

### 3.4. Multi-Qubit Systems and Entanglement

**Definition 1 (Tensor Product).** In quantum computing, we need a mathematical framework to describe composite quantum systems, systems consisting of multiple qubits. The tensor product provides this framework, allowing us to construct the state space of a composite system. Let $\mathcal{H}_A$ and $\mathcal{H}_B$ be Hilbert spaces of dimensions $d_A$ and $d_B$ respectively. The tensor product $\mathcal{H}_A \otimes \mathcal{H}_B$ is a new Hilbert space of dimension $d_A \cdot d_B$.
For quantum computing with n qubits, where each qubit belongs to $\mathbb{C}^2$, the composite system belongs

$$ \mathcal{H} = \underbrace{\mathbb{C}^2 \otimes \mathbb{C}^2 \otimes \cdots \otimes \mathbb{C}^2}_{n \text{ times}} = \mathbb{C}^{2n} \qquad (14) $$

Given $|\psi\rangle \in \mathcal{H}_A$ and $|\phi\rangle \in \mathcal{H}_B$, their tensor product is denoted:

$$ |\psi\rangle \otimes |\phi\rangle = |\psi\rangle |\phi\rangle = |\psi, \phi\rangle \qquad (15) $$

If $|\psi\rangle = \begin{bmatrix} \alpha_0 \\ \alpha_1 \end{bmatrix}$ and $|\phi\rangle = \begin{bmatrix} \beta_0 \\ \beta_1 \end{bmatrix}$, then:

$$ |\psi\rangle \otimes |\phi\rangle = \begin{bmatrix} \alpha_0\beta_0 \\ \alpha_0\beta_1 \\ \alpha_1\beta_0 \\ \alpha_1\beta_1 \end{bmatrix} \qquad (16) $$

For example two qubits basis states:

$$ \begin{align} |0\rangle \otimes |0\rangle &= |00\rangle = \begin{bmatrix} 1 \\ 0 \\ 0 \\ 0 \end{bmatrix}, \quad |0\rangle \otimes |1\rangle &= |01\rangle = \begin{bmatrix} 0 \\ 1 \\ 0 \\ 0 \end{bmatrix}, \nonumber \\ |1\rangle \otimes |0\rangle &= |10\rangle = \begin{bmatrix} 0 \\ 0 \\ 1 \\ 0 \end{bmatrix}, \quad |1\rangle \otimes |1\rangle &= |11\rangle = \begin{bmatrix} 0 \\ 0 \\ 0 \\ 1 \end{bmatrix} \tag{17} \end{align} $$

Multi-qubit systems are described by tensor product spaces. For example, the state of two qubits is given by:

$$ |\psi\rangle = \alpha|00\rangle + \beta|01\rangle + \gamma|10\rangle + \delta|11\rangle, \qquad (18) $$

with normalization $|\alpha|^2 + |\beta|^2 + |\gamma|^2 + |\delta|^2 = 1$. Such systems may exhibit entanglement, wherein the total state cannot be factored into individual qubit states. For instance, the Bell state:

$$ |\Phi^+\rangle = \frac{1}{\sqrt{2}}(|00\rangle + |11\rangle) \qquad (19) $$

is a maximally entangled state. Entanglement is a resource leveraged in quantum optimization to explore solution spaces non-classically [Pre18, Mon16].

## 4. Gate-Based Quantum Computing

In this section, we continue to expand upon the material presented in the 3 section and derive some of the most popular gate-based QC algorithms used to solve real-world problems.
## 4.1. Deutsch's Algorithm

### 4.1.1. The Problem:

The Deutsch algorithm works by creating an “Oracle,” which implements a function

$$f: \{0, 1\} \rightarrow \{0, 1\} \qquad (20)$$

which takes in one qubit as its argument and we're told that the function $f$ is either constant (i.e. outputs either 0 always or, 1 always) or balanced (i.e. outputs 0 for half of the input qubit values and 1 for the other half). Our task is to determine which of the two categories, $f$ belongs to.

### 4.1.2. Computational Complexity for a Classical Computer:

In this section, we will show that a classical computer needs two queries to determine whether $f$ is constant or balanced. This is because, if the function is balanced or constant, unless a classical computer checks both the outcomes, it cannot ascertain the nature of the function. However, as we'll show that for a quantum computer, with the Deutsch algorithm, it only takes 1 query.

### 4.1.3. Computational Complexity for a Quantum Computer Using the Deutsch Algorithm:

Before beginning the algorithm analysis we will define what a “Quantum Oracle” is and how it works.

* **Quantum Oracle:** We would always want to implement the quantum circuit transformations or functions in such a way that the operation is reversible. i.e. given any output of the transformation, we should be able to trace-back uniquely to what set of inputs produced that output. Consider the circuit shown in Figure 3.

In this circuit, $|x\rangle$ is the input qubit and $|y\rangle$ is the “target qubit.” As can be seen from this figure, one of the outputs is $|x\rangle$ itself, while the other one becomes $|y \oplus f(x)\rangle$. This indeed makes the transformation reversible, since if $|y\rangle = |0\rangle$, then the output is $|f(x)\rangle$ and otherwise, it's $|\overline{f(x)}\rangle$.

* **Phase Oracle:** Now, let's explore the situation when the target qubit happens to be $|−\rangle$. Now, an interesting thing happens as we will soon prove. The output for the $|x\rangle$ qubit now changes to $(-1)^{f(x)}|x\rangle$, whereas the other output now stays at $|−\rangle$ as shown in Figure 4. Let's see how this happens. We will write the input, which is $|x\rangle \otimes |−\rangle$ as $|x\rangle \otimes \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)$

$$|x\rangle \otimes |−\rangle = |x\rangle \otimes \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle) = \frac{1}{\sqrt{2}}(|x\rangle \otimes |0\rangle - |x\rangle \otimes |1\rangle)$$
<figure><img src="image_8.png" /><figcaption>Figure 3: Quantum Circuit for Quantum Oracle Function</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>Figure 4: Quantum Circuit for Phase Oracle Function</figcaption></figure>
<figure><img src="image_10.png" /><figcaption>Figure 5: Quantum Circuit for Deutsch Algorithm Implementation</figcaption></figure>

Now applying the oracle transformation (since it's acting on superposition states, being a linear operator, it'll distribute itself to both the terms:

$$ \frac{1}{\sqrt{2}}(|x\rangle \otimes |0\rangle - |x\rangle \otimes |1\rangle) \xrightarrow{U_f} \frac{1}{\sqrt{2}}(|x\rangle \otimes |0 \oplus f(x)\rangle - |x\rangle \otimes |1 \oplus f(x)\rangle) \\ = \frac{1}{\sqrt{2}}(|x\rangle \otimes |f(x)\rangle - |x\rangle \otimes |\overline{f(x)}\rangle) $$

$$ V(x) = \begin{cases} |x\rangle|-\rangle & \text{if } f(x) = 0 \\ -|x\rangle|-\rangle & \text{if } f(x) = 1. \end{cases} $$

which can be generalized as

$$ (-1)^{f(x)}|x\rangle|-\rangle $$

So, it can be concluded that a quantum oracle $U_f$ which implements either a constant or a balanced function $f$ transforms the set of inputs as follows:

$$ |x\rangle|y\rangle \rightarrow |y \oplus f(x)\rangle \qquad (22a) $$

$$ |x\rangle|-\rangle \rightarrow (-1)^{f(x)}|x\rangle|-\rangle \qquad (22b) $$

With this as the background material, let's look at the circuit for implementing Deutsch's algorithm, as shown in figure 5. In this figure, we start off with two quits $|0\rangle$ and $|1\rangle$ (The second qubit can also be thought of as starting with an initial value of $|0\rangle$, followed by an $X$-gate. After that, each qubit is passed through a Hadamard gate transforming them into $|+\rangle$ and $|-\rangle$, respectively. Given below is the analysis of the action of Deutsch's algorithm:

$$ |+\rangle \otimes |-\rangle = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle) \otimes |-\rangle \xrightarrow{U_f} \frac{1}{\sqrt{2}}(U_f(|0\rangle \otimes |-\rangle) + U_f(|1\rangle \otimes |-\rangle)) $$
We could distribute the operator as above, since $U_f$ is linear and the superposition is also a linear phenomenon.

$$ 
\begin{aligned}
&= \frac{1}{\sqrt{2}}((-1)^{f^{(0)}}|0\rangle \otimes |-\rangle + (-1)^{f^{(1)}}|1\rangle \otimes |-\rangle) \\
&= \frac{1}{\sqrt{2}}((-1)^{f^{(0)}}|0\rangle + (-1)^{f^{(1)}}|1\rangle) \otimes |-\rangle
\end{aligned}
$$

We can neglect $|-\rangle$ in above, since it's the other output. Now, depending on whether $f(0) = f(1)$ (i.e. $f$ is constant) or, $f(0) \neq f(1)$ (i.e. $f$ is balanced), we will get the following outcome:

$$ |\psi_2\rangle = \begin{cases} \pm|+\rangle & \text{if } f(0) = f(1) \\ \pm|-\rangle & \text{if } f(0) \neq f(1). \end{cases} $$

Ignoring the global phase $\pm$ from above, and applying a Hadamard gate now gives the final output to be measured (i.e. $|\psi_3\rangle$) as follows:

$$ |\psi_3\rangle = \begin{cases} |0\rangle & \text{if } f(0) = f(1) \\ |1\rangle & \text{if } f(0) \neq f(1). \end{cases} $$

Hence, it can be seen that, we just need 1 query of the oracle on a quantum machine to estimate the nature of $f$. In the next section, we'll extend this idea to any number of qubits.

## 4.2. Deutsch-Jozsa Algorithm

### 4.2.1. The Problem:

The Deutsch-Jozsa algorithm works by creating an “Oracle,” which implements a function

$$ f: \{0,1\}^n \to \{0,1\} \qquad (24) $$

which takes in $n$ qubits as its argument and we're told that the function $f$ is either constant (i.e. outputs either 0 always or, 1 always) or balanced (i.e. outputs 0 for half of the input qubit combinations and 1 for the other half). Our task is to determine which of the two categories, $f$ belongs to.

### 4.2.2. Computational Complexity for a Classical Computer:

In this section, we will show that for a classical computer, the solve time to determine whether $f$ is constant or balanced scales exponentially with the number of qubits (or, bit, in this case, to be precise) in the worst case. This is because, if the function is balanced or constant, then in the worst scenario, the first half of all the outputs will be same (either 1 or 0). So, after the first $2^n/2 = 2^{n-1}$ queries, we will have to do one more query to check whether $f$ is constant or balanced. If the $2^{n-1} + 1$-th result is the same as before, then $f$ is constant; otherwise, it's balanced. Hence, for a classical computer, it takes $2^{n-1} + 1$ (which is exponential in $n$) to ascertain the nature of $f$. In the next section, we'll show that for a quantum computer, with the Deutsch-Jozsa algorithm, it only takes 1 query.
<figure><img src="image_11.png" /><figcaption>Figure 6: Quantum Circuit for Deutsch-Josza Algorithm Implementation</figcaption></figure>

### 4.2.3. Computational Complexity for a Quantum Computer Using the Deutsch-Josza Algorithm:

In the Deutsch-Josza algorithm, to start off, the initial state of the qubits from figure 6 is as follows:

$$|\psi_0\rangle = |0\rangle \otimes |0\rangle \otimes \dots \otimes |0\rangle (n \text{ times}) \otimes |1\rangle = |00\dots0\rangle \otimes |1\rangle \quad (25)$$

After applying the Hadamard gates, the state will be as follows:

$$ \begin{aligned} |\psi_1\rangle &= H|0\rangle \otimes H|0\rangle \otimes \dots \otimes H|0\rangle (n \text{ times}) \otimes H|1\rangle = |++\dots+\rangle \otimes |-\rangle \\ &= \frac{1}{\sqrt{2^n}} \left( \sum_{s \in \{0,1\}^n} |s\rangle \right) \otimes |-\rangle \end{aligned} \quad (26a) $$

Here the term $\left( \sum_{s \in \{0,1\}^n} |s\rangle \right)$ indicates summation over all the possible bit strings of length $n$ represented by $s$ (which is $2^n$ in number, since upon doing the tensor product, that will be the possible bit strings over which the summation has to be run). Distributing the $|-\rangle$ and applying the oracle, we get the following:

$$ \begin{aligned} |\psi_2\rangle &= \frac{1}{\sqrt{2^n}} \left( \sum_{s \in \{0,1\}^n} U_f |s\rangle \otimes |-\rangle \right) \\ &= \frac{1}{\sqrt{2^n}} \left( \sum_{s \in \{0,1\}^n} (-1)^{f(s)} |s\rangle \otimes |-\rangle \right) \text{Applying the phase oracle identity from 22b} \end{aligned} \quad (27a) $$
Let us now focus only on the first term, since the second one is just for the phase oracle output. Now, applying the set of $n$ Hadamard gates,

$$ \begin{aligned} |\psi_3\rangle &= \frac{1}{\sqrt{2^n}} \left( H^{\otimes n} \sum_{s \in \{0,1\}^n} (-1)^{f(s)} |s\rangle \right) \\ &= \frac{1}{\sqrt{2^n}} \left( \sum_{s \in \{0,1\}^n} (-1)^{f(s)} H^{\otimes n} |s\rangle \right) \end{aligned} \qquad (28a) $$

Now, let's investigate the term $H^{\otimes n}|s\rangle$ in detail below. First of all, let's rephrase that $H|x\rangle = \frac{1}{\sqrt{2}}(|0\rangle + (-1)^x|1\rangle)$. Now, let's focus our attention on a particular bit string of length $n$, where the 1's occur at positions $n_1, n_2, ..., n_m$ and the remaining $(n-m)$ positions has 0s and the bit string looks like the following:

$$ |s\rangle = |00010011100....100\rangle $$

Now, it is a standard result that the action of $n$ Hadamard gates on a computational basis state is given by

$$ H^{\otimes n}|s\rangle = \frac{1}{\sqrt{2^n}} \sum_{y \in \{0,1\}^n} (-1)^{s \cdot y} |y\rangle, \qquad (29) $$

where $s \cdot y = \bigoplus_{i=1}^n s_i y_i$ denotes the bitwise dot product modulo 2.

Substituting this into $|\psi_3\rangle$ (and keeping the unchanged ancilla $|-\rangle$), we obtain

$$ |\psi_3\rangle = \frac{1}{\sqrt{2^n}} \sum_{s \in \{0,1\}^n} (-1)^{f(s)} \left( \frac{1}{\sqrt{2^n}} \sum_{y \in \{0,1\}^n} (-1)^{s \cdot y} |y\rangle \right) \otimes |-\rangle \qquad (30a) $$

$$ = \frac{1}{2^n} \sum_{y \in \{0,1\}^n} \left( \sum_{s \in \{0,1\}^n} (-1)^{f(s)+s \cdot y} \right) |y\rangle \otimes |-\rangle. \qquad (30b) $$

The amplitude of each $|y\rangle$ in the first $n$ qubits is therefore $\frac{1}{2^n} \sum_s (-1)^{f(s)+s \cdot y}$.

In particular, for the all-zero state $y = 0^n$, we have $s \cdot y = 0$ for all $s$, so the amplitude simplifies to

$$ \frac{1}{2^n} \sum_{s \in \{0,1\}^n} (-1)^{f(s)}. \qquad (31) $$

If $f$ is constant, $(-1)^{f(s)}$ is the same for all $s$, so the sum is $\pm 2^n$ and the amplitude is $\pm 1$ (probability 1 of measuring $0^n$).

If $f$ is balanced, the sum is 0 (probability 0 of measuring $0^n$).

Thus, measuring the first $n$ qubits yields $0^n$ if and only if $f$ is constant (and some non-zero string otherwise), determining the nature of $f$ with certainty using a single oracle query.

This achieves an exponential speedup compared to the classical case, which requires up to $2^{n-1} + 1$ queries in the worst case.
## 4.3. Bernstein-Vazirani Algorithm

### 4.3.1. The Problem:

The Bernstein-Vazirani algorithm addresses the problem of determining a secret bit string $S$ of length $n$. It uses an oracle that implements a function

$$f: \{0,1\}^n \to \{0,1\} \qquad (32)$$

defined as $f(X) = S \cdot X \mod 2$, where $\cdot$ denotes the bitwise dot product modulo 2. The task is to find the unknown string $S$. The circuit used is the same as that shown in Figure 6.

### 4.3.2. Computational Complexity for a Classical Computer:

For a classical computer, determining $S$ requires querying the function $f$ for each basis vector (i.e., strings with a single 1 and the rest 0s). Each query reveals one bit of $S$, so it takes exactly $n$ queries in the worst case.

### 4.3.3. Computational Complexity for a Quantum Computer Using the Bernstein-Vazirani Algorithm:

In the Bernstein-Vazirani algorithm, the initial state of the qubits is:

$$|\psi_0\rangle = |0\rangle^{\otimes n} \otimes |1\rangle \qquad (33)$$

After applying Hadamard gates to all qubits:

$$|\psi_1\rangle = H^{\otimes n}|0\rangle^{\otimes n} \otimes H|1\rangle = \left( \frac{1}{\sqrt{2^n}} \sum_{X \in \{0,1\}^n} |X\rangle \right) \otimes |-\rangle \qquad (34a)$$

Applying the oracle $U_f$, which uses phase kickback:

$$|\psi_2\rangle = \frac{1}{\sqrt{2^n}} \sum_X U_f |X\rangle \otimes |-\rangle = \frac{1}{\sqrt{2^n}} \sum_X (-1)^{f(X)} |X\rangle \otimes |-\rangle \qquad (35a)$$

$$= \frac{1}{\sqrt{2^n}} \sum_X (-1)^{S \cdot X} |X\rangle \otimes |-\rangle \qquad (35b)$$

Applying Hadamard gates again to the first $n$ qubits:

$$|\psi_3\rangle = \frac{1}{\sqrt{2^n}} H^{\otimes n} \left( \sum_X (-1)^{S \cdot X} |X\rangle \right) \otimes |-\rangle \qquad (36a)$$

Using the identity $H^{\otimes n}|X\rangle = \frac{1}{\sqrt{2^n}} \sum_Y (-1)^{X \cdot Y} |Y\rangle$, substituting yields:

$$|\psi_3\rangle = \frac{1}{2^n} \sum_Y \left( \sum_X (-1)^{S \cdot X + X \cdot Y} \right) |Y\rangle \otimes |-\rangle \qquad (37a)$$
<figure><img src="image_12.png" /><figcaption>Figure 7: Quantum Circuit for Quantum Fourier Transform</figcaption></figure>

The inner sum is $2^n$ if $Y = S$ (constructive interference) and 0 otherwise (destructive interference). Thus, the state collapses to $|S\rangle \otimes |-\rangle$, and measuring the first $n$ qubits yields $S$ with probability 1.

This determines $S$ with a single oracle query, providing a linear speedup over the classical requirement of $n$ queries.

## 4.4. Quantum Fourier Transform

The Quantum Fourier Transform (QFT) is a quantum algorithm that transforms a computational basis state $|j\rangle$ into a state where the phase encodes the value of $j$ (Refer to the Figure 7 for the circuit implementing the Quantum Fourier Transform).

### 4.4.1. The Problem:

The QFT is the quantum analog of the discrete Fourier transform, mapping an $n$-qubit state $|j\rangle$ (where $j$ is an integer from 0 to $2^n - 1$) to:

$$ \text{QFT}|j\rangle = \frac{1}{\sqrt{2^n}} \sum_{k=0}^{2^n-1} e^{2\pi ijk/2^n} |k\rangle. \qquad (38) $$

The phase $2\pi jk/2^n$ encodes the integer $j$ in the phases of the qubits.
### 4.4.2. Computational Complexity for a Classical Computer:

The classical Fast Fourier Transform (FFT) computes the DFT on $N = 2^n$ elements in $O(n2^n)$ time, which is exponential in $n$.

### 4.4.3. Computational Complexity for a Quantum Computer Using the Quantum Fourier Transform:

The QFT circuit for $n$ qubits applies rotations from the least significant qubit to the most significant. It uses controlled-$R_k$ gates, where $R_k = \begin{pmatrix} 1 & 0 \\ 0 & e^{2\pi i/2^k} \end{pmatrix}$.

Start with the state $|\psi_0\rangle = |j_1j_2\cdots j_n\rangle$ (binary representation of $j$).

For each qubit $l$ (from 1 to $n$, starting from the most significant): - Apply Hadamard gate $H$ to qubit $l$. - Apply controlled-$R_k$ gates from qubit $l$ to qubits $l+k$ for $k=1$ to $n-l$.

After all operations:

$$|\psi\rangle = \frac{1}{\sqrt{2^n}} \sum_{k=0}^{2^n-1} e^{2\pi i j k / 2^n} |k\rangle, \qquad (39a)$$

followed by SWAP gates (or relabeling) to reverse the qubit order.

For example, with 3 qubits and input $|101\rangle = |5\rangle$, the phases correspond to rotations of $5 \cdot 2\pi/8$, $10 \cdot 2\pi/8$, etc., matching the binary representation of $5/8 = 0.625$.

The inverse QFT (QFT†) reverses the process, recovering the original state from the phase-encoded value.

The circuit uses $O(n^2)$ gates, providing an exponential speedup over the classical FFT.

## 4.5. Shor's Algorithm

Shor's algorithm is a quantum algorithm for integer factorization that provides an exponential speedup over the best known classical algorithms. Given a composite integer $N$, the goal is to find a non-trivial factor of $N$.

The algorithm reduces the problem to finding the order (period) $r$ of a randomly chosen integer $a$ (coprime to $N$) in the multiplicative group modulo $N$, i.e., the smallest positive integer $r$ such that $a^r \equiv 1 \pmod{N}$. Once $r$ is known, factors can be found classically using $\text{gcd}(a^{r/2} \pm 1, N)$ if $r$ is even. The circuit for the algorithm is shown in the Figure 8.

### 4.5.1. The Problem:

Find the period $r$ of the function $f(x) = a^x \pmod{N}$.

### 4.5.2. Computational Complexity for a Classical Computer:

Classically, finding the order $r$ requires $O(\sqrt{N})$ operations in the worst case (using trial division or more advanced methods), which is exponential in the number of bits $\log N$.
<figure><img src="image_13.png" /><figcaption>Figure 8: Quantum Circuit for Shor's Algorithm</figcaption></figure>

### 4.5.3. Computational Complexity for a Quantum Computer Using Shor's Algorithm:

The quantum period-finding subroutine uses two registers: a control register of size $n \approx 2 \log_2 N$ qubits and a target register of size $\approx \log_2 N$ qubits.

The steps are as follows:

1. Initialize the state:

$$|\psi_0\rangle = |0\rangle^{\otimes n} \otimes |1\rangle. \qquad (40)$$

2. Apply Hadamard gates to the control register and $H$ to the target qubit (creating $|−\rangle$ is not needed here since the modular exponentiation oracle uses standard form):

$$|\psi_1\rangle = \frac{1}{\sqrt{2^n}} \sum_{x=0}^{2^n-1} |x\rangle \otimes |1\rangle. \qquad (41)$$

3. Apply the controlled modular exponentiation oracle $U_f$ defined by:

$$U_f|x\rangle|y\rangle = |x\rangle|a^x y \mod N\rangle. \qquad (42)$$

This yields (starting from $y = 1$):

$$|\psi_2\rangle = \frac{1}{\sqrt{2^n}} \sum_{x=0}^{2^n-1} |x\rangle \otimes |a^x \mod N\rangle. \qquad (43)$$
4. Apply the Quantum Fourier Transform (QFT) to the control register:

$$|\psi_3\rangle = \frac{1}{2^n} \sum_{k=0}^{2^n-1} \sum_{x=0}^{2^n-1} e^{2\pi i k x / 2^n} |k\rangle \otimes |a^x \text{ mod } N\rangle. \quad (44)$$

Due to the periodicity of $f(x)$ with period $r$, the amplitude in the control register is significant only when $k/2^n \approx j/r$ for integer $j$. Measurement of the control register yields a value $k$ such that $k/2^n$ is a good approximation to some $j/r$.

Using continued fraction expansion on $k/2^n$, one recovers candidate values for $r$. Repeating the quantum subroutine a few times and checking candidates yields the true period $r$ with high probability.

Once $r$ is found, classical post-processing extracts factors of $N$.

Shor's algorithm runs in polynomial time $O((\log N)^3)$ on a quantum computer, achieving an exponential speedup over classical factorization algorithms.

## 4.6. Grover's Algorithm

Grover's algorithm provides a quadratic speedup for unstructured search problems. Given an unstructured database of $N = 2^n$ items, the task is to find the (unique) item $w$ that satisfies a condition, implemented via an oracle function $f(x)$ where $f(x) = 1$ if $x = w$ and $f(x) = 0$ otherwise.

### 4.6.1. The Problem:

Find the marked item $w$ such that $f(w) = 1$.

### 4.6.2. Computational Complexity for a Classical Computer:

Classically, finding $w$ in an unstructured list requires $O(N)$ queries in the worst case (and $\Omega(N)$ on average), as each query eliminates only one possibility.

### 4.6.3. Computational Complexity for a Quantum Computer Using Grover's Algorithm:

The circuit uses $n$ qubits for the search space and one ancilla qubit. The steps are:

1. Initialize the state:

$$|\psi_0\rangle = |0\rangle^{\otimes n} \otimes |1\rangle. \quad (45)$$

2. Apply Hadamard gates to all qubits:

$$|\psi_1\rangle = H^{\otimes n}|0\rangle^{\otimes n} \otimes H|1\rangle = \frac{1}{\sqrt{2^n}} \sum_{x=0}^{2^n-1} |x\rangle \otimes |-\rangle. \quad (46a)$$

This creates a uniform superposition over all possible $x$.
3. Repeat the Grover iteration approximately $\lfloor \pi\sqrt{N}/4 \rfloor$ times:

* Apply the oracle $U_f$ that implements phase flip for the marked state:

$$U_f|x\rangle|y\rangle = |x\rangle|y \oplus f(x)\rangle, \qquad (47)$$

which, due to phase kickback on $|-\rangle$, effectively applies $(-1)^{f(x)}$ to $|x\rangle$:

$$|\psi_2\rangle = \frac{1}{\sqrt{2^n}} \sum_x (-1)^{f(x)} |x\rangle \otimes |-\rangle. \qquad (48)$$

* Apply the diffusion operator (Grover reflection) $G = 2|s\rangle\langle s| - I$, where $|s\rangle$ is the uniform superposition state:

$$G = H^{\otimes n}(2|0\rangle\langle 0|^{\otimes n} - I)H^{\otimes n}. \qquad (49)$$

This inverts amplitudes about the mean, amplifying the marked state.

Each iteration rotates the state vector in the plane spanned by the marked and unmarked states by an angle $\theta$ such that $\sin^2(\theta/2) = 1/N$, increasing the amplitude of $|w\rangle$.

After $O(\sqrt{N})$ iterations, the probability of measuring $|w\rangle$ in the first $n$ qubits approaches 1. Measurement yields the solution $w$ with high probability.

Grover's algorithm thus solves the search problem with $O(\sqrt{N})$ oracle queries, achieving a quadratic speedup over the classical $O(N)$ requirement.

## 4.7. Quantum Approximate Optimization Algorithm (QAOA)

In quantum computing, the Quantum Approximate Optimization Algorithm (QAOA) is a hybrid quantum-classical variational algorithm designed to solve combinatorial optimization problems. It is particularly suited for finding approximate solutions to NP-hard problems such as MaxCut, Max-SAT, and other constraint satisfaction problems. QAOA uses a parameterized quantum circuit (ansatz) to prepare a quantum state whose measurement statistics encode a candidate solution, and a classical optimizer adjusts the parameters to minimize (or maximize) the expected value of the problem's objective function. The algorithm was originally proposed in 2014 by Edward Farhi, Jeffrey Goldstone, and Sam Gutmann.[FGG14]

QAOA is a prominent example of a noisy intermediate-scale quantum (NISQ) algorithm and has been widely studied for its performance guarantees on certain problem classes and its potential near-term applicability.
### 4.7.1. Problem Encoding

The objective of QAOA is to find an approximate solution to a combinatorial optimization problem defined by a cost function $C(z)$ over bit strings $z \in \{0, 1\}^n$. The goal is to find $z^*$ that minimizes (or maximizes) $C(z)$.

The cost function $C(z)$ is typically expressed as a sum of local terms that act on a small number of bits. To implement QAOA on a quantum computer, the classical cost function is mapped to a problem Hamiltonian $H_C$ (also called the cost Hamiltonian), which is a diagonal operator in the computational basis:

$$H_C = \sum_k c_k P_k, \qquad (50)$$

where each $P_k$ is a Pauli-Z operator (or tensor product of Pauli-Zs) acting on the qubits involved in the k-th clause/term of $C(z)$, and $c_k$ are the corresponding coefficients. The expectation value $\langle H_C \rangle$ corresponds directly to the classical objective function value.

A mixing Hamiltonian $H_M$ is also defined, usually chosen as

$$H_M = \sum_{i=1}^{n} X_i, \qquad (51)$$

where $X_i$ is the Pauli-X operator on qubit $i$. This encourages exploration of the solution space by driving transitions between different bit strings.

### 4.7.2. The QAOA Ansatz

The QAOA circuit with $p$ layers (often called “level $p$”) consists of alternating applications of the cost and mixing unitaries, with variational parameters $\gamma = (\gamma_1, \dots, \gamma_p)$ and $\beta = (\beta_1, \dots, \beta_p)$:

$$|\gamma, \beta\rangle = U_M(\beta_p) U_C(\gamma_p) \cdots U_M(\beta_1) U_C(\gamma_1) |+\rangle^{\otimes n}, \qquad (52)$$

where

$$U_C(\gamma_k) = e^{-i\gamma_k H_C}, \qquad (53)$$

$$U_M(\beta_k) = e^{-i\beta_k H_M}. \qquad (54)$$

The initial state $|+\rangle^{\otimes n} = H^{\otimes n}|0\rangle^{\otimes n}$ is an equal superposition of all bit strings.

The algorithm proceeds as follows:

1. Choose an initial set of parameters $(\gamma, \beta)$.

2. Prepare the state $|\gamma, \beta\rangle$ on the quantum computer.

3. Measure the state repeatedly in the computational basis to estimate $\langle H_C \rangle = \langle \gamma, \beta | H_C | \gamma, \beta \rangle$.

4. Use a classical optimizer to update $(\gamma, \beta)$ to reduce $\langle H_C \rangle$ (for minimization problems).
5. Repeat until convergence.

The final approximate solution is obtained by measuring the optimized state and selecting the bit string with the highest probability (or the best observed $C(z)$).

As $p$ increases, QAOA can approximate the optimal solution arbitrarily well for certain problems (in the limit $p \to \infty$, it reaches the quantum adiabatic algorithm). In practice, small fixed $p$ (often $p = 1$ to $p \approx 10$) already provides good approximation ratios on many instances.

## 4.8. Variational Quantum Eigensolver (VQE)

In quantum computing, the variational quantum eigensolver (VQE) is a quantum algorithm for quantum chemistry, quantum simulations and optimization problems. It is a hybrid algorithm that uses both classical computers and quantum computers to find the ground state of a given physical system. Given a guess or ansatz, the quantum processor calculates the expectation value of the system with respect to an observable, often the Hamiltonian, and a classical optimizer is used to improve the guess. The algorithm is based on the variational method of quantum mechanics.

It was originally proposed in 2014, with corresponding authors Alberto Peruzzo, Alán Aspuru-Guzik and Jeremy O'Brien [P+14]. The algorithm has also found applications in quantum machine learning and has been further substantiated by general hybrid algorithms between quantum and classical computers. It is an example of a noisy intermediate-scale quantum (NISQ) algorithm.

### 4.8.1. Pauli Encoding

The objective of the VQE is to find a set of quantum operations that prepares the lowest energy state (or minima) of a close approximation to some target quantity or observable. While the only strict requirement for the representation of an observable is its efficiency in estimating its expectation values, it is often more straightforward if the operator has a compact or simple expression in terms of Pauli operators or tensor products of Pauli operators.

For a fermionic system, it is often most convenient to qubitize: that is to write the many-body Hamiltonian of the system using second quantization, and then use a mapping to write the creation-annihilation operators in terms of Pauli operators. Common schemes for fermions include Jordan-Wigner transformation, Bravyi-Kitaev transformation, and parity transformation.

### 4.8.2. The VQE Ansatz

The success of VQE heavily depends on the choice of the parameterized quantum circuit, known as the *ansatz* $U(\theta)$, which prepares the trial state

$$|\psi(\theta)\rangle = U(\theta)|0\rangle^{\otimes n}. \qquad (55)$$
<figure><img src="image_14.png" /></figure>

Notes:

* y parameters control problem encoding (phase separation)

* β parameters control mixing between computational basis states

* Typically p = 1-10 layers (higher p gives better approximation)

<caption>Figure 9: QAOA circuit for p=2 layers with algorithm flowchart and key equations.</caption>
The ansatz should be expressive enough to represent (or approximate) the true ground state while remaining shallow to mitigate noise on NISQ devices.

Popular choices include:

* Hardware-efficient ansatz: Alternating layers of single-qubit rotations (e.g., $R_y(\theta)$ and $R_z(\phi)$) and fixed entangling blocks (e.g., nearest-neighbor CNOT or CZ gates) tailored to the quantum hardware topology.

* Unitary Coupled Cluster (UCC): Especially UCCSD, which exponentiates cluster operators derived from classical quantum chemistry, providing chemically accurate results for molecular systems.

* Adaptive ansätze: Such as ADAPT-VQE or qubit-ADAPT-VQE, where the circuit is grown iteratively by selecting the most gradient-improving operator from a predefined pool at each step.

### 4.8.3. Cost Function and Measurement

The variational principle guarantees that

$$E(\boldsymbol{\theta}) = \langle\psi(\boldsymbol{\theta})|H|\psi(\boldsymbol{\theta})\rangle \ge E_0, \qquad (56)$$

with equality when $|\psi(\boldsymbol{\theta})\rangle$ is the true ground state. Minimizing $E(\boldsymbol{\theta})$ yields an upper bound to the ground-state energy $E_0$.

The Hamiltonian is expressed as a sum of Pauli strings:

$$H = \sum_{k=1}^{M} h_k P_k, \qquad (57)$$

so

$$E(\boldsymbol{\theta}) = \sum_{k=1}^{M} h_k \langle P_k \rangle_{\boldsymbol{\theta}}. \qquad (58)$$

Each expectation value $\langle P_k \rangle$ is estimated by preparing $|\psi(\boldsymbol{\theta})\rangle$ many times and measuring in the eigenbasis of $P_k$ (rotating qubits accordingly before measurement). Commuting Pauli terms can be grouped to reduce the number of circuits.

The hybrid optimization loop proceeds as:

1. Initialize parameters $\boldsymbol{\theta}$.

2. On the quantum device: prepare $|\psi(\boldsymbol{\theta})\rangle$ and measure to estimate $E(\boldsymbol{\theta})$.

3. On the classical optimizer: update $\boldsymbol{\theta}$ to reduce $E(\boldsymbol{\theta})$ (using gradient-free methods like COBYLA or SPSA, or parameter-shift rule for analytic gradients).

4. Repeat until convergence or shot budget exhaustion.
### 4.8.4. Advantages, Challenges, and Outlook

VQE is particularly well-suited for NISQ hardware because:

* Circuits are short and customizable.

* Measurement overhead can be mitigated by term grouping and error mitigation techniques.

* It naturally tolerates noise through classical post-processing.

Key challenges include:

* Barren plateaus in random or highly expressive ansätze, causing exponentially vanishing gradients.

* Exponential measurement cost for high precision (mitigated by advanced sampling strategies).

* Ansatz selection and initialization bias.

Recent developments incorporate symmetry constraints, measurement reduction techniques, and adaptive growth to improve scalability. VQE has demonstrated chemical accuracy for small molecules (e.g., H₂, LiH, BeH₂) on current quantum hardware and remains a leading candidate for near-term quantum advantage in quantum chemistry, materials science, and optimization problems mapped to qubit Hamiltonians.

## 4.9. Harrow-Hassidim-Lloyd (HHL) Algorithm

The Harrow-Hassidim-Lloyd (HHL) algorithm is a quantum algorithm for solving linear systems of equations $Ax = b$, where $A$ is an $N \times N$ sparse Hermitian matrix, $b$ is a known vector, and the goal is to prepare a quantum state $|x\rangle$ proportional to the solution vector $x$.

### 4.9.1. The Problem:

Given access to a unitary oracle encoding $A$ and a state $|b\rangle$ (normalised version of $b$), prepare a state $|x\rangle = |x\rangle/\|x\|$ with efficiency exponential in the dimension $\log N$.

### 4.9.2. Computational Complexity for a Classical Computer:

Solving a dense linear system classically requires $O(N^3)$ time using Gaussian elimination, or $O(N^2)$ for sparse matrices with iterative methods. For $N = 2^n$, this is exponential in $n$.
<figure><img src="image_15.png" /></figure>

<figure><img src="image_16.png" /></figure>

Notes: Ansatz choice crucial. Common optimizers: COBYLA, SPSA, gradient descent.

<caption>Figure 10: VQE circuit with algorithm flowchart and key equations.</caption>
### 4.9.3. Computational Complexity for a Quantum Computer Using the HHL Algorithm:

The HHL algorithm uses three registers: - Clock register: $n_c$ qubits, initialised to $|0\rangle^{\otimes n_c}$. - Ancilla register: 1 qubit, initialised to $|1\rangle$. - System register: $n$ qubits, initialised to $|b\rangle$.

The steps are:

1. Apply Hadamard gates to the clock and ancilla registers:

$$|\psi_1\rangle = \frac{1}{\sqrt{2^{n_c}}} \sum_{t=0}^{2^{n_c}-1} |t\rangle \otimes |-\rangle \otimes |b\rangle. \qquad (59)$$

2. Apply quantum phase estimation (QPE) with the unitary $e^{iAt_0}$ (where $t_0$ is a scaling factor) on the clock register, controlled by the system register. This maps eigenvalues $\lambda_j$ of A to the clock register (assuming $|b\rangle = \sum_j \beta_j |\lambda_j\rangle$):

$$|\psi_2\rangle = \frac{1}{\sqrt{2^{n_c}}} \sum_{t=0}^{2^{n_c}-1} \sum_j \beta_j |t\rangle |\tilde{\lambda}_j\rangle \otimes |\lambda_j\rangle, \qquad (60)$$

where $|\tilde{\lambda}_j\rangle$ approximates $\lambda_j$.

3. Apply a controlled rotation on the ancilla qubit conditioned on the clock register to encode $1/\lambda_j$:

$$R_y(\theta_j) = \begin{pmatrix} 1 & 0 \\ 0 & e^{i\theta_j} \end{pmatrix}, \quad \theta_j = 2 \arcsin(C/\tilde{\lambda}_j), \qquad (61)$$

with C chosen such that $C \le \kappa$ (condition number of A). This yields an ancilla state proportional to $\sum_j \beta_j / \lambda_j$. The full state becomes:

$$|\psi_3\rangle \propto \sum_j \beta_j |\tilde{\lambda}_j\rangle \otimes \left( |\lambda_j\rangle + \frac{C}{\lambda_j} |1\rangle \right). \qquad (62)$$

4. Apply inverse QPE to uncompute the clock register.

5. Measure the ancilla qubit. If it is $|1\rangle$ (post-selected with probability $\propto \|\mathbf{x}\|^2$), the system register collapses to the normalised solution state $|x\rangle$.

The algorithm runs in time $O(\log N \cdot \kappa^2/\epsilon)$ under suitable sparsity and conditioning assumptions, providing an exponential speedup over classical methods for preparing $|x\rangle$ (not for extracting all classical components of $\mathbf{x}$).

Note that HHL is BQP-complete and offers speedup primarily when the solution state $|x\rangle$ is used as input for further quantum computations.
<figure><img src="image_17.png" /></figure>

<figure><img src="image_18.png" /></figure>

**Key Equations:**

Problem: Solve $Ax = b$

**Assumptions:**

* A is Hermitian

* A is s-sparse

* $\kappa = \lambda_{max}/\lambda_{min}$ (condition number)

**QPE extracts eigenvalues:**

$$A|\psi_i\rangle = \lambda_i|\psi_i\rangle$$

$$|b\rangle = \sum_j \beta_j |\psi_j\rangle$$

**After QPE:**

$$|b\rangle \otimes |0\rangle \rightarrow \sum_j \beta_j |\psi_j\rangle \otimes |\lambda_j\rangle$$

**Rotation implements $\lambda^{-1}$:**

$$R(\lambda^{-1}|\lambda\rangle|0\rangle \rightarrow |\lambda\rangle(\sqrt{1-C^2/\lambda^2}|0\rangle + C/|1\rangle)$$

(C: normalization constant)

**Result:**

$$|x\rangle \propto A^{-1}|b\rangle = \sum_j \beta_j \lambda_j^{-1} |\psi_j\rangle$$

**Complexity:**

**Classical:**

$$O(N^2\kappa \log(1/\epsilon))$$

**HHL:**

$$O(\log(N)\sqrt{\kappa^2 \log(1/\epsilon)})$$

Exponential speedup in N!

**Challenges:**

* Quantum RAM required

* State preparation

* Condition number $\kappa$

* Post-selection: $P \sim 1/\kappa^2$

<caption>Figure 11: HHL circuit with algorithm flowchart and key equations.</caption>
## 4.10. Variational Quantum Linear Solver

The Variational Quantum Linear Solver (VQLS) is a variational quantum algorithm that utilizes the framework of the Variational Quantum Eigensolver (VQE) to solve systems of linear equations $Ax = b$ more efficiently than classical algorithms in certain parameter regimes. Given a matrix $A$ and a vector $b$, the goal is to prepare a normalized quantum state $|x\rangle \propto |x\rangle$ such that $A|x\rangle \propto |b\rangle$.

The output is similar to that of the Harrow-Hassidim-Lloyd (HHL) algorithm, but unlike HHL—which offers exponential speedup yet requires fault-tolerant quantum hardware with many qubits and deep circuits—VQLS is designed for near-term NISQ devices due to its shallow, parameterized ansatz and hybrid quantum-classical nature.

To begin, the inputs to the algorithm are: - The matrix $A$, decomposed into a linear combination of unitaries (LCU):

$$A = \sum_{n} c_{n} A_{n}, \qquad (63)$$

where each $A_n$ is unitary and the $c_n$ are complex coefficients. - A unitary $U$ that prepares the (normalized) state $|b\rangle = U|0\rangle^{\otimes n}$.

The algorithm follows the standard variational paradigm: a parameterized quantum circuit (ansatz) $V(\theta)$ prepares a trial state $|\psi(\theta)\rangle = V(\theta)|0\rangle^{\otimes n}$, and a classical optimizer adjusts $\theta$ to minimize a cost function whose global minimum corresponds to the desired normalized solution $|x\rangle$.

### 4.10.1. Cost Function

The natural cost function is the residual error:

$$C(\theta) = 1 - \frac{|\langle b | A | \psi(\theta) \rangle|^2}{\langle b | b \rangle \langle \psi(\theta) | A^\dagger A | \psi(\theta) \rangle}. \qquad (64)$$

However, direct evaluation requires tomography. Instead, VQLS uses local and global cost functions that can be estimated efficiently via Hadamard tests.

A common practical choice is the *local* cost function based on the LCU decomposition:

$$C_L(\theta) = \frac{1}{2} \left( 1 - \sum_{n,m} \Re \left[ c_n c_m^* \langle \psi(\theta) | A_n^\dagger A_m | \psi(\theta) \rangle \langle b | A_n^\dagger A_m | b \rangle^* \right] \right). \qquad (65)$$

Each term $\langle \psi | A_n^\dagger A_m | \psi \rangle$ and $\langle b | A_n^\dagger A_m | b \rangle$ is measured using Hadamard-test subcircuits (controlled-$A_n^\dagger A_m$ with an ancilla).

The circuit shown in the figure illustrates one such Hadamard test: the ancilla is prepared in $|+\rangle$ or $|+i\rangle$ to extract real/imaginary parts, and the probability of measuring $|0\rangle$ on the ancilla gives the desired overlap.
### 4.10.2. Algorithm Workflow

1. Preprocess A into LCU form $\sum c_n A_n$ (possible for sparse or structured matrices).

2. Choose a parameterized ansatz $V(\theta)$ (e.g., hardware-efficient, problem-inspired, or ADAPT-VQE style).

3. Initialize parameters $\theta$.

4. Repeat until convergence:

* For each pair $(n, m)$, run Hadamard-test circuits to estimate $\Re[\langle\psi(\theta)|A_n^\dagger A_m|\psi(\theta)\rangle]$ and the corresponding $|b\rangle$ overlaps.

* Compute $C_L(\theta)$ classically.

* Use a classical optimizer (e.g., SPSA, COBYLA, Adam) to update $\theta$ and reduce $C_L$.

5. Upon convergence (when $C_L < \epsilon$), prepare $|\psi(\theta^*)\rangle$, which approximates the normalized solution $|x\rangle$.

### 4.10.3. Complexity and Advantages

The runtime scales as $O(\kappa^2/\epsilon^2)$ in the condition number $\kappa$ of A and desired precision $\epsilon$, with each iteration requiring $O(1)$ depth circuits (depending on ansatz and LCU implementation). While HHL achieves exponential speedup in dimension, VQLS offers polynomial speedup in certain regimes and is feasible on current NISQ hardware for small-to-moderate systems.

VQLS is particularly promising for applications where the solution state $|x\rangle$ is needed for further quantum processing (e.g., electromagnetic scattering, fluid dynamics, or as a subroutine in larger quantum algorithms).

## 5. Transverse Field Ising Model & Quantum Annealing

The transverse-field Ising model (TFIM) is a fundamental quantum many-body model that extends the classical Ising model by incorporating a transverse magnetic field, introducing quantum effects due to non-commuting spin operators. It serves as a prototypical system for studying quantum phase transitions, symmetry breaking, and exact solvability in quantum physics.

The model describes a lattice of spins (typically spin-1/2 particles) with nearest-neighbor interactions along the z-direction and an external field along the x-direction. Its Hamiltonian is:

$$H = -J \sum_{\langle i,j \rangle} Z_i Z_j - Jg \sum_j X_j, \qquad (66)$$
<figure><img src="image_19.png" /></figure>

<figure><img src="image_20.png" /></figure>

Note: Hadamard test evaluates $(V\dagger(\theta)UV(\theta))$ for various unitaries $U$ to compute cost function components.

<caption>Figure 12: VQLS circuit and ansatz structure.</caption>
<figure><img src="image_21.png" /></figure>

Notes: VQLS uses variational optimization similar to VQE.
Suitable for NISQ devices. Ansatz choice is critical for performance.

<caption>Figure 13: VQLS algorithm flowchart.</caption>
VQLS vs HHL Comparison

Variational vs Exact Quantum Linear Solvers

<table><thead><tr><td>Feature</td><td>HHL Algorithm</td><td>VQLS Algorithm</td></tr></thead><tbody><tr><td>Device Requirements</td><td>Fault-tolerant quantum computer required</td><td>NISQ-friendly (shallow circuits)</td></tr><tr><td>Quantum Speedup</td><td>Exponential in system size N</td><td>Problem-dependent (no guaranteed speedup)</td></tr><tr><td>Qubit Count</td><td>log(N) + ancilla qubits</td><td>log(N) qubits (no ancilla)</td></tr><tr><td>Circuit Depth</td><td>Poly(log N, κ) (deep circuits)</td><td>Shallow and trainable (variational)</td></tr><tr><td>Output</td><td>Quantum state |x⟩ (requires tomography)</td><td>Classical parameters (direct measurement)</td></tr><tr><td>Condition Number κ</td><td>Success prob ~ 1/κ² (challenging for large κ)</td><td>Can handle through optimization</td></tr><tr><td>Implementation</td><td>Needs QPE, QFT (complex gates)</td><td>Uses Hadamard test (simpler gates)</td></tr></tbody></table>

Summary:

<caption>Figure 14: VQLS vs HHL comparison.</caption>
where $J > 0$ is the ferromagnetic coupling strength, $g$ is the dimensionless transverse field strength, $Z_i$ and $X_i$ are Pauli operators on site $i$, and the sum $\langle i, j \rangle$ is over nearest neighbors. (For antiferromagnetic coupling, $J < 0$.)

The TFIM exhibits a global $Z_2$ symmetry under the operator $\prod_j X_j$, which flips all spins. In one dimension, it is exactly solvable via the Jordan-Wigner transformation, mapping spins to non-interacting fermions, revealing a spectrum of quasiparticle excitations.

## 5.1. Phases and Phase Transitions

In 1D: - For $|g| < 1$ (ordered/ferromagnetic phase): The ground state is twofold degenerate, breaks $Z_2$ symmetry, and exhibits long-range order. The energy gap closes linearly as $\Delta = 2|J|(1 - |g|)$. - For $|g| > 1$ (disordered/paramagnetic phase): The ground state is unique, preserves symmetry, and aligns spins along the x-direction in the large-$g$ limit. Gap: $\Delta = 2|J|(|g| - 1)$. - At $|g| = 1$ (critical point): The system is gapless, described by the Ising conformal field theory with central charge $c = 1/2$, marking a second-order quantum phase transition.

Kramers-Wannier duality relates the model at $g$ to one at $1/g$, interchanging ordered and disordered phases.

In higher dimensions (e.g., 2D), the model remains integrable under certain conditions and is used to study quantum criticality and topological phases.

## 5.2. Relevance to Quantum Computing

The TFIM is a benchmark for quantum simulations on platforms like trapped ions or superconducting qubits, testing quantum advantage in many-body physics. Its mappings to free fermions aid in exploring entanglement, quantum information propagation, and Majorana modes. In quantum annealing, the TFIM Hamiltonian drives the optimization process (see below).

## 5.3. Quantum Annealing

Quantum annealing (QA) is a metaheuristic optimization technique that leverages quantum fluctuations to find the global minimum of a complex objective function, particularly for problems with rugged energy landscapes like spin glasses or NP-hard combinatorial optimizations (e.g., Max-Cut, SAT, traveling salesman).

Proposed as a quantum analog of simulated annealing, QA exploits quantum tunneling to escape local minima more efficiently than classical thermal hopping, especially in landscapes with tall, thin barriers.

## 5.4. Principles and Adiabatic Theorem

QA starts with the system in the ground state of an initial "driver" Hamiltonian (e.g., a transverse field inducing superposition). The Hamiltonian evolves slowly to the "problem"
Hamiltonian, whose ground state encodes the optimal solution. By the adiabatic theorem, if the evolution is sufficiently slow, the system remains in the instantaneous ground state, ending in the desired minimum.

The time-dependent Hamiltonian is typically:

$$H(t) = A(t)H_D + B(t)H_P, \qquad (67)$$

where $H_D$ is the driver (e.g., $-\sum_i X_i$), $H_P$ is the problem Hamiltonian (e.g., classical Ising $\sum_{ij} J_{ij} Z_i Z_j + \sum_i h_i Z_i$), $A(t)$ decreases from 1 to 0, and $B(t)$ increases from 0 to 1 over time $t \in [0, T]$. The minimal gap during evolution determines the required $T$ for adiabaticity.

Quantum tunneling probability through a barrier is $e^{-\sqrt{\Delta w}/\Gamma}$ (with height $\Delta$, width $w$, field $\Gamma$), contrasting thermal $e^{-\Delta/k_B T}$, enabling faster traversal of certain barriers.

## 5.5. Use of the Transverse Field Ising Model

QA often employs the TFIM as the framework: the transverse field $g \sum X_j$ acts as the tunneling term (non-commuting with $H_P$), gradually reduced to zero, allowing the system to anneal into the classical ground state.

## 5.6. Quantum Processor Topologies

D-Wave quantum annealers implement Quantum Annealing (QA) on physical hardware with specific qubit interconnection topologies. These topologies define the native connectivity of the processor and significantly impact the efficiency of minor embedding. The topology determines how naturally a problem graph can be mapped onto the hardware; higher connectivity reduces the need for auxiliary qubits to form "chains," thereby allowing larger and denser problems to be solved with higher fidelity.

* **Chimera Topology**: Used in systems such as the D-Wave 2000Q. It is organized as a lattice of unit cells, each containing 8 qubits in a $K_{4,4}$ bipartite configuration (refer to Figure 15 for two different ways of representing the unit cell of Chimera topology). With a qubit degree of $d = 6$, the Chimera architecture often requires long qubit chains for dense problems, which can increase the susceptibility to thermal noise and calibration errors. The connection between the unit cells is shown in Figure 16. Figure 17 and Figure 18 present the simplified diagram and a summary of the Chimera topology, respectively.
<figure><img src="image_22.png" /><figcaption>Figure 15: Two Different Representations of 8-qubit Chimera unit with Qubits and Couplers</figcaption></figure>

<figure><img src="image_23.png" /><figcaption>Figure 16: Coupling Connections Between the Chimera Cells</figcaption></figure>
<figure><img src="image_24.png" /><figcaption>Figure 17: Simplified Connection diagram of Chimera cells</figcaption></figure>
<figure><img src="image_25.png" /><figcaption>Figure 18: Chimera Topology Summary</figcaption></figure>

* **Pegasus Topology:** Introduced with the D-Wave Advantage system (5000+ qubits).
Pegasus ($P_N$) significantly improves connectivity by introducing internal, external, and "odd" couplers. With a qubit degree of $d = 15$ (specifically the $P_{12}$ architecture), it reduces embedding overhead and allows for the native representation of more complex graphs compared to Chimera. Figure 19 and Figure 20 present the simplified diagram and a summary of the Pegasus topology, respectively.

<figure><img src="image_26.png" /><figcaption>Figure 19: Simplified Connection diagram of Pegasus cells</figcaption></figure>
<figure><img src="image_27.png" /><figcaption>Figure 20: Pegasus Topology Summary</figcaption></figure>

* **Zephyr Topology:** The latest architecture designed for the Advantage2 system. Zephyr ($Z_N$) further enhances connectivity with a qubit degree of $d = 20$ (e.g., in $Z_{16}$ implementations). This topology offers the highest density to date, natively supporting larger complete subgraphs ($K_{16}$) and minimizing the chain-length requirements for complex, real-world optimization tasks. Figure 21 and Figure 22 present the simplified
diagram and a summary of the Zephyr topology, respectively.

<figure><img src="image_28.png" /></figure>

<figure><img src="image_29.png" /><figcaption>Figure 21: Simplified Connection diagram of Zephyr cells</figcaption></figure>
<figure><img src="image_30.png" /><figcaption>Figure 22: Zephyr Topology Summary</figcaption></figure>

The *working graph*—the set of qubits and couplers available after post-fabrication
calibration—is typically a subgraph of the full theoretical topology due to manufacturing
yield. D-Wave’s Ocean SDK automates the minor embedding process to map arbitrary
problem graphs onto these specific hardware geometries.

5.7. Applications and Implementations

QA targets finding ground states of disordered systems and solving encoded NP-complete problems. Commercial implementations include D-Wave processors (e.g., D-Wave Advantage with over 5000 qubits), using superconducting flux qubits. Applications span machine learning, finance (portfolio optimization), drug discovery, and logistics. Hybrid quantum-classical methods enhance scalability.

Experimental evidence shows QA outperforming simulated annealing in specific instances,
though universal speedup remains debated.

6. Exploration of Further Possibilities

This section examines the potential of quantum computing to enhance mathematical modeling, building on current research to propose innovative applications.

## 6.1. Quantum Collaborative Filtering for Recommendation Systems

A key area for quantum optimization lies in a new class of problems beyond traditional
combinatorial optimization. A particularly promising application is in collaborative filtering
for large-scale recommendation systems [KP17, WKS15]. While modern neural networks
excel at this task, their scalability is limited by the immense size of user and item embeddings,
leading to high computational and energy costs [CAS16]. A quantum approach offers a
compelling alternative.

This model operates as a hybrid quantum-classical system built on the principles of
a Variational Quantum Eigensolver (VQE)-like algorithm [P+14, MRBAG16]. The core
idea is to represent users and items by encoding their respective features into the quantum
states of individual qubits. For a given user-item pair, the complex, non-linear relationships
and preferences are not captured through classical embeddings, but through quantum
entanglement generated by a parameterized quantum circuit, or ansatz [CAB+21].

The parameters of this ansatz are classically optimized using an algorithm like SPSA
[Spa98] to minimize a cost function. This cost function measures the discrepancy between the
circuit's output (the predicted preference) and known user-item preference scores. Through
this process, the quantum circuit effectively learns the underlying preference relationship.
The primary advantage of this approach lies in the exponential Hilbert space of qubits
(2ⁿ dimensional), which theoretically allows n qubits to represent correlations that would
require O(2ⁿ) classical parameters [BWP+17, SP18]. However, realizing this advantage in
practice depends on circuit trainability, the absence of barren plateaus, and problem structure
[CAB+21].
### 6.1.1. Mathematical Framework

**Feature Encoding.** Let $\mathcal{U} = \{u_1, u_2, \dots, u_M\}$ denote the set of $M$ users and $\mathcal{I} = \{i_1, i_2, \dots, i_N\}$ denote the set of $N$ items. For a user $u \in \mathcal{U}$ with feature vector $\mathbf{f}_u \in \mathbb{R}^{d_u}$ and an item $i \in \mathcal{I}$ with feature vector $\mathbf{f}_i \in \mathbb{R}^{d_i}$, we encode these classical features into quantum states using angle encoding. We allocate $n_u$ qubits for user encoding and $n_i$ qubits for item encoding, where $n_u \ge \lceil \log_2(d_u) \rceil$ and $n_i \ge \lceil \log_2(d_i) \rceil$. Features are first normalized to $[0, 1]$ and mapped to qubit indices. The encoded states are:

$$|\psi_u(\mathbf{f}_u)\rangle = \bigotimes_{j=1}^{n_u} \left( \cos\left(\frac{\pi \tilde{f}_u^{(j)}}{2}\right) |0\rangle + \sin\left(\frac{\pi \tilde{f}_u^{(j)}}{2}\right) |1\rangle \right) \qquad (68)$$

$$|\psi_i(\mathbf{f}_i)\rangle = \bigotimes_{k=1}^{n_i} \left( \cos\left(\frac{\pi \tilde{f}_i^{(k)}}{2}\right) |0\rangle + \sin\left(\frac{\pi \tilde{f}_i^{(k)}}{2}\right) |1\rangle \right) \qquad (69)$$

where $\tilde{f}_u^{(j)}$ and $\tilde{f}_i^{(k)}$ represent the mapped features: if $j \le d_u$, then $\tilde{f}_u^{(j)} = f_u^{(j)}$; otherwise $\tilde{f}_u^{(j)} = 0$ (padding). Both states are normalized: $\langle\psi_u|\psi_u\rangle = \langle\psi_i|\psi_i\rangle = 1$.

**Parameterized Quantum Circuit (Ansatz).** The combined initial state is $|\psi_0\rangle = |\psi_u\rangle \otimes |\psi_i\rangle$ operating on $n = n_u + n_i$ qubits, satisfying $\langle\psi_0|\psi_0\rangle = 1$. The parameterized quantum circuit $U(\theta)$ generates entanglement through a sequence of $L$ layers:

$$U(\theta) = \prod_{\ell=1}^{L} U_{\text{ent}}^{(\ell)} \cdot U_{\text{rot}}^{(\ell)}(\theta_{\ell}) \qquad (70)$$

where:

* $U_{\text{rot}}^{(\ell)}(\theta_{\ell}) = \bigotimes_{j=1}^{n} R_y(\theta_{\ell,j}^y) R_z(\theta_{\ell,j}^z)$ applies single-qubit rotations, where $R_y(\theta) = e^{-i\theta Y/2}$ and $R_z(\theta) = e^{-i\theta Z/2}$

* $U_{\text{ent}}^{(\ell)}$ applies entangling gates. We use CNOT gates in a ring topology: $U_{\text{ent}}^{(\ell)} = \prod_{j=1}^{n-1} \text{CNOT}_{j,j+1} \cdot \text{CNOT}_{n,1}$

The final quantum state is:

$$|\psi(\theta)\rangle = U(\theta)|\psi_0\rangle \qquad (71)$$

which remains normalized: $\langle\psi(\theta)|\psi(\theta)\rangle = 1$ since $U(\theta)$ is unitary.

**Measurement and Prediction.** The predicted preference score $\hat{r}_{ui}(\theta)$ is obtained by measuring an observable $\hat{O}$, chosen as a weighted sum of Pauli-Z operators:

$$\hat{O} = \sum_{j=1}^{n} w_j \sigma_j^z \qquad (72)$$
where $\sigma_j^z$ is the Pauli-Z operator on qubit j and $w_j = 1/n$ are uniform weighting coefficients. The expectation value yields:

$$ \langle \hat{O} \rangle (\boldsymbol{\theta}) = \langle \psi(\boldsymbol{\theta}) | \hat{O} | \psi(\boldsymbol{\theta}) \rangle \in [-1, 1] \qquad (73) $$

To map this to a rating scale $[r_{\min}, r_{\max}]$ (e.g., [0, 5] or [1, 5]), we apply an affine transformation:

$$ \hat{r}_{ui}(\boldsymbol{\theta}) = \frac{r_{\max} - r_{\min}}{2} \cdot \langle \hat{O} \rangle(\boldsymbol{\theta}) + \frac{r_{\max} + r_{\min}}{2} \qquad (74) $$

This ensures $\hat{r}_{ui}(\boldsymbol{\theta}) \in [r_{\min}, r_{\max}]$.

**Cost Function.** For a training set $\mathcal{D} = \{(u, i, r_{ui})\}$ of user-item pairs with known ratings $r_{ui} \in [r_{\min}, r_{\max}]$, the cost function to minimize is:

$$ \mathcal{L}(\boldsymbol{\theta}) = \frac{1}{|\mathcal{D}|} \sum_{(u, i, r_{ui}) \in \mathcal{D}} (\hat{r}_{ui}(\boldsymbol{\theta}) - r_{ui})^2 + \lambda \|\boldsymbol{\theta}\|^2 \qquad (75) $$

where $\lambda \ge 0$ is a regularization parameter preventing overfitting.

**SPSA Optimization.** The parameters $\boldsymbol{\theta} \in \mathbb{R}^{2nL}$ are updated using the Simultaneous Perturbation Stochastic Approximation (SPSA) algorithm [Spa98]:

$$ \boldsymbol{\theta}_{t+1} = \boldsymbol{\theta}_t - a_t \hat{\boldsymbol{g}}_t \qquad (76) $$

where the gradient estimate $\hat{\boldsymbol{g}}_t \in \mathbb{R}^{2nL}$ has components:

$$ \hat{g}_t^{(j)} = \frac{\mathcal{L}(\boldsymbol{\theta}_t + c_t \boldsymbol{\Delta}_t) - \mathcal{L}(\boldsymbol{\theta}_t - c_t \boldsymbol{\Delta}_t)}{2c_t \Delta_t^{(j)}}, \quad j = 1, \dots, 2nL \qquad (77) $$

with $\boldsymbol{\Delta}_t \in \{-1, +1\}^{2nL}$ being a random perturbation vector with elements drawn independently from a Rademacher distribution (i.e., $P(\Delta_t^{(j)} = \pm 1) = 1/2$). The step sizes decay according to:

$$ a_t = \frac{a}{(t+1+A)^\alpha}, \quad c_t = \frac{c}{(t+1)^\gamma} \qquad (78) $$

where $a, c > 0$ are tuning parameters, $A \ge 0$ is a stability constant, and typical choices are $\alpha = 0.602$ and $\gamma = 0.101$ as suggested by Spall [Spa98].

### 6.1.2. Training Algorithm

The complete training procedure for the quantum collaborative filtering model is summarized in Algorithm 1.
**Algorithm 1 Quantum Collaborative Filtering Training**

**Require:** Training set $\mathcal{D} = \{(u, i, r_{ui})\}$, number of qubits $n_u, n_i$, ansatz layers $L$, iterations $T$, SPSA parameters $a, c, A, \alpha, \gamma$, regularization $\lambda$

**Ensure:** Optimized parameters $\boldsymbol{\theta}^*$

1: Initialize parameters $\boldsymbol{\theta}_0 \sim \mathcal{U}(-\pi, \pi)^{2(n_u+n_i)L}$

2: **for** $t = 0$ to $T-1$ **do**

3: Compute step sizes: $a_t = a/(t+1+A)^\alpha, c_t = c/(t+1)^\gamma$

4: Sample perturbation: $\boldsymbol{\Delta}_t \sim \text{Rademacher}(\pm 1)^{2(n_u+n_i)L}$

5: Set $\boldsymbol{\theta}_t^+ = \boldsymbol{\theta}_t + c_t \boldsymbol{\Delta}_t$

6: Set $\boldsymbol{\theta}_t^- = \boldsymbol{\theta}_t - c_t \boldsymbol{\Delta}_t$

7: Compute $\mathcal{L}(\boldsymbol{\theta}_t^+)$ using Eq. (75)

8: Compute $\mathcal{L}(\boldsymbol{\theta}_t^-)$ using Eq. (75)

9: **for** $j = 1$ to $2(n_u + n_i)L$ **do**

10: $\hat{g}_t^{(j)} = \frac{\mathcal{L}(\boldsymbol{\theta}_t^+)-\mathcal{L}(\boldsymbol{\theta}_t^-)}{2c_t \Delta_t^{(j)}}$

11: **end for**

12: Update parameters: $\boldsymbol{\theta}_{t+1} = \boldsymbol{\theta}_t - a_t \hat{g}_t$

13: **end for**

14: **return** $\boldsymbol{\theta}^* = \boldsymbol{\theta}_T$

### 6.1.3. Computational Complexity Analysis

The quantum collaborative filtering approach offers potential advantages in terms of state space representation. Classical collaborative filtering methods, such as matrix factorization or neural collaborative filtering, typically require $O(M \cdot d_u + N \cdot d_i)$ parameters for user and item embeddings, where $M$ and $N$ are the numbers of users and items, respectively, and $d_u, d_i$ are embedding dimensions. For deep neural approaches, the parameter count can grow to $O(M \cdot d + N \cdot d + d^2 \cdot h)$ where $d$ is the embedding dimension and $h$ is the number of hidden layers.

In contrast, our quantum approach requires only $O(n \cdot L)$ parameters for the variational ansatz, where $n = n_u + n_i = O(\log(d_u) + \log(d_i))$ is the total number of qubits and $L$ is the number of layers. Since the quantum state space has dimension $2^n$, this allows for exponentially rich representational capacity with logarithmic qubit requirements. Specifically, to represent $d_u$ user features and $d_i$ item features, we need approximately $n_u = \lceil \log_2(d_u) \rceil$ and $n_i = \lceil \log_2(d_i) \rceil$ qubits.

Each circuit evaluation requires $O(n \cdot L)$ quantum gates. The SPSA optimization requires $O(1/\epsilon^2)$ iterations for convergence to an $\epsilon$-approximate solution, with each iteration requiring two circuit evaluations over the training set. The overall training complexity is thus $O(n \cdot L \cdot |\mathcal{D}|/\epsilon^2)$ for $|\mathcal{D}|$ training samples.

However, practical quantum advantage depends critically on:

1. **Circuit trainability:** Deep quantum circuits can suffer from barren plateaus where gradients vanish exponentially [CAB$^{+21}$].
2. **Noise resilience:** Near-term quantum devices have limited coherence times and gate fidelities.

3. **Classical optimization overhead:** The classical SPSA loop can dominate runtime for small problem sizes.

### 6.1.4. Experimental Validation

We implemented the proposed quantum collaborative filtering model using the Qiskit framework (version 0.45.0) and evaluated it on synthetic recommendation data. The experimental setup consisted of:

* **Model configuration:** $n_u = 3$ user qubits, $n_i = 3$ item qubits, $L = 2$ ansatz layers, yielding 36 trainable parameters.

* **Dataset:** 300 synthetic user–item ratings with $M = 30$ users, $N = 30$ items, latent dimension $k = 3$, and ratings in [0, 5]. User and item features (dimension $d_u = d_i = 5$) are generated via learned projections of latent factors: $\mathbf{f}_u = \sigma(\mathbf{z}_u W_u)$ and $\mathbf{f}_i = \sigma(\mathbf{z}_i W_i)$, where $\mathbf{z}_u, \mathbf{z}_i \in \mathbb{R}^k$ are latent vectors, $W_u, W_i \in \mathbb{R}^{k \times 5}$ are random projection matrices, and $\sigma(\cdot)$ denotes the sigmoid function. Ratings are generated as $r_{ui} = \text{scale}(\mathbf{z}_u^\top \mathbf{z}_i + \epsilon)$ with $\epsilon \sim \mathcal{N}(0, 0.5^2)$.

* **Data split:** 60% training (192 samples), 20% validation (48 samples), and 20% test (60 samples).

* **Optimization:** SPSA with $T = 50$ iterations, $a = 0.1$, $c = 0.1$, $A = 10$, $\alpha = 0.602$, $\gamma = 0.101$, and regularization parameter $\lambda = 0.01$.

* **Simulator:** Qiskit Aer statevector simulator with exact (noiseless) quantum state evolution.

The model achieved a test RMSE of approximately 0.85 on the 5-point rating scale, demonstrating the feasibility of learning user–item preference relationships using variational quantum circuits. Although the optimization objective is mean squared error (MSE) with $L_2$ regularization, performance on the test set is reported using root mean squared error (RMSE) for interpretability on the rating scale.

Figure 23 illustrates the convergence behavior during training. Both training and validation loss decrease steadily over iterations, with mild stochastic fluctuations characteristic of SPSA due to its simultaneous perturbation gradient approximation. The quantum approach demonstrates particular promise for scenarios with high-dimensional feature spaces but limited training data, where the exponential quantum state space can potentially capture complex user–item interactions more efficiently than classical embeddings. However, several challenges remain for practical deployment:
Quantum Collaborative Filtering Training Curve
Convergence over 50 SPSA Iterations

<figure><img src="image_31.png" /><figcaption>Figure 23: Training and validation loss (MSE + L₂ regularization) over 50 SPSA iterations for the quantum collaborative filtering model.</figcaption></figure>

* **Scalability to real datasets:** Current noisy intermediate-scale quantum (NISQ) devices support ~100–1000 qubits, limiting the feature dimensionality that can be directly encoded

* **Cold-start problem:** New users/items without features cannot be encoded without additional mechanisms

* **Inference cost:** Each prediction requires a full quantum circuit execution, which may be slower than classical matrix operations for small-scale problems

Future work will explore scaling to larger datasets such as MovieLens-1M, investigating hybrid classical-quantum architectures that combine the strengths of both paradigms, and studying the impact of quantum hardware noise on model performance.

## 6.2. Quantum Social Network: A Modeling Use Case

The Quantum Social Network (QSN) employs quantum computing to model social interactions by representing beliefs as quantum states, featuring the following unique characteristics:

* **Quantum Superposition of Beliefs:** Individuals can simultaneously hold contradictory opinions until measured.

* **Entanglement Between Users:** Strong connections foster quantum entanglement, correlating belief state collapses across users.
* **Measurement Collapse:** Public expressions of opinions cause belief states to collapse, impacting connected individuals.

* **Quantum Interference:** Conflicting influences may amplify or cancel, introducing complexity to the model.

* **Temporal Quantum Coherence:** Beliefs evolve over time while retaining their quantum properties.

This use case advances the modeling of social dynamics, offering insights into processes such as consensus formation and polarization, which may inform future optimization strategies.

### 6.2.1. Implementation and Simulation

The QSN is implemented using the Qiskit framework, integrated with NetworkX for classical network structures. The simulation leverages a Python class to manage quantum circuit construction and influence dynamics, executed on the Aer simulator with 1024 shots.

<figure><img src="image_32.png" /><figcaption>Figure 24: Visualization of Quantum Social Network Simulation Results. The plots include: (a) Social Network Topology (complete network with four users), (b) Consensus Evolution (final belief state probabilities), (c) Quantum Influence Strengths (heatmap), (d) Belief State Evolution (initial vs. final distributions), and (e) Consensus Analysis (metric changes).</figcaption></figure>
### 6.2.2. Results and Insights

The simulation results, presented in Figure 24, demonstrate the QSN’s modeling capabilities for the complete network topology in Experiment 2 (Echo Chamber Effect), chosen to study fully connected social dynamics:

* The “*Consensus Evolution*” plot reveals a dominant final state of (0000) with 423 occurrences, indicating strong negative consensus where all users align toward the —0) state (e.g., against or negative opinion).

* The influence heatmap shows varied interaction strengths, with notable connections between users 0-1 and 2-3.

* Belief state evolution shifts from a uniform initial distribution (due to superposition) to a peaked final distribution, with the “*Belief State Evolution*” plot showing a peak of 334 occurrences, driven by quantum interference.

* Consensus metrics indicate a final negative consensus of 0.4, polarization of 0.3, and belief diversity of 0.1 (from an initial near-zero diversity), consistent with an echo chamber effect in the fully connected network.

This use case highlights the ability of quantum computing to model complex social systems, providing a basis for future research into optimization challenges such as influence maximization or polarization control within quantum frameworks.

## 7. Concluding Remarks

Quantum computing represents a paradigm-shifting avenue for addressing mathematical optimization challenges that remain intractable for classical computational methods. By harnessing quantum mechanics principles including superposition, entanglement, and quantum tunneling, quantum algorithms demonstrate potential to solve NP-hard optimization problems with unprecedented efficiency and scalability. This comprehensive review systematically examines quantum optimization’s evolution from theoretical foundations to practical implementations, encompassing foundational algorithms such as Quantum Approximate Optimization Algorithm (QAOA), Quantum Annealing (QA), Variational Quantum Eigensolver (VQE), and hybrid quantum-classical frameworks including Variational Quantum Linear Solver (VQLS) and Harrow-Hassidim-Lloyd (HHL) algorithm.

The survey has highlighted the transformative potential of quantum computing across diverse application domains, ranging from collaborative filtering in recommendation systems to power network optimization, logistics, drug discovery, and quantum social network modeling. By encoding complex optimization problems into quantum states and leveraging the exponential dimensionality of Hilbert spaces, quantum approaches offer theoretical advantages that classical methods cannot replicate. However, the path toward practical quantum advantage is accompanied by significant challenges characteristic of the Noisy
Intermediate-Scale Quantum (NISQ) era. Issues such as quantum decoherence, limited gate fidelity, error correction overhead, restricted qubit connectivity, and the barren plateau phenomenon in variational algorithms necessitate continued innovation in both hardware architecture and algorithmic design.

Looking toward future research directions, Quantum Machine Learning (QML) stands at the intersection of quantum computing and artificial intelligence, offering potential breakthroughs in pattern recognition, feature extraction, and predictive modeling through quantum-enhanced learning algorithms. The application of quantum optimization to power network systems, including optimal power flow, unit commitment, and distributed energy resource management, presents immediate practical opportunities, as evidenced by recent advances in quantum interior-point methods and CVQLS-augmented approaches for smart grid optimization. Furthermore, the integration of quantum algorithms with emerging paradigms such as quantum-inspired tensor networks, topological quantum computing, and fault-tolerant quantum error correction codes will be instrumental in enabling the transition from NISQ devices to fully error-corrected quantum computers capable of delivering sustained quantum advantage.

This comprehensive survey provides a roadmap for researchers and practitioners seeking to navigate the complex landscape of quantum optimization. By bridging theoretical rigor with practical implementation considerations, this work serves as a foundational reference for understanding how quantum computational principles can be leveraged to transform optimization paradigms. As quantum hardware continues to mature and algorithmic innovations accelerate, the synergistic integration of quantum computing with classical optimization frameworks is expected to unlock new frontiers in computational problem-solving, reshaping our approach to some of the most challenging mathematical optimization problems across science, engineering, and industry.

## 8. Acknowledgement

In this article, the figures, Fig 9 to Fig 14 and Fig 17 to Fig 22 have been generated using Anthropic Claude Sonnet 4.5 and the authors would like to admit this and express their gratitude to the Claude team for creating the AI tools that enabled us to create these diagrams.

## References

[AAA$^{+24}$] Amira Abbas, Andris Ambainis, Brandon Augustino, Andreas Bärtschi, Harry Buhrman, Carleton Coffrin, Giorgio Cortiana, Vedran Dunjko, Daniel J. Egger, Bruce G. Elmegreen, Nicola Franco, Filippo Fratini, Bryce Fuller, Julien Gacon, Constantin Gonciulea, Sander Gribling, Swati Gupta, Stuart Hadfield, Raowel Heese, Gerhard Kircher, Thomas Kleinert, Thorsten Koch, Georgios Korpas, Steve Lenk, Jakub Marecek, Vanio Markov, Guglielmo Mazzola, Stefano Mensa, Naeimeh Mohseni, Giacomo Nannicini, Corey O'Meara, Elena Peña Tapia, Sebastian Pokutta, Manuel Proissl, Patrick Rebentrost, Emre Sahin, Benjamin C. B. Symons, Sabine Tornow, Víctor Valls, Stefan Woerner, Mira L. Wolf-Bauwens, Jon Yard,
Sheir Yarkoni, Dirk Zechiel, Sergiy Zhuk, and Christa Zoufal. Challenges and opportunities in quantum optimization. *Nature Reviews Physics*, 6:718, 2024

[AK25a] Farshad Amani and Amin Kargarian. Optimal power flow solution via noise-resilient quantum interior-point methods. *Electric Power Systems Research*, 240:111216, 2025.

[AK25b] Farshad Amani and Amin Kargarian. Quantum optimization for optimal power flow: Cvqls-augmented interior point method. *IEEE Transactions on Smart Grid*, 16(6):5040–5052, 2025.

[BBR01] J. Brooke, D. Bitko, and Thomas F. Rosenbaum. Quantum annealing of a disordered spin system. 2001.

[BPLC$^{+23}$] Carlos Bravo-Prieto, Ryan LaRose, M. Cerezo, Yigit Subasi, Lukasz Cincio, and Patrick J. Coles. Variational Quantum Linear Solver. *Quantum*, 7:1188, November 2023.

[BV97] Ethan Bernstein and Umesh Vazirani. Quantum complexity theory. *SIAM Journal on Computing*, 26(5):1411–1473, 1997.

[BWP$^{+17}$] Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, and Seth Lloyd. Quantum machine learning. *Nature*, 549(7671):195–202, 2017.

[CAB$^{+21}$] Marco Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C. Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R. McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, et al. Variational quantum algorithms. *Nature Reviews Physics*, 3(9):625–644, 2021.

[CAS16] Paul P. Covington, Jay Adams, and Emre Sargin. Deep neural networks for YouTube recommendations. In *Proceedings of the 10th ACM Conference on Recommender Systems*, pages 191–198, 2016.

[CB20] Sambuddha Chakrabarti and Ross Baldick. Look-ahead scopf (lascopf) for tracking demand variation via auxiliary proximal message passing (apmp) algorithm. *International Journal of Electrical Power & Energy Systems*, 116:105533, 2020.

[Cha09] Jeffrey R. Chasnov. Introduction to differential equations. Lecture Notes for MATH, The Hong Kong University of Science and Technology, 2009.

[Cha17] Sambuddha Chakrabarti. *Post-contingency states representation and redispatch for restoration in power systems operation*. PhD thesis, 2017.

[CKC$^{+14}$] Sambuddha Chakrabarti, Matt Kraning, Eric Chu, Ross Baldick, and Stephen Boyd. Security constrained optimal power flow via proximal message passing. In *2014 Clemson University Power Systems Conference*, pages 1–8, 2014.

[Cop94] Don Coppersmith. An approximate fourier transform useful in quantum factoring. Technical report, IBM Research Report RC 19642, 1994. Also available as arXiv:quant-ph/0201067.

[CV20] Carleton J. Coffrin and Marc Vuffray. The potential of quantum annealing for rapid solution structure identification. *Journal of Statistical Physics*, 181(2):445–463, 2020.

[Deu85] David Deutsch. Quantum theory, the church-turing principle and the universal quantum computer. *Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences*, 400:97–117, 1985.

[Dir30] Paul Dirac. *The Principles of Quantum Mechanics*. Clarendon Press, Oxford, 1930.

[DJ92] David Deutsch and Richard Jozsa. Rapid solution of problems by quantum computation. *Proceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences*, 439:553–558, 1992.

[FGG14] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028, 2014.

[Fre23] FreeCodeCamp.org. Quantum computing course: Math and theory for beginners. YouTube, 2023. Online video.

[Gro96] Lov K. Grover. A fast quantum mechanical algorithm for database search. In *Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing*, pages 212–219, Philadelphia, Pennsylvania, USA, 1996. ACM.

[GS18] David J. Griffiths and Darrell F. Schroeter. *Introduction to Quantum Mechanics*. Cambridge University Press, 3rd edition, 2018.

[Hal93] Paul R. Halmos. *Finite-Dimensional Vector Spaces*. Undergraduate Texts in Mathematics.
Springer, 1993.

[HHL09] Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for linear systems of equations. *Physical Review Letters*, 103(15), October 2009.

[HK25a] Milad Hasanzadeh and Amin Kargarian. D2-uc: A distributed-distributed quantum-classical framework for unit commitment, 2025.

[HK25b] Milad Hasanzadeh and Amin Kargarian. Distributed implementation of variational quantum eigensolver to solve qubo problems, 2025.

[HRK26] Milad Hasanzadeh, Ali Rajabi, and Amin Kargarian. A survey on applications of quantum computing for unit commitment, 2026.

[KL04] W. M. Kaminsky and S. Lloyd. Scalable architecture for adiabatic quantum computing of np-hard problems. In A. J. Leggett, B. Ruggiero, and P. Silvestrini, editors, *Quantum Computing and Quantum Bits in Mesoscopic Systems*, pages 229–236. Springer US, Boston, MA, 2004.

[KMG+18] Amin Kargarian, Javad Mohammadi, Junyao Guo, Sambuddha Chakrabarti, Masoud Barati, Gabriela Hug, Soumyya Kar, and Ross Baldick. Toward distributed/decentralized dc optimal power flow implementation in future electric power systems. *IEEE Transactions on Smart Grid*, 9(4):2574–2594, 2018.

[KN98] Tadashi Kadowaki and Hidetoshi Nishimori. Quantum annealing in the transverse Ising model. *Physical Review E*, 58(5):5355, 1998.

[KP17] Iordanis Kerenidis and Anupam Prakash. Quantum recommendation systems. In *Proceedings of the 8th Innovations in Theoretical Computer Science Conference (ITCS)*, pages 49:1–49:21, 2017.

[Luc14] Andrew Lucas. Ising formulations of many NP problems. *Frontiers in Physics*, 2:5, 2014.

[MDS+17] Daniel K. Molzahn, Florian Dörfler, Henrik Sandberg, Steven H. Low, Sambuddha Chakrabarti, Ross Baldick, and Javad Lavaei. A survey of distributed optimization and control algorithms for electric power systems. *IEEE Transactions on Smart Grid*, 8(6):2941–2962, 2017.

[Mon16] Ashley Montanaro. Quantum algorithms: an overview. *npj Quantum Information*, 2(1):1–8, 2016.

[MRBAG16] Jarrod R. McClean, Jonathan Romero, Ryan Babbush, and Alán Aspuru-Guzik. The theory of variational hybrid quantum-classical algorithms. *New Journal of Physics*, 18(2):023023, 2016.

[MRR+53] Nicholas Metropolis, Arianna W. Rosenbluth, Marshall N. Rosenbluth, Augusta H. Teller, and Edward Teller. Equation of state calculations by fast computing machines. *The Journal of Chemical Physics*, 21(6):1087–1092, 1953.

[NC02] Michael A. Nielsen and Isaac L. Chuang. *Quantum Computation and Quantum Information*. Cambridge University Press, 2002.

[P+14] Alberto Peruzzo et al. A variational eigenvalue solver on a photonic quantum processor. *Nature Communications*, 5:4213, 2014.

[Pre18] John Preskill. Quantum computing in the NISQ era and beyond. *Quantum*, 2:79, 2018.

[Sho94] Peter W. Shor. Algorithms for quantum computation: Discrete logarithms and factoring. In *Proceedings of the 35th Annual Symposium on Foundations of Computer Science (FOCS)*, pages 124–134. IEEE, 1994.

[SP18] Maria Schuld and Francesco Petruccione. *Supervised Learning with Quantum Computers*. Springer International Publishing, 2018.

[Spa98] James C. Spall. Implementation of the simultaneous perturbation algorithm for stochastic optimization. *IEEE Transactions on Aerospace and Electronic Systems*, 34(3):817–823, 1998.

[TAM+24] Byron Alexander Tasseff, Tameem Albash, Zachary Alexander Morrell, Marc Denis Vuffray, Andrey Lokhov, Sidhant Misra, and Carleton James Coffrin. On the emerging potential of quantum annealing hardware for combinatorial optimization. *Journal of Heuristics*, 30(5-6):34, 2024.

[WKS15] Nathan Wiebe, Ashish Kapoor, and Krysta M. Svore. Quantum algorithms for nearest-neighbor methods for supervised and unsupervised learning. *Quantum Information & Computation*, 15(3-4):316–356, 2015.