In adiabatic quantum computation the required run-time to reach a given ground-state fidelity is dictated by the size of the minimum gap that appears between the ground and first-excited state in the annealing spectrum. In general the presence of avoided level crossings demands an exponential increase in the annealing time with the system size which has consequences both for the efficiency of the algorithm and the required qubit coherence times. One promising avenue being explored to produce more favorable gap scaling is the introduction of nonstoquastic X X couplings in the form of a catalyst—of particular interest are catalysts which utilize accessible information about the optimization problem in their construction. Here we show extreme sensitivity of the effect of an X X catalyst to subtle changes in the encoding of the optimization problem. In particular, we observe that a targeted catalyst containing a single coupling can significantly reduce the gap closing with system size at an avoided level crossing. For slightly different encodings of the same problems however, these same catalysts result in closing gaps in the annealing spectrum. To understand the origin of these closing gaps, we study how the evolution of the ground-state vector is altered by the presence of the catalyst and find that the negative components of the ground-state vector are key to understanding the response of the gap spectrum. We also consider how and when these closing gaps could be utilized in diabatic quantum annealing protocols—a promising alternative to adiabatic quantum annealing in which transitions to higher energy levels are exploited to reduce the run time of the algorithm. Published by the American Physical Society 2024
In adiabatic quantum computation the required run-time to reach a given ground-state fidelity is dictated by the size of the minimum gap that appears between the ground and first-excited state in the annealing spectrum. In general the presence of avoided level crossings demands an exponential increase in the annealing time with the system size which has consequences both for the efficiency of the algorithm and the required qubit coherence times. One promising avenue being explored to produce more favorable gap scaling is the introduction of nonstoquastic X X couplings in the form of a catalyst—of particular interest are catalysts which utilize accessible information about the optimization problem in their construction. Here we show extreme sensitivity of the effect of an X X catalyst to subtle changes in the encoding of the optimization problem. In particular, we observe that a targeted catalyst containing a single coupling can significantly reduce the gap closing with system size at an avoided level crossing. For slightly different encodings of the same problems however, these same catalysts result in closing gaps in the annealing spectrum. To understand the origin of these closing gaps, we study how the evolution of the ground-state vector is altered by the presence of the catalyst and find that the negative components of the ground-state vector are key to understanding the response of the gap spectrum. We also consider how and when these closing gaps could be utilized in diabatic quantum annealing protocols—a promising alternative to adiabatic quantum annealing in which transitions to higher energy levels are exploited to reduce the run time of the algorithm. Published by the American Physical Society 2024
Abstract In adiabatic quantum annealing, the speed with which an anneal can be run, while still achieving a high final ground state (GS) fidelity, is dictated by the size of the minimum gap that appears between the ground and first excited state in the annealing spectrum. To avoid the exponential slowdown associated with exponentially closing gaps, diabatic transitions to higher energy levels may be exploited in such a way that the system returns to the GS before the end of the anneal. In certain cases, this is facilitated by the original annealing spectrum. However, there are also examples where careful manipulation of the annealing Hamiltonian has been used to alter the spectrum to create a diabatic path to the GS. Since diabatic transitions depend on the evolution rate and the gap sizes in the spectrum, it is important to consider the sensitivity of any potential enhancement to changes in the anneal time as well as any parameters involved in the manipulation of the spectrum. We explore this sensitivity using annealing spectra containing an exponentially closing gap and an additional, tuneable, small gap created by a catalyst. We find that there is a trade-off between the precision needed in the catalyst strength and the anneal time in order to maintain the enhancement to the final GS fidelity.
The potential quantum speedup in solving optimization problems via adiabatic quantum annealing is often hindered by the closing of the energy gap during the anneal, especially when this gap scales exponentially with system size. In this work, we alleviate this bottleneck by demonstrating that for the NP-complete Maximum Weighted Independent Set (MWIS) problem, an informed choice of n -local catalysts (operators involving n qubits) can reopen the gap during the annealing process. By analyzing first-order phase transitions in toy instances of the MWIS problem, we first identify direct-tunneling catalysts that effectively eliminate the transition and provide an analytical discussion on when the sign of the catalyst influences its impact. We then reveal that n -local catalysts exponentially improve gap scaling and in certain scenarios are as effective as direct-tunnel coupling between two minima. Utilizing this understanding, we show that they also increase the efficiency of ground-state preparation via adiabatic quantum annealing in random graphs and analytically demonstrate the necessity of their placement across unfrustrated loops in the graph for effective performance in MWIS problems. Additionally, using a circuit implementation of the n -local catalyst (requiring 2 n nearest-neighbor gates), we demonstrate that both the circuit depth and the total number of gates required to solve the problem are reduced by several orders of magnitude when compared to the discrete-time version of traditional quantum annealing using local drivers. Our analysis suggests that nonlocal quantum fluctuations entangling multiple qubits as a catalyst are key to achieving the desired quantum advantage.
Quantum annealing is a promising algorithm for solving combinatorial optimization problems. It searches for the ground state of the Ising model, which corresponds to the optimal solution of a given combinatorial optimization problem. The guiding principle of quantum annealing is the adiabatic theorem in quantum mechanics, which guarantees that a system remains in the ground state of its Hamiltonian if the time evolution is sufficiently slow. According to the adiabatic theorem, the annealing time required for quantum annealing to satisfy the adiabaticity scales inversely proportional to the square of the minimum energy gap between the ground state and the first excited state during time evolution. As a result, finding the ground state becomes significantly more difficult when the energy gap is small, creating a major bottleneck in quantum annealing. Expanding the energy gap is one strategy for improving the performance of quantum annealing; however, its implementation in actual hardware remains difficult. This study proposes a method for efficiently solving instances with small energy gaps by introducing additional local terms to the Hamiltonian and exploiting the diabatic transition remaining in the small energy gap. The proposed method achieves an approximate quadratic speedup of the exponential scaling exponent in time to solution compared to the conventional quantum annealing. In addition, we investigate the transferability of the parameters obtained with the proposed method.
This paper explores the phenomenon of avoided level crossings in quantum annealing, a promising framework for quantum computing that may provide a quantum advantage for certain tasks. Quantum annealing (QA) involves letting a quantum system evolve according to the Schr\"odinger equation, with the goal of obtaining the optimal solution to an optimization problem through measurements of the final state. However, the continuous nature of quantum annealing makes analytical analysis challenging, particularly with regard to the instantaneous eigenenergies. The adiabatic theorem provides a theoretical result for the annealing time required to obtain the optimal solution with high probability, which is inversely proportional to the square of the minimum spectral gap. Avoided level crossings can create exponentially closing gaps, which can lead to exponentially long running times for optimization problems. In this paper, we use a perturbative expansion to derive a condition for the occurrence of an avoided level crossing during the annealing process. We then apply this condition to the MaxCut problem on bipartite graphs. We show that no exponentially small gaps arise for regular bipartite graphs, implying that QA can efficiently solve MaxCut in that case. On the other hand, we show that irregularities in the vertex degrees can lead to the satisfaction of the avoided level crossing occurrence condition. We provide numerical evidence to support this theoretical development, and discuss the relation between the presence of exponentially closing gaps and the failure of quantum annealing.
Abstract One of the main challenges in solving combinatorial optimisation problems with quantum annealers is the emergence of extremely small energy gaps between the ground state and the first excited state of the annealing Hamiltonian. These small gaps may be symptoms of an underlying first-order phase transition, which, according to the adiabatic theorem, can significantly extend the required anneal time, making practical implementation effectively infeasible. In this paper we demonstrate that attaching an XX-catalyst on all the edges of a graph upon which a MWIS (Maximum Weighted Independent Set) problem is defined, significantly enhances the minimum energy gap. Remarkably, our analysis shows that the smaller the energy gap, the more effective the catalyst is in opening it. This result is based on a detailed statistical analysis performed on a large number of randomly generated MWIS problem instances on both Erdõs–Rényi and Barabáasi–Albert graphs. We perform the analysis using both stoquastic and non-stoquastic catalysts.
In the computational model of quantum annealing, the size of the minimum gap between the ground state and the first excited state of the system is of particular importance, since it is inversely proportional to the running time of the algorithm. Thus, it is desirable to keep the gap as large as possible during the annealing process, since it allows the computation to remain under the protection of the adiabatic theorem while staying efficient. We propose steered quantum annealing as a new method to enlarge the gap throughout the process, in the case of diagonal final Hamiltonians, based on the exploitation of some assumptions we can make about the particular problem instance. In order to introduce this information, we propose beginning the anneal from a biased Hamiltonian that incorporates reliable assumptions about the final ground state. Our simulations show that this method yields a larger average gap throughout the whole computation, which results in an increased robustness of the overall annealing process.