This study presents a comprehensive analysis of optimization methodologies in quantum annealing (QA), investigating both theoretical frameworks and practical implementations. We examine various techniques for enhancing quantum annealing performance, including embedding strategies, parameter optimization, and hybrid quantum-classical approaches. Our research identifies critical challenges: qubit connectivity constraints, noise susceptibility, and problem representation difficulties. Through quantitative comparisons of optimization strategies across various problem classes, we establish a systematic framework for evaluating quantum annealing solutions. Results indicate that while significant challenges persist, strategic optimization approaches can substantially improve quantum annealing performance for specific problem domains, suggesting potential quantum advantage for certain complex optimization tasks.
Combinatorial optimization is a foundation of numerous scientific, industrial, and social decision-making questions, but its usefulness is mostly restricted by the exponential complexity of the problem of classical computability. The quantum annealing (QA) has become one of the leading analogue quantum systems to address such problems, whereby optimization problems are converted into physical energy structures and quantum fluctuations are utilized to perform systematic exploration. It provides a critical, synthesized, and comprehensive review of quantum annealing as applied to combinatorial optimization, including the theoretical basis, hardware designs, algorithm methods, issues of embedding and encoding, benchmarking procedures, applications, and integration with quantum algorithms based on gates and solvers on a classical computer. We build a comprehensive taxonomy between adiabatic dynamics, Ising and QUBO models, stoquastic and non-stoquastic Hamiltonians, and diabatic transitions to state-of-the-art flux-qubit annealers, new architectures, and hybrid quantum classical pipelines. We show that the overhead of embedding and encoding and the benchmarking approach taken are the most significant factors in determining scalability and performance, but not the raw number of qubits. Transportation, energy systems, robotics, finance, pharmacological discovery, and machine learning are just some examples of the domain-specific case studies that use QA with minimal empirical utility as a hybrid refinement engine and not an independent solver. Moreover, we introduce a stringent evaluation of the existing benchmarking culture, clarify the causal links between QA and QAOA as well as between VQE and structural predicaments, and reveal the institutional roots of the existing restrictions. We conclude by identifying a research roadmap in the future, focusing on the annealing hardness characterization, Stoquastic control manipulation, embedding rules automation, architecture design, and development of principled quantum advantage. It creates a benchmark reference to those in the field and research and deployment of scalable, reliable, and application-relevant quantum optimization
Optimization is one of the key applications of quantum computing where a quantum speedup has been an eagerly anticipated outcome. A promising approach to optimization using quantum dynamics is to consider a linear combination $s(t)B+[1\ensuremath{-}s(t)]C$ of two noncommuting Hamiltonians
B and
C, where
C encodes the solution to the optimization problem in its ground state,
B is a Hamiltonian whose ground state is easy to prepare, and $s(t)\ensuremath{\in}[0,1]$ is the bounded ``switching schedule'' or ``path,'' with $t\ensuremath{\in}[0,{t}_{f}]$. This approach encompasses two of the most widely studied quantum-optimization algorithms: quantum annealing [QA; continuous
s(t)] and the quantum approximate optimization algorithm [QAOA; piecewise constant
s(t)]. While it is notoriously difficult to prove a quantum advantage for either algorithm, it is possible to compare and contrast them by finding the optimal
s(t). Here we provide a rigorous analysis of this quantum optimal control problem, entirely within the geometric framework of Pontryagin's maximum principle of optimal control theory. We extend earlier results, derived in a purely closed-system setting, to open systems. This is the natural setting for experimental realizations of QA and QAOA. In the closed-system setting it was shown that the optimal solution is a ``bang-anneal-bang'' schedule, with the bangs characterized by
s(t)=0 and
s(t)=1 in finite subintervals of
[0,tf], in particular,
s(0)=0 and
s(tf)=1, in contrast to the standard prescription
s(0)=1 and
s(tf)=0 of QA. As an example, we prove that for a single spin-
1/2, the optimal solution in the closed-system setting is the bang-bang schedule, switching midway from $s\ensuremath{\equiv}0$ to $s\ensuremath{\equiv}1$. For finite-dimensional environments and without any approximations we identify sufficient conditions ensuring that either the bang-anneal, anneal-bang, or bang-anneal-bang schedules are optimal, and recover the optimality of
s(0)=0 and
s(tf)=1. However, for infinite-dimensional environments and a system described by an adiabatic Redfield master equation we do not recover the bang-type optimal solution. In fact we can only identify conditions under which
s(tf)=1, and even this result is not recovered in the fully Markovian limit, suggesting that the pure anneal-type schedule is optimal. Our open-system results have implications for the use of experimental quantum-information processors, which are by necessity noisy, and suggest that in this practical sense the optimal schedules for quantum optimization are likely to be continuous.
The recent advances in the world of quantum technologies have prompted the development of various quantum-based algorithms, some of which are suitable to run on available quantum devices. Two leading candidates in this area are Quantum Annealing (QA) and hybrid quantum-classical variational algorithms, such as the Quantum Approximate Optimization Algorithm (QAOA). In the first part of the Thesis, we re-examine the issue of whether Simulated Quantum Annealing (SQA) with Path Integral Monte Carlo has anything to do with the coherent QA Schrödinger dynamics. We do that by studying the random quantum Ising Chain in a transverse field. In the second part of the Thesis we address the issue of schedule optimization in both {em digitized}-QA and QAOA. Traditional schedule optimization in QA requires spectral information on the problem (e.g., location of the minimum gaps), which is in most cases inaccessible. On the other hand, in QAOA, the issue of schedule optimization --- alias, the optimization of the variational parameters --- is often an expensive task that constitutes a bottleneck for the algorithm. We show that, by combining the framework of QAOA and digitized-QA, optimal digitized-QA protocols can be constructed efficiently. When using this approach, the computational cost of schedule optimization is also significantly reduced, leading to a computational advantage both over a linear-schedule QA, and over an unstructured QAOA search. While studying these issues, we also developed rigorous variational bounds that provide insight on the best possible performance that one can hope to obtain from a digital QAOA circuit.
Recent advances in quantum technologies have intensified the search for algo rithms that can use quantum resources effectively. Quantum annealing and hybrid quantum–classical variational algorithms are two prominent approaches in this set ting. Conventional quantum annealing follows a prescribed Hamiltonian interpo lation and may therefore be limited by small spectral gaps along that path. This Thesis investigates how algorithmic performance changes when three elements are varied: the annealing schedule (Chapter 2), the independent parameters of a digi tized evolution (Chapter 3), and the encoding of the problem (Chapter 4). For weighted MaxCut instances with anomalously small annealing gaps, opti mized smooth schedules outperform linear digitized annealing at equal circuit depth. Rather than restoring adiabaticity or enlarging the gap, the dynamics deliberately leaves the instantaneous ground state and later returns the population to the target state. Smoothness allows these digital solutions to retain their quality as continuous time controls and when transferred between related instances. The schedule restriction is then removed for a frustrated Ising ring whose anneal ing gap closes exponentially with system size. Optimizing all circuit angles inde pendently yields numerically exact ground-state preparation at the critical depth Pcr 1 =(N2−1)/4. This quadratic threshold is explained by the dimension and sym metries of the reachable free-fermion manifold, demonstrating that controllability, rather than the gap of a particular interpolation, determines the required number of digital controls. Finally, the same ring family is reformulated through the parity mapping. For the original frustrated ring, Parity-QAOA reaches the exact ground state using only single-qubit rotations, without applying the constraint unitary. The number of layers equals the number of distinct coupling values and does not grow with system size. To clarify the role of constraints, an equal-magnitude signed ring is also studied, for which the constraint unitary is essential for preparing the target ground state. Together, these results identify the shape, controllability, and encoding of a quan tum protocol as resources for overcoming limitations imposed by more restricted routes to ground-state preparation.
Quantum annealing is a generic name of quantum algorithms that use quantum-mechanical fluctuations to search for the solution of an optimization problem. It shares the basic idea with quantum adiabatic evolution studied actively in quantum computation. The present paper reviews the mathematical and theoretical foundations of quantum annealing. In particular, theorems are presented for convergence conditions of quantum annealing to the target optimal state after an infinite-time evolution following the Schrödinger or stochastic (Monte Carlo) dynamics. It is proved that the same asymptotic behavior of the control parameter guarantees convergence for both the Schrödinger dynamics and the stochastic dynamics in spite of the essential difference of these two types of dynamics. Also described are the prescriptions to reduce errors in the final approximate solution obtained after a long but finite dynamical evolution of quantum annealing. It is shown there that we can reduce errors significantly by an ingenious choice of annealing schedule (time dependence of the control parameter) without compromising computational complexity qualitatively. A review is given on the derivation of the convergence condition for classical simulated annealing from the view point of quantum adiabaticity using a classical-quantum mapping.