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

arXiv:1906.08948

Quantum Annealing: a journey through Digitalization, Control, and hybrid Quantum Variational schemes

Glen Bigan Mbeng, Rosario Fazio, Giuseppe E. Santoro

Published Jun 21, 2019• 37 citations
arXivHTMLPDF

Abstract

We establish and discuss a number of connections between a digitized version of Quantum Annealing (QA) with the Quantum Approximate Optimization Algorithm (QAOA) introduced by Farhi et al. (arXiv:1411.4028) as an alternative hybrid quantum-classical variational scheme for quantum-state preparation and optimization. We introduce a technique that allows to prove, for instance, a rigorous bound concerning the performance of QAOA for MaxCut on a $2$-regular graph, equivalent to an unfrustrated antiferromagnetic Ising chain. The bound shows that the optimal variational error of a depth-$\mathrm{P}$ quantum circuit has to satisfy $ε^\mathrm{res}_{\mathrm{P}}\ge (2\mathrm{P}+2)^{-1}$. In a separate work (Mbeng et al., arXiv:1911.12259) we have explicitly shown, exploiting a Jordan-Wigner transformation, that among the $2^{\mathrm{P}}$ degenerate variational minima which can be found for this problem, all strictly satisfying the equality $ε^\mathrm{res}_{\mathrm{P}}=(2\mathrm{P}+2)^{-1}$, one can construct a special {\em regular} optimal solution, which is computationally optimal and does not require any prior knowledge about the spectral gap. We explicitly demonstrate here that such a schedule is adiabatic, in a digitized sense, and can therefore be interpreted as an optimized digitized-QA protocol. We also discuss and compare our bound on the residual energy to well-known results on the Kibble-Zurek mechanism behind a continuous-time QA. These findings help elucidating the intimate relation between digitized-QA, QAOA, and optimal Quantum Control.

DOI
10.48550/arxiv.1906.08948

Related papers

Optimal quantum control with digitized Quantum Annealing

Glen Bigan Mbeng, Rosario Fazio, Giuseppe E. Santoro

We show how a digitized version of Quantum Annealing can be made optimal, realizing the best possible solution allowed by quantum mechanics in the shortest time, without any prior knowledge on the location and properties of the spectral gap. Our findings elucidate the intimate relation between digitized-QA, optimal Quantum Control, and recently proposed hybrid quantum-classical variational algorithms for quantum-state preparation and optimization. We illustrate this on the simple benchmark problem of an unfrustrated antiferromagnetic Ising chain in a transverse field.

arXiv:1911.12259•Nov 25, 2019•9 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

Beyond quantum annealing: optimal control solutions to maxcut problems

Giovanni Pecci, Ruiyi Wang, Pietro Torta +2 more

Abstract Quantum Annealing (QA) relies on mixing two Hamiltonian terms, a simple driver and a complex problem Hamiltonian, in a linear combination. The time-dependent schedule for this mixing is often taken to be linear in time: improving on this linear choice is known to be essential and has proven to be difficult. Here, we present different techniques for improving on the linear-schedule QA along two directions, conceptually distinct but leading to similar outcomes: 1) the first approach consists of constructing a Trotter-digitized QA (dQA) with schedules parameterized in terms of Fourier modes or Chebyshev polynomials, inspired by the Chopped Random Basis algorithm for optimal control in continuous time; 2) the second approach is technically a Quantum Approximate Optimization Algorithm (QAOA), whose solutions are found iteratively using linear interpolation or expansion in Fourier modes. Both approaches emphasize finding smooth optimal schedule parameters, ultimately leading to hybrid quantum–classical variational algorithms of the alternating Hamiltonian Ansatz type. We apply these techniques to MaxCut problems on weighted 3-regular graphs with N = 14 sites, focusing on hard instances that exhibit a small spectral gap, for which a standard linear-schedule QA performs poorly. We characterize the physics behind the optimal protocols for both the dQA and QAOA approaches, discovering shortcuts to adiabaticity -like dynamics. Furthermore, we study the transferability of such smooth solutions among hard instances of MaxCut at different circuit depths. Finally, we show that the smoothness pattern of these protocols obtained in a digital setting enables us to adapt them to continuous-time evolution, contrarily to generic non-smooth solutions. This procedure results in an optimized QA schedule that is implementable on analog devices.

arXiv:2405.08630•Quantum Science and Technology•Jul 9, 2024•8 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 Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices

Leo Zhou, Sheng-Tao Wang, Soonwon Choi +2 more

The quantum approximate optimization algorithm (QAOA) is a hybrid quantum-classical variational algorithm designed to tackle combinatorial optimization problems.Despite its promise for near-term quantum applications, not much is currently understood about the QAOA's performance beyond its lowestdepth variant.An essential but missing ingredient for understanding and deploying the QAOA is a constructive approach to carry out the outer-loop classical optimization.We provide an in-depth study of the performance of the QAOA on MaxCut problems by developing an efficient parameter-optimization procedure and revealing its ability to exploit nonadiabatic operations.Building on observed patterns in optimal parameters, we propose heuristic strategies for initializing optimizations to find quasioptimal p-level QAOA parameters in O½polyðpÞ time, whereas the standard strategy of random initialization requires 2 OðpÞ optimization runs to achieve similar performance.We then benchmark the QAOA and compare it with quantum annealing, especially on difficult instances where adiabatic quantum annealing fails due to small spectral gaps.The comparison reveals that the QAOA can learn via optimization to utilize nonadiabatic mechanisms to circumvent the challenges associated with vanishing spectral gaps.Finally, we provide a realistic resource analysis on the experimental implementation of the QAOA.When quantum fluctuations in measurements are accounted for, we illustrate that optimization is important only for problem sizes beyond numerical simulations but accessible on near-term devices.We propose a feasible implementation of large MaxCut problems with a few hundred vertices in a system of 2D neutral atoms, reaching the regime to challenge the best classical algorithms.

arXiv:1812.01041•Physical Review X•Jun 24, 2020•932 citations

Digital controllability of transverse-field Ising chains

Vincenzo Roberto Arezzo, Ruiyi Wang, Kiran Thengil +2 more

Quantum Annealing (QA) encounters limitations when the energy gap along the annealing path becomes exponentially small, leading to impractically long runtimes. In contrast, the success of hybrid digital methods like the Quantum Approximate Optimization Algorithm (QAOA), which operate via discrete unitary operations, relies on the optimization of the variational parameters appearing in the state. We analyze a class of transverse-field Ising models which includes problems with exponentially small spectral gaps, but whose dynamics is described in terms of fermionic Gaussian states after Jordan-Wigner mapping. We show that, for digital alternating QAOA-like states, the number of unitaries required to reach the exact ground state scales quadratically with system size and is independent of the annealing gap. This number can be exactly computed from the algebraic properties of the Ansatz, revealing a fundamental distinction between digital methods and their analog counterpart.

arXiv:2509.17754•Physical Review A•Dec 9, 2025•0 citations
We establish and discuss a number of connections between a digitized version of Quantum Annealing (QA) with the Quantum Approximate Optimization Algorithm (QAOA) introduced by Farhi et al. (arXiv:1411.4028) as an alternative hybrid quantum-classical variational scheme for quantum-state preparation and optimization. We introduce a technique that allows to prove, for instance, a rigorous bound concerning the performance of QAOA for MaxCut on a 222-regular graph, equivalent to an unfrustrated antiferromagnetic Ising chain. The bound shows that the optimal variational error of a depth-P\mathrm{P}P quantum circuit has to satisfy εPres≥(2P+2)−1ε^\mathrm{res}_{\mathrm{P}}\ge (2\mathrm{P}+2)^{-1}εPres​≥(2P+2)−1. In a separate work (Mbeng et al., arXiv:1911.12259) we have explicitly shown, exploiting a Jordan-Wigner transformation, that among the 2P2^{\mathrm{P}}2P degenerate variational minima which can be found for this problem, all strictly satisfying the equality εPres=(2P+2)−1ε^\mathrm{res}_{\mathrm{P}}=(2\mathrm{P}+2)^{-1}εPres​=(2P+2)−1, one can construct a special {\em regular} optimal solution, which is computationally optimal and does not require any prior knowledge about the spectral gap. We explicitly demonstrate here that such a schedule is adiabatic, in a digitized sense, and can therefore be interpreted as an optimized digitized-QA protocol. We also discuss and compare our bound on the residual energy to well-known results on the Kibble-Zurek mechanism behind a continuous-time QA. These findings help elucidating the intimate relation between digitized-QA, QAOA, and optimal Quantum Control.
We show how a digitized version of Quantum Annealing can be made optimal, realizing the best possible solution allowed by quantum mechanics in the shortest time, without any prior knowledge on the location and properties of the spectral gap. Our findings elucidate the intimate relation between digitized-QA, optimal Quantum Control, and recently proposed hybrid quantum-classical variational algorithms for quantum-state preparation and optimization. We illustrate this on the simple benchmark problem of an unfrustrated antiferromagnetic Ising chain in a transverse field.
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.
Abstract Quantum Annealing (QA) relies on mixing two Hamiltonian terms, a simple driver and a complex problem Hamiltonian, in a linear combination. The time-dependent schedule for this mixing is often taken to be linear in time: improving on this linear choice is known to be essential and has proven to be difficult. Here, we present different techniques for improving on the linear-schedule QA along two directions, conceptually distinct but leading to similar outcomes: 1) the first approach consists of constructing a Trotter-digitized QA (dQA) with schedules parameterized in terms of Fourier modes or Chebyshev polynomials, inspired by the Chopped Random Basis algorithm for optimal control in continuous time; 2) the second approach is technically a Quantum Approximate Optimization Algorithm (QAOA), whose solutions are found iteratively using linear interpolation or expansion in Fourier modes. Both approaches emphasize finding smooth optimal schedule parameters, ultimately leading to hybrid quantum–classical variational algorithms of the alternating Hamiltonian Ansatz type. We apply these techniques to MaxCut problems on weighted 3-regular graphs with N = 14 sites, focusing on hard instances that exhibit a small spectral gap, for which a standard linear-schedule QA performs poorly. We characterize the physics behind the optimal protocols for both the dQA and QAOA approaches, discovering shortcuts to adiabaticity -like dynamics. Furthermore, we study the transferability of such smooth solutions among hard instances of MaxCut at different circuit depths. Finally, we show that the smoothness pattern of these protocols obtained in a digital setting enables us to adapt them to continuous-time evolution, contrarily to generic non-smooth solutions. This procedure results in an optimized QA schedule that is implementable on analog devices.
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 quantum approximate optimization algorithm (QAOA) is a hybrid quantum-classical variational algorithm designed to tackle combinatorial optimization problems.Despite its promise for near-term quantum applications, not much is currently understood about the QAOA's performance beyond its lowestdepth variant.An essential but missing ingredient for understanding and deploying the QAOA is a constructive approach to carry out the outer-loop classical optimization.We provide an in-depth study of the performance of the QAOA on MaxCut problems by developing an efficient parameter-optimization procedure and revealing its ability to exploit nonadiabatic operations.Building on observed patterns in optimal parameters, we propose heuristic strategies for initializing optimizations to find quasioptimal p-level QAOA parameters in O½polyðpÞ time, whereas the standard strategy of random initialization requires 2 OðpÞ optimization runs to achieve similar performance.We then benchmark the QAOA and compare it with quantum annealing, especially on difficult instances where adiabatic quantum annealing fails due to small spectral gaps.The comparison reveals that the QAOA can learn via optimization to utilize nonadiabatic mechanisms to circumvent the challenges associated with vanishing spectral gaps.Finally, we provide a realistic resource analysis on the experimental implementation of the QAOA.When quantum fluctuations in measurements are accounted for, we illustrate that optimization is important only for problem sizes beyond numerical simulations but accessible on near-term devices.We propose a feasible implementation of large MaxCut problems with a few hundred vertices in a system of 2D neutral atoms, reaching the regime to challenge the best classical algorithms.
Quantum Annealing (QA) encounters limitations when the energy gap along the annealing path becomes exponentially small, leading to impractically long runtimes. In contrast, the success of hybrid digital methods like the Quantum Approximate Optimization Algorithm (QAOA), which operate via discrete unitary operations, relies on the optimization of the variational parameters appearing in the state. We analyze a class of transverse-field Ising models which includes problems with exponentially small spectral gaps, but whose dynamics is described in terms of fermionic Gaussian states after Jordan-Wigner mapping. We show that, for digital alternating QAOA-like states, the number of unitaries required to reach the exact ground state scales quadratically with system size and is independent of the annealing gap. This number can be exactly computed from the algebraic properties of the Ansatz, revealing a fundamental distinction between digital methods and their analog counterpart.