Introduction

Optimization begins with a simple act: choosing well.

A delivery company chooses routes. A power-grid operator chooses which generators to activate. A researcher chooses the parameters of a model. A compiler chooses how to arrange instructions. An investor chooses a portfolio under risk constraints. In each case, many possibilities are available, but not all are equally good. Optimization is the mathematical study of how to select a best, or at least a very good, option from a set of allowed options.

In its most compact form, an optimization problem can be written as

\[ \text{minimize } f(x) \quad \text{subject to } x \in \mathcal{F}. \]

Here \(x\) is a candidate solution, \(f(x)\) is the objective function, and \(\mathcal{F}\) is the feasible set: the set of solutions allowed by the rules of the problem. If we want to maximize profit, accuracy, or energy production, we can usually rewrite the problem as minimization by minimizing the negative of that quantity. For example, maximizing a profit \(P(x)\) is equivalent to minimizing \(-P(x)\).

This innocent-looking notation hides much of modern computation. If \(x\) is a real-valued vector and \(f\) is smooth and convex, powerful classical methods may solve the problem reliably. If \(x\) is a string of binary decisions and the feasible set is combinatorial, the number of possibilities can grow exponentially with problem size. A problem with \(n\) yes-or-no choices has \(2^n\) possible assignments. For \(n=100\), this is already far larger than the number of operations any ordinary exhaustive search could perform in practical time.

Quantum optimization studies whether quantum computation, quantum dynamics, or quantum-inspired models can help with such difficult optimization tasks. It is not a promise that quantum computers automatically solve hard problems efficiently. Rather, it is a research field asking a sharper question:

When, how, and under which assumptions can quantum resources improve optimization?

That question will guide this book.

Why optimization is hard

Some optimization problems are hard because they are large. Others are hard because they are structurally deceptive. A local improvement may lead toward a poor solution, while the global optimum lies behind a barrier of worse intermediate choices.

Consider the Max-Cut problem. We are given a graph: a collection of vertices connected by edges. The goal is to divide the vertices into two groups so that as many edges as possible cross between the groups. If each vertex represents a decision \(s_i \in \{-1,+1\}\), then an edge \((i,j)\) is cut when \(s_i\) and \(s_j\) have opposite signs. For an unweighted graph, one common objective is

\[ C(s)=\sum_{(i,j)\in E} \frac{1-s_i s_j}{2}, \]

where \(E\) is the set of edges. Maximizing \(C(s)\) means cutting as many edges as possible. This formulation is simple, but Max-Cut is NP-hard in general, meaning that a polynomial-time algorithm for solving all instances exactly would imply a polynomial-time algorithm for every problem in NP under standard many-one reductions (Garey and Johnson, 1979).

This does not mean every Max-Cut instance is difficult. Some are easy because of special graph structure. It also does not mean useful approximate solutions are impossible. Indeed, approximation algorithms, relaxations, heuristics, and problem-specific methods are central to classical optimization. The point is more subtle: many natural optimization problems have worst-case barriers that make them plausible candidates for alternative computational approaches.

Quantum optimization enters at this point—not as a replacement for classical optimization, but as an additional set of mathematical and physical tools.

What makes an approach “quantum”?

A quantum computer represents information using quantum states. The simplest unit is a qubit, whose pure state is a unit vector in a two-dimensional complex Hilbert space. In the computational basis, a qubit may be written as

\[ |\psi\rangle = \alpha |0\rangle + \beta |1\rangle, \]

where \(\alpha,\beta \in \mathbb{C}\) and

\[ |\alpha|^2 + |\beta|^2 = 1. \]

The numbers \(\alpha\) and \(\beta\) are called amplitudes. When the qubit is measured in the computational basis, the outcome is \(0\) with probability \(|\alpha|^2\) and \(1\) with probability \(|\beta|^2\). This is not merely ordinary randomness written in unfamiliar notation. Quantum states can interfere: amplitudes can add or cancel, and multi-qubit systems can exhibit entanglement, a form of correlation that cannot be represented as independent local states.

Quantum algorithms try to arrange this interference so that desirable answers become more likely when measured. Grover’s search algorithm is the classic example: for unstructured search over \(N\) possibilities, it finds a marked item using \(O(\sqrt{N})\) oracle queries, whereas a classical exhaustive search requires \(O(N)\) queries in the black-box setting (Grover, 1996). This quadratic improvement is important, but it also illustrates a recurring theme of this book: the speedup depends on the computational model and on the cost of implementing the oracle.

Optimization problems are often more structured than unstructured search. A quantum algorithm may exploit that structure through circuits, Hamiltonian evolution, quantum walks, variational ansätze, or annealing dynamics. Each approach has its own assumptions, strengths, and failure modes.

From objective functions to energy landscapes

A central idea in quantum optimization is to turn an optimization problem into an energy minimization problem.

In physics, a Hamiltonian is an operator representing the energy of a system. In quantum computing, Hamiltonians are also used as mathematical objects that generate time evolution or define the cost structure of an algorithm. If an optimization problem is encoded into a Hamiltonian \(H_C\), the goal is often to make the lowest-energy states of \(H_C\) correspond to optimal solutions of the original problem. The lowest-energy state is called a ground state.

For example, the Max-Cut objective above can be encoded using Pauli-\(Z\) operators. The Pauli-\(Z\) operator has eigenvalues \(+1\) and \(-1\), matching the binary variables \(s_i\). A cost Hamiltonian for Max-Cut can be written as

\[ H_C = \sum_{(i,j)\in E} \frac{I - Z_i Z_j}{2}. \]

Here \(Z_i\) means that \(Z\) acts on qubit \(i\), and \(I\) is the identity operator. Measuring a computational-basis state gives a bit string, and the energy associated with that bit string equals the number of cut edges. Depending on convention, one may maximize this cost Hamiltonian or minimize its negative. The important point is the mapping: bit strings become candidate solutions, and energies become objective values.

This Hamiltonian viewpoint is one of the bridges between optimization, quantum information, and statistical physics. It is also the foundation of adiabatic quantum computation, quantum annealing, and the Quantum Approximate Optimization Algorithm.

Three recurring algorithmic families

This book studies several families of quantum optimization methods. They are different enough that they should not be blurred together, but they share a common ambition: to use quantum dynamics or quantum computation to improve the search for good solutions.

The first family is based on quantum search and amplitude amplification. Grover’s algorithm is the prototype. If we can recognize good solutions with an oracle, amplitude amplification can increase the probability of measuring one of them. This gives a rigorous quadratic query improvement in the unstructured setting (Grover, 1996). Later chapters will show how this idea extends to minimum finding and subroutines inside larger algorithms.

The second family is based on adiabatic evolution and annealing. In adiabatic quantum computation, one begins with a Hamiltonian whose ground state is easy to prepare and slowly changes it into a problem Hamiltonian whose ground state encodes the answer. Under suitable spectral-gap and smoothness conditions, the adiabatic theorem implies that the system approximately remains in its instantaneous ground state. Farhi, Goldstone, Gutmann, and Sipser formulated this as a model of quantum computation for optimization-motivated problems (Farhi et al., 2000), and Aharonov and collaborators later proved that adiabatic quantum computation is polynomially equivalent to the standard circuit model under appropriate constructions (Aharonov et al., 2007). Quantum annealing is closely related but usually emphasizes physical implementation, finite temperature, open-system effects, and heuristic performance; an early influential formulation used a transverse-field Ising model to study quantum annealing dynamics (Kadowaki and Nishimori, 1998).

The third family is based on variational quantum algorithms. These are hybrid algorithms in which a quantum device prepares a parameterized state, measurements estimate an objective value, and a classical optimizer updates the parameters. The best-known example for combinatorial optimization is the Quantum Approximate Optimization Algorithm, or QAOA, introduced by Farhi, Goldstone, and Gutmann (Farhi et al., 2014). In QAOA, one alternates between applying a cost Hamiltonian and a mixing Hamiltonian. At low depth, QAOA is a structured heuristic. At increasing depth, it connects conceptually to adiabatic evolution, though practical performance depends strongly on instance structure, parameter selection, noise, and classical optimization.

These three families—search, annealing/adiabatic methods, and variational circuits—will appear repeatedly throughout the book. They are not the whole field, but they provide a useful map.

A necessary warning about quantum advantage

A central phrase in this field is quantum advantage. It means that a quantum method outperforms relevant classical methods according to a clearly defined task and resource measure. The phrase is easy to misuse.

For optimization, advantage can mean many different things. It might mean better asymptotic scaling, lower time-to-solution on a fixed benchmark distribution, better approximation quality under a fixed time budget, lower energy consumption, or improved performance as a subroutine inside a larger workflow. These are not equivalent claims. A quantum device beating a weak classical baseline is not strong evidence of fundamental advantage. A small instance solved faster by special-purpose hardware may not imply favorable scaling. Conversely, a quantum algorithm with a rigorous asymptotic improvement may still be impractical if its constants, oracle costs, data-loading assumptions, or fault-tolerance overheads are too large.

Rønnow and collaborators emphasized the importance of carefully defining and detecting quantum speedup, distinguishing several notions such as provable speedup, strong quantum speedup, and potential quantum speedup relative to specified classical competitors (Rønnow et al., 2014). This book follows that caution. We will ask not merely “Does the quantum method work?” but also “Compared with what, under which cost model, and on which instances?”

This caution is especially important in the current hardware era. Preskill described the present stage as the NISQ era—noisy intermediate-scale quantum technology—where devices may be scientifically valuable but are not yet error-corrected at large scale (Preskill, 2018). NISQ devices can explore new regimes, test heuristics, and inspire algorithms, but noise, limited connectivity, calibration errors, and measurement cost strongly affect optimization performance.

What this book assumes—and what it will build

This book is written for graduate and postgraduate readers, but it does not assume that you already know quantum optimization. It does assume mathematical maturity: comfort with linear algebra, probability, algorithms, and basic complexity language will help. When a concept is essential, we will define it before using it heavily.

We will build the subject in layers.

First, we study classical optimization. This is not optional background. Every serious claim about quantum optimization must be compared with classical baselines. Branch and bound, dynamic programming, simulated annealing, semidefinite programming, integer programming, local search, and modern metaheuristics are not historical footnotes; they are active competitors.

Second, we develop quantum computing foundations. We will study qubits, Hilbert spaces, measurements, unitary evolution, tensor products, entanglement, circuits, Hamiltonians, and Pauli operators. These are the grammar of the field.

Third, we examine complexity and limits. NP-hardness does not disappear when a problem is placed on a quantum computer. Quantum algorithms are powerful, but they obey their own complexity-theoretic boundaries. We will distinguish BQP, QMA, query complexity, circuit complexity, black-box lower bounds, and heuristic performance.

Fourth, we learn how to encode optimization problems into Hamiltonians. This includes Ising models, QUBO formulations, constraints, penalties, graph problems, satisfiability, coloring, routing, and portfolio optimization. Such encodings are never free: they may require additional qubits, large penalty coefficients, high locality, or complicated embeddings. Lucas’s survey of Ising formulations illustrates how broad this mapping program is, while also showing that formulation details matter greatly (Lucas, 2014).

Fifth, we study the major algorithmic paradigms: Grover search, amplitude amplification, quantum walks, adiabatic quantum computing, quantum annealing, QAOA, broader variational algorithms, and quantum linear-algebra methods relevant to continuous optimization. Along the way, we will discuss both rigorous results and heuristic practice.

Finally, we turn to hardware, benchmarking, applications, and frontier research. Quantum optimization today is not only an algorithmic theory; it is also an experimental and engineering enterprise. Superconducting annealers, gate-model processors, Rydberg atom arrays, photonic systems, coherent Ising machines, tensor-network simulations, and quantum-inspired classical methods all shape the research landscape. For example, Rydberg atom arrays have been used experimentally to study maximum independent set optimization on programmable neutral-atom platforms, illustrating how analog quantum systems can naturally encode certain graph problems (Ebadi et al., 2022).

A small example: why encoding choices matter

Suppose we want to solve a tiny binary optimization problem:

\[ \text{minimize } f(x_1,x_2)=x_1+x_2-2x_1x_2, \]

where \(x_1,x_2 \in \{0,1\}\).

We can evaluate all four possibilities:

\[ \begin{array}{c|c|c} x_1 & x_2 & f(x_1,x_2) \\ \hline 0 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{array} \]

The minima occur at \((0,0)\) and \((1,1)\). This objective rewards agreement between the two bits.

Quantum optimization often uses spin variables \(s_i \in \{-1,+1\}\) instead of binary variables \(x_i \in \{0,1\}\). A common conversion is

\[ x_i = \frac{1-s_i}{2}. \]

Thus \(x_i=0\) corresponds to \(s_i=+1\), and \(x_i=1\) corresponds to \(s_i=-1\). Substituting this transformation into the objective gives an equivalent expression in spin variables. This kind of conversion may look minor, but in larger problems it affects coefficients, constraints, hardware embedding, and energy scales. A poor formulation can make an otherwise reasonable algorithm perform badly.

This is why the book spends an entire chapter on translating optimization problems into Hamiltonians. The mapping is part of the algorithm, not a clerical step.

The role of negative results

A mature field does not consist only of success stories. Quantum optimization contains beautiful ideas, impressive experiments, and rigorous speedups in some models. It also contains limitations, failed expectations, difficult benchmarking debates, and strong classical competitors.

Variational quantum algorithms, for instance, can suffer from barren plateaus, where the optimization landscape becomes so flat that gradients are exponentially small in relevant system parameters under certain assumptions. McClean and collaborators gave influential results showing how barren plateaus can arise in quantum neural network training landscapes (McClean et al., 2018). This does not make all variational algorithms useless, but it warns us that ansatz design, locality, initialization, cost-function structure, and training strategy matter.

Similarly, quantum annealing may exploit tunneling in some landscapes, but thermal effects, small spectral gaps, control errors, and embedding overhead can limit performance. Quantum speedup claims must therefore be tested against strong classical algorithms, not against naive exhaustive search.

Negative results are not discouraging. They are navigational tools. They tell us where easy hopes fail and where sharper ideas are needed.

How to read the rest of the book

As you read, keep four questions active.

First: What is the optimization problem? Identify the variables, objective function, constraints, and performance metric.

Second: What is the quantum representation? Determine whether the method uses qubits, a Hamiltonian, an oracle, a circuit ansatz, an annealing schedule, a quantum walk, or another model.

Third: What is the comparison baseline? Ask which classical algorithms are being used for comparison and whether they are appropriate for the instance family.

Fourth: What is the claim? Is it a proof of asymptotic speedup, a heuristic improvement, a hardware demonstration, an approximation guarantee, or an empirical observation?

These questions will prevent confusion. They will also make the literature easier to read, because many disagreements in quantum optimization are not about algebra but about assumptions, benchmarks, and interpretation.

The promise of the field

Quantum optimization is compelling because it sits at a rare intersection. It connects the mathematics of hard decision problems, the physics of many-body systems, the engineering of quantum devices, and the practical needs of science and industry. It asks whether nature’s quantum rules can be shaped into computational methods that solve useful problems better than classical machines alone.

The honest answer today is mixed. Some quantum speedups are rigorous but apply to idealized models. Some hardware experiments are impressive but not yet decisive for broad practical advantage. Some variational methods are flexible but difficult to train. Some encodings are elegant on paper but costly in qubits or precision. At the same time, the field is advancing rapidly: algorithms are becoming more careful, experiments more programmable, benchmarks more demanding, and theory more precise.

This book will not treat quantum optimization as magic. It will treat it as a discipline: one with definitions, models, theorems, engineering constraints, empirical methods, open problems, and historical context. By the end, you should be able not only to recognize the major algorithms, but also to evaluate claims, design fair experiments, read current papers critically, and begin formulating your own research questions.

References

• Aharonov, D., van Dam, W., Kempe, J., Landau, Z., Lloyd, S., and Regev, O. (2007). “Adiabatic quantum computation is equivalent to standard quantum computation.” SIAM Journal on Computing, 37(1), 166–194. https://doi.org/10.1137/S0097539705447323

• Ebadi, S., Wang, T. T., Levine, H., Keesling, A., Semeghini, G., Omran, A., Bluvstein, D., Samajdar, R., Pichler, H., Ho, W. W., Choi, S., Sachdev, S., Greiner, M., Vuletić, V., and Lukin, M. D. (2022). “Quantum optimization of maximum independent set using Rydberg atom arrays.” Science, 376(6598), 1209–1215. https://doi.org/10.1126/science.abo6587

• Farhi, E., Goldstone, J., Gutmann, S., and Sipser, M. (2000). “Quantum Computation by Adiabatic Evolution.” arXiv:quant-ph/0001106.

• Farhi, E., Goldstone, J., and Gutmann, S. (2014). “A Quantum Approximate Optimization Algorithm.” arXiv:1411.4028.

• Garey, M. R., and Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman.

• Grover, L. K. (1996). “A fast quantum mechanical algorithm for database search.” Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, 212–219. https://doi.org/10.1145/237814.237866

• Kadowaki, T., and Nishimori, H. (1998). “Quantum annealing in the transverse Ising model.” Physical Review E, 58(5), 5355–5363. https://doi.org/10.1103/PhysRevE.58.5355

• Lucas, A. (2014). “Ising formulations of many NP problems.” Frontiers in Physics, 2, 5. https://doi.org/10.3389/fphy.2014.00005

• McClean, J. R., Boixo, S., Smelyanskiy, V. N., Babbush, R., and Neven, H. (2018). “Barren plateaus in quantum neural network training landscapes.” Nature Communications, 9, 4812. https://doi.org/10.1038/s41467-018-07090-4

• Preskill, J. (2018). “Quantum Computing in the NISQ era and beyond.” Quantum, 2, 79. https://doi.org/10.22331/q-2018-08-06-79

• Rønnow, T. F., Wang, Z., Job, J., Boixo, S., Isakov, S. V., Wecker, D., Martinis, J. M., Lidar, D. A., and Troyer, M. (2014). “Defining and detecting quantum speedup.” Science, 345(6195), 420–424. https://doi.org/10.1126/science.1252319