Advances in quantum algorithms suggest a tentative scaling advantage on certain combinatorial optimization problems. Recent work, however, has also reinforced the idea that barren plateaus render variational algorithms ineffective on large Hilbert spaces. Hence, finding annealing protocols by variation ultimately appears to be difficult. Similarly, the adiabatic theorem fails on hard problem instances with first-order quantum phase transitions. Here we show how to use the spin coherent-state path integral to shape the geometry of quantum adiabatic evolution, leading to annealing protocols at polynomial overhead that provide orders-of-magnitude improvements in the probability to measure optimal solutions, relative to linear protocols. These improvements are not obtained on a controllable toy problem but on randomly generated hard instances (Sherrington-Kirkpatrick and maximum 2-satisfiability), making them generic and robust. Our method works for large systems and may thus be used to improve the performance of state-of-the-art quantum devices.
Advances in quantum algorithms suggest a tentative scaling advantage on certain combinatorial optimization problems. Recent work, however, has also reinforced the idea that barren plateaus render variational algorithms ineffective on large Hilbert spaces. Hence, finding annealing protocols by variation ultimately appears to be difficult. Similarly, the adiabatic theorem fails on hard problem instances with first-order quantum phase transitions. Here we show how to use the spin coherent-state path integral to shape the geometry of quantum adiabatic evolution, leading to annealing protocols at polynomial overhead that provide orders-of-magnitude improvements in the probability to measure optimal solutions, relative to linear protocols. These improvements are not obtained on a controllable toy problem but on randomly generated hard instances (Sherrington-Kirkpatrick and maximum 2-satisfiability), making them generic and robust. Our method works for large systems and may thus be used to improve the performance of state-of-the-art quantum devices.
The path integral Monte Carlo simulated quantum annealing algorithm is applied to the optimization of a large hard instance of the random satisfiability problem (N = 10,000). The dynamical behavior of the quantum and the classical annealing are compared, showing important qualitative differences in the way of exploring the complex energy landscape of the combinatorial optimization problem. At variance with the results obtained for the Ising spin glass and for the traveling salesman problem, in the present case the linear-schedule quantum annealing performance is definitely worse than classical annealing. Nevertheless, a quantum cooling protocol based on field-cycling and able to outperform standard classical simulated annealing over short time scales is introduced.
The correspondence between long-range interacting quantum spin glasses and combinatorial optimization problems underpins the physical motivation for adiabatic quantum computing. On one hand, in disordered (quantum) spin systems, the focus is on exact methods such as the replica trick that allow the calculation of system quantities in the limit of infinite system and ensemble size. On the other hand, when solving a given instance of an optimization problem, disorder-averaged quantities are of no relevance, as one is solely interested in instance-specific, finite-size properties, in particular the optimal solution. Here, we apply the nonequilibrium Green's function formalism to the spin coherent-state path integral to obtain the statistical fluctuations and the collective-excitation spectrum along the annealing path. For the example of the quantum Sherrington-Kirkpatrick spin glass, by comparing to extensive numerically exact results, we show that this method provides access to the instance-specific bottlenecks of the annealing protocol.
We embed 1-layer QAOA circuits into the larger class of parametrized instantaneous quantum polynomial circuits to produce an improved variational quantum algorithm for solving combinatorial optimization problems. The use of analytic expressions to find optimal parameters classically makes our protocol robust against barren plateaus and hardware noise. The average overlap with the ground state scales as 2−0.31(2)N with the number of qubits N for random Sherrington-Kirkpatrick (SK) Hamiltonians of up to 29 qubits, a polynomial improvement over 1-layer QAOA. Additionally, we observe that performing variational imaginary time evolution on the manifold approximates low-temperature pseudo-Boltzmann states. Our protocol outperforms 1-layer QAOA on the recently released Quantinuum H2 trapped-ion quantum hardware and emulator, where we obtain an average approximation ratio of 0.985 across 312 random SK instances of 7 to 32 qubits, from which almost 44% are solved optimally using only 4 to 1208 shots per instance. Published by the American Physical Society 2024
Abstract We consider a classical and superadiabatic version of an iterative quantum adiabatic algorithm to solve combinatorial optimization problems. This algorithm is deterministic because it is based on purely classical dynamics, that is, it does not rely on any stochastic approach to mimic quantum dynamics. Moreover, we use the exact shortcut to adiabaticity for stationary states of classical spin systems, and thus the final state of an annealing process does not depend on the annealing time. We apply this algorithm to a certain class of hard instances of the 3-SAT problem, which is specially hard for purely adiabatic algorithms. We find that more than 90% of such 64-bits hard instances, which we try to solve, can be resolved by a few iteration. Our approach can also be used to analyze properties of instances themselves apart from stochastic uncertainty and shortage of adiabaticity.
Estimating partition functions of Ising spin glasses is a cornerstone of statistical physics and computational science, yet it remains classically challenging due to its #P-hard complexity. While Jarzynski's equality offers a theoretical pathway, its practical application is crippled at low temperatures by rare, divergent statistical fluctuations. Here, we introduce a quantum protocol that overcomes this fundamental limitation by synergizing reverse quantum annealing with optimized nonequilibrium initial distributions. Our method dramatically suppresses the estimator variance, achieving saturation in the low-temperature regime where existing methods fail. Numerical benchmarks on the Sherrington-Kirkpatrick spin glass and the 3-SAT problem demonstrate that our protocol reduces computational scaling exponents by over an order of magnitude (e.g., from ∼8.5 to ∼0.5), despite retaining exponential system-size dependence. Crucially, our protocol circumvents stringent adiabatic constraints, making it feasible for near-term quantum devices like superconducting qubits, trapped ions, and Rydberg atom arrays. This Letter provides a methodological framework for quantum-enhanced estimation in spin glass thermodynamics and beyond by harnessing nonadiabatic quantum dynamics to address a classically difficult problem.
Combinatorial Optimization problems play an important role in various domains such as logis- tics, life science or the financial sector. As their complexity in general grows exponentially with their problem size, finding the optimal solution classically becomes infeasible very fast. This raises the central question of whether quantum computers are in principle suitable for solving combinatorial optimization problems better and faster than classical computers. In order to find answers to that question, one needs to study quantum algorithms designed for those problems under ideal conditions (i.e., simulations, which are however limited due to exponential scaling) to investigate their potential, but one also needs real quantum hardware to test its viability and evaluate whether practical advantages are reasonable. In this regard, we consider variational quantum algorithms, especially the Quantum Approximate Optimization Algorithm (QAOA) consisting of a problem and a mixer Hamiltonian with freely selectable parameters, originally proposed as variational hybrid ansatz with classical optimization. This algorithm structure of- fers flexible and relatively shallow circuits, which makes it suitable for current NISQ hardware. However, optimizing the variational circuit parameters can be an NP-hard problem at worst. In this thesis, we study different versions of QAOA, especially with a focus on limitations, perfor- mance and potential advantages opposite classical methods. The first part of the thesis concerns the investigation of various aspects regarding the imple- mentation of the variational QAOA protocol such as: the incorporation of a problem constraint either by adding a suitable penalty term of by choosing a suitable mixer (that restricts the search space), the scaling of the problem Hamiltonian in comparison to the mixer Hamiltonian, the choice of the initial values for the classical optimization of the circuit parameters, and finally the choice of the function to be minimized (i.e., CVaR vs. expectation value). We apply this proto- col to both the portfolio optimization and the feature selection and evaluate the performance. In order to improve QAOA, we consider the warm-start QAOA for different problem instances and analyze its improved performance with regard to involved quantum effects. For this purpose, we propose a classical pre-processing method and demonstrate that the warm-start results can be reproduced or even exceeded by this method. The second part addresses the issue that the standard variational form requires a high number of circuit parameters that have to be optimized at a sufficiently large depth, which is a major limitationforachievingpotentialscalingadvantagescomparedtoclassicalmethods. Toovercome this limitation, we investigate and further develop fixed schedules for QAOA, which only rely on two free parameters. We start with introducing the continuous adiabatic theorem as it motivates the form of QAOA and show its limitations, which we address by applying a discrete version of the theorem. With our findings, a new version of QAOA based on linear-ramps (LR-QAOA) is introduced and further developed. In order to derive suitable parameter values for this schedule, we propose a method based on extrapolation from smaller towards larger problem sizes. With our results obtained on a noiseless emulator, we evaluate the quantum runtime scaling and discuss whether a scaling advantage can be achieved compared to classical methods.