Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Radboud University Press eBooks

Quantum Annealing Complexity and Stochastic Quantum Control

Aarón Villanueva

Published Sep 23, 2026• 0 citations
Publisher

Abstract

This thesis investigates two central challenges for quantum computing: identifying when quantum annealing can offer a computational advantage, and developing effective methods to control realistic quantum systems. It establishes complexity bounds for an adiabatic algorithm for combinatorial optimization, showing a universal quadratic advantage while highlighting the practical difficulty of realizing the required schedule. It also introduces Path Integral Quantum Control, a trajectory-based framework for optimizing controls in open quantum systems, and develops a stochastic Hamiltonian description of continuous quantum measurement connected to double-bracket gradient flows. Together, these results advance the theoretical foundations of quantum optimization, open-system control, and measurement-based feedback

DOI
10.54195/9789465153179

Related papers

Optimization In Quantum Annealing: Methods And Challenges

Debasis Dhal, Shovan Roy

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.

International Journal of Environmental Sciences•Aug 20, 2025•0 citations

Optimal Control for Quantum Optimization of Closed and Open Systems

Lorenzo Campos Venuti, Domenico D’Alessandro, Daniel A. Lidar

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,{t}_{f}]$, in particular, $s(0)=0$ and $s({t}_{f})=1$, in contrast to the standard prescription $s(0)=1$ and $s({t}_{f})=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({t}_{f})=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({t}_{f})=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.

arXiv:2107.03517•Physical Review Applied•Nov 11, 2021•27 citations

Quantum Optimal Control and Variational Algorithms for Optimization

RUIYI WANG

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.

•Sep 24, 2026•0 citations

Quantum annealing and digital quantum ground state preparation algorithms

Glen Bigan Mbeng

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.

•Oct 24, 2019•2 citations

Mathematical foundation of quantum annealing

Satoshi Morita, Hidetoshi Nishimori

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.

arXiv:0806.1859•Journal of Mathematical Physics•Dec 1, 2008•423 citations

Path integral control of open quantum systems

Aarón Villanueva, Hilbert J. Kappen

We investigate open-loop quantum state preparation for a class of open quantum systems whose dynamics follow a Gorini-Kossakowski-Lindblad-Sudarshan (GKLS) master equation that admits a trajectory-based stochastic representation. The deterministic control objective is reformulated as a stochastic optimal control problem -- interpreting stochasticity as a methodological tool akin to stochastic Schrödinger equation unravelings -- which situates the problem within the path integral control framework. For the class of GKLS generators under consideration, this reformulation leads to an explicit expression for the optimal control as a weighted average over stochastic quantum trajectories, thereby eliminating the need for gradient evaluations. Building on this theoretical result, we derive a control update rule for piecewise-constant control pulses and demonstrate that adaptive importance sampling progressively enhances the control estimator during optimization, culminating in the algorithm we term Path integral Quantum Control (PiQC). We further introduce an annealed variant of PiQC, wherein a synthetic noise schedule gradually steers open-system trajectories toward closed-system dynamics, enabling high-fidelity unitary state preparation. Numerical studies on a dissipative single-qubit system and a multi-qubit Nuclear Magnetic Resonance model verify that PiQC yields precise open-loop controls and displays robustness to Hamiltonian perturbations. We propose PiQC as a trajectory-based alternative to gradient-based approaches, which might offer a viable solution in quantum control problems where gradient computation is infeasible or computationally demanding.

arXiv:2410.18635•Physical Review A•Jun 9, 2026•7 citations
This thesis investigates two central challenges for quantum computing: identifying when quantum annealing can offer a computational advantage, and developing effective methods to control realistic quantum systems. It establishes complexity bounds for an adiabatic algorithm for combinatorial optimization, showing a universal quadratic advantage while highlighting the practical difficulty of realizing the required schedule. It also introduces Path Integral Quantum Control, a trajectory-based framework for optimizing controls in open quantum systems, and develops a stochastic Hamiltonian description of continuous quantum measurement connected to double-bracket gradient flows. Together, these results advance the theoretical foundations of quantum optimization, open-system control, and measurement-based feedback
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.
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 BBB and CCC, where CCC encodes the solution to the optimization problem in its ground state, BBB 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)s(t)s(t)] and the quantum approximate optimization algorithm [QAOA; piecewise constant s(t)s(t)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)s(t)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)=0s(t)=0s(t)=0 and s(t)=1s(t)=1s(t)=1 in finite subintervals of [0,tf][0,{t}_{f}][0,tf​], in particular, s(0)=0s(0)=0s(0)=0 and s(tf)=1s({t}_{f})=1s(tf​)=1, in contrast to the standard prescription s(0)=1s(0)=1s(0)=1 and s(tf)=0s({t}_{f})=0s(tf​)=0 of QA. As an example, we prove that for a single spin-1/21/21/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)=0s(0)=0s(0)=0 and s(tf)=1s({t}_{f})=1s(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)=1s({t}_{f})=1s(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.
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.
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.
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.
We investigate open-loop quantum state preparation for a class of open quantum systems whose dynamics follow a Gorini-Kossakowski-Lindblad-Sudarshan (GKLS) master equation that admits a trajectory-based stochastic representation. The deterministic control objective is reformulated as a stochastic optimal control problem -- interpreting stochasticity as a methodological tool akin to stochastic Schrödinger equation unravelings -- which situates the problem within the path integral control framework. For the class of GKLS generators under consideration, this reformulation leads to an explicit expression for the optimal control as a weighted average over stochastic quantum trajectories, thereby eliminating the need for gradient evaluations. Building on this theoretical result, we derive a control update rule for piecewise-constant control pulses and demonstrate that adaptive importance sampling progressively enhances the control estimator during optimization, culminating in the algorithm we term Path integral Quantum Control (PiQC). We further introduce an annealed variant of PiQC, wherein a synthetic noise schedule gradually steers open-system trajectories toward closed-system dynamics, enabling high-fidelity unitary state preparation. Numerical studies on a dissipative single-qubit system and a multi-qubit Nuclear Magnetic Resonance model verify that PiQC yields precise open-loop controls and displays robustness to Hamiltonian perturbations. We propose PiQC as a trajectory-based alternative to gradient-based approaches, which might offer a viable solution in quantum control problems where gradient computation is infeasible or computationally demanding.