Abstract Quantum annealing (QA) holds promise for optimization problems in quantum computing, especially for combinatorial optimization. This analog framework attracts attention for its potential to address complex problems. Its gate-based homologous, QAOA with proven performance, has attracted a lot of attention to the NISQ era. Several numerical benchmarks try to compare these two metaheuristics, however, classical computational power highly limits the performance insights. In this work, we introduce a parametrized version of QA enabling a precise 1-local analysis of the algorithm. We develop a tight Lieb–Robinson bound for regular graphs, achieving the best-known numerical value to analyze QA locally. Studying MaxCut over cubic graph as a benchmark optimization problem, we show that a linear-schedule QA with a 1-local analysis achieves an approximation ratio over 0.7020, outperforming any known 1-local algorithms.
Abstract Quantum annealing (QA) holds promise for optimization problems in quantum computing, especially for combinatorial optimization. This analog framework attracts attention for its potential to address complex problems. Its gate-based homologous, QAOA with proven performance, has attracted a lot of attention to the NISQ era. Several numerical benchmarks try to compare these two metaheuristics, however, classical computational power highly limits the performance insights. In this work, we introduce a parametrized version of QA enabling a precise 1-local analysis of the algorithm. We develop a tight Lieb–Robinson bound for regular graphs, achieving the best-known numerical value to analyze QA locally. Studying MaxCut over cubic graph as a benchmark optimization problem, we show that a linear-schedule QA with a 1-local analysis achieves an approximation ratio over 0.7020, outperforming any known 1-local algorithms.
Abstract Quantum annealing (QA) is a computational framework where a quantum system’s continuous evolution is used to find the global minimum of an objective function over an unstructured search space. It can be seen as a general metaheuristic for optimization problems, including NP-hard ones if we allow an exponentially large running time. While QA is widely studied from a heuristic point of view, little is known about theoretical guarantees on the quality of the solutions obtained in polynomial time. In this paper, we use a technique borrowed from theoretical physics, the Lieb–Robinson (LR) bound, and develop new tools proving that short, constant-time QA guarantees constant factor approximations ratios for some optimization problems when restricted to bounded degree graphs. Informally, on bounded degree graphs the LR bound allows us to retrieve a (relaxed) locality argument, through which the approximation ratio can be deduced by studying subgraphs of bounded radius. We illustrate our tools on problems MaxCut and maximum independent set for cubic graphs, providing explicit approximation ratios and the runtimes needed to obtain them. Our results are of similar flavor to the well-known ones obtained in the different but related QAOA (quantum optimization algorithms) framework.
This study presents a rigorous empirical evaluation of the Quantum Approximate Optimization Algorithm (QAOA) within a hybrid quantum-classical framework for solving the NP-hard Max-Cut problem. Using Python and Qiskit Aer statevector simulations, we benchmark QAOA (depths p = 2 and p = 3) against established classical algorithms, including simulated annealing, the Goemans–Williamson algorithm, and greedy heuristics, across Erdős–Rényi and regular graphs with 4 to 20 nodes (100 instances per size). Results demonstrate that low-depth QAOA suffers from significant performance degradation, achieving a 0.467 approximation ratio at 20 nodes compared to 0.856 for Goemans–Williamson, alongside a 210× runtime overhead. Convergence analysis further reveals low optimality probabilities and high iteration costs, highlighting limitations of variational optimization in NISQ-era devices. This work provides a reproducible benchmarking framework and contributes to a realistic assessment of near-term quantum advantage.
This study presents a rigorous empirical evaluation of the Quantum Approximate Optimization Algorithm (QAOA) within a hybrid quantum-classical framework for solving the NP-hard Max-Cut problem. Using Python and Qiskit Aer statevector simulations, we benchmark QAOA (depths p = 2 and p = 3) against established classical algorithms, including simulated annealing, the Goemans–Williamson algorithm, and greedy heuristics, across Erdős–Rényi and regular graphs with 4 to 20 nodes (100 instances per size). Results demonstrate that low-depth QAOA suffers from significant performance degradation, achieving a 0.467 approximation ratio at 20 nodes compared to 0.856 for Goemans–Williamson, alongside a 210× runtime overhead. Convergence analysis further reveals low optimality probabilities and high iteration costs, highlighting limitations of variational optimization in NISQ-era devices. This work provides a reproducible benchmarking framework and contributes to a realistic assessment of near-term quantum advantage.
This study presents a rigorous empirical evaluation of the Quantum Approximate Optimization Algorithm (QAOA) within a hybrid quantum-classical framework for solving the NP-hard Max-Cut problem. Using Python and Qiskit Aer statevector simulations, we benchmark QAOA (depths p = 2 and p = 3) against established classical algorithms, including simulated annealing, the Goemans–Williamson algorithm, and greedy heuristics, across Erdős–Rényi and regular graphs with 4 to 20 nodes (100 instances per size). Results demonstrate that low-depth QAOA suffers from significant performance degradation, achieving a 0.467 approximation ratio at 20 nodes compared to 0.856 for Goemans–Williamson, alongside a 210× runtime overhead. Convergence analysis further reveals low optimality probabilities and high iteration costs, highlighting limitations of variational optimization in NISQ-era devices. This work provides a reproducible benchmarking framework and contributes to a realistic assessment of near-term quantum advantage.
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-P quantum circuit has to satisfy ε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 2P degenerate variational minima which can be found for this problem, all strictly satisfying the equality ε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.
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.