Session W70: Quantum Annealer Characterization

A Parameter Setting Heuristic for the Quantum Alternating Operator Ansatz

The Quantum Alternating Operator Ansatz, a generalized approach building on the Quantum Approximate Optimization Algorithm, is a widely studied method for tackling optimization problems. Finding high-quality parameters efficiently for QAOA remains a major challenge. In this work we introduce a classical strategy for parameter setting, especially suitable for cases in which the number of distinct cost values grows only polynomially with the problem size. Our approach is based on the observation that if classical variable configurations with the same cost have the same quantum amplitudes at a given step, which we denote as Perfect Homogeneity, then under mild assumptions one may efficiently apply another QAOA step or compute expectation values classically. High overlaps between QAOA states and states with Perfect Homogeneity have been empirically observed in a number of settings. Hence, we define a Classical Homogeneous Proxy for QAOA in which Perfect Homogeneity is asserted to hold exactly. Given a problem instance drawn from a class and QAOA circuit depth, we classically determine good parameters for the the proxy, and then incorporate these parameters into the corresponding QAOA circuit, an approach we call the Homogeneous Heuristic for Parameter Setting. We numerically examine this heuristic for MaxCut on unweighted random graphs. For depth l=3, we demonstrate that the heuristic is easily able to find parameters that match approximation ratios corresponding to previously-found globally optimized approaches. For depth l   

Digital adiabatic state preparation error scales better than you might expect

Adiabatic time evolution can be used to prepare a complicated quantum many-body state from one that is easier to synthesize and Trotterization can be used to implement such an evolution digitally. The complex interplay between non-adiabaticity and digitization influences the infidelity of this process. We prove that the first-order Trotterization of a complete adiabatic evolution has a cumulative infidelity that scales as O(T^-2 δt²) instead of O(T δt) expected from general Trotter error bounds, where δt is the time step and T is the total time. This result explains why, despite increasing T, infidelities for fixed-δt digitized evolutions still decrease for a wide variety of Hamiltonians. It also establishes a correspondence between the Quantum Approximate Optimization Algorithm (QAOA) and digitized quantum annealing.

SNL is managed and operated by NTESS under DOE NNSA contract DE-NA0003525. This paper describes objective technical results and analysis. Any subjective views or opinions that might be expressed in the abstract do not necessarily represent the views of the U.S. Department of Energy or the United States Government.   

Strategies for simulating adiabatic time evolution on noisy quantum computers

Recent experiments on quantum hardware are beginning to show advantage, although in very strict cases, over classical computers. While these novel qubits are being developed, it is instructive to study their dynamics on available noisy intermediate-scale quantum (NISQ) hardware. Adiabatic time evolution has emerged in various application sets in quantum simulation. They range from simulating time evolution of Hamiltonians to solving optimization problems where the solution is obtained through simulating a slowly varying Hamiltonian that evolves a known ground state into an unknown desired ground state. We study various strategies for breaking down the time evolution into single-qubit and two-qubit operations with a special emphasis on error analysis of Trotter-Suzuki expansion, adiabatic conditions, and hardware error. We focus on a few sample systems such as the Ising chain as well as the Fermi-Hubbard Hamiltonians.   

Performance and limitations of the QAOA at constant levels on different problems

The Quantum Approximate Optimization Algorithm (QAOA) is a general

purpose quantum algorithm designed for combinatorial optimization. We

analyze its expected performance and prove concentration properties at

any constant level (number of layers) on ensembles of random

combinatorial optimization problems in the infinite size limit. These

ensembles include mixed spin models and Max-q-XORSAT on sparse random

hypergraphs. We then show that the performance of the QAOA at constant

levels for the pure q-spin model matches asymptotically the ones for

Max-q-XORSAT on random sparse Erdos-Renyi hypergraphs and every

large-girth regular hypergraph. Through this correspondence, we

establish that the average-case value produced by the QAOA at constant

levels is bounded away from optimality for pure q-spin models when q ≥

4 and is even. This limitation gives a hardness of approximation

result for quantum algorithms in a new regime where the whole graph is

seen. Furthermore, we also derive analytical expressions for the

performance of the QAOA on the spiked tensor model at low-depth and

compare it to the classical power iteration method, shedding

additional light on the comparative power of classical and quantum

algorithms for optimization.   

Adiabatic oracle for Grover's algorithm

Grover's search algorithm was originally proposed for circuit-based quantum computers. A crucial part of it is to query an oracle, which is a specific unitary operation. Generation of this oracle is formally beyond the original algorithm design. Here, we propose a realization of Grover's oracle for a large class of searching problems using a quantum annealing step. The time of this step grows only logarithmically with the size of the database. This suggests an efficient path to application of Grover's algorithm to practically important problems, such as finding the ground state of a Hamiltonian with a spectral gap over its ground state.   

Quantum annealing with error mitigation

Quantum annealing (QA) is one of the efficient methods to calculate the ground state energy of a problem Hamiltonian. If an adiabatic condition is satisfied, we can accurately estimate the ground state energy by using QA without noise. However, in actual physical implementation, systems suffer from decoherence. On the other hand, much effort has been paid into the noisy intermediate-scale quantum (NISQ) computation research. For practical NISQ computation, many error mitigation (EM) methods have been devised to remove noise effects. Here, we propose a QA strategy combined with the EM method called dual-state purification to suppress the effects of decoherence. Our protocol consists of four parts; conventional dynamics, single-qubit projective measurements, Hamiltonian dynamics corresponding to an inverse map of the first dynamics, and post-processing measurement results. Importantly, our protocol works without two-qubit gates, so our protocol is suitable for the devices designed for QA. We also provide numerical calculations to show that our protocol leads to a more accurate estimation of the ground energy than the conventional QA under decoherence.   

Catastrophic failure of quantum annealing owing to non-stoquastic Hamiltonian and its avoidance by decoherence

Quantum annealing (QA) is a promising method for solving combinatorial optimization problems whose solutions are embedded into a ground state of the Ising Hamiltonian. This method employs two types of Hamiltonians: a driver Hamiltonian and a problem Hamiltonian. After a sufficiently slow change from the driver Hamiltonian to the problem Hamiltonian, we can obtain the target ground state that corresponds to the solution. The inclusion of non-stoquastic terms in the driver Hamiltonian is believed to enhance the efficiency of the QA. Meanwhile, decoherence is regarded as of the main obstacles for QA. Here, we present examples showing that non-stoaquastic Hamiltonians can lead to catastrophic failure of QA, whereas a certain decoherence process can be used to avoid such failure. More specifically, when we include anti-ferromagnetic interactions (i.e., typical nonstoquastic terms) in the Hamiltonian, we are unable to prepare the target ground state even with an infinitely long annealing time for some specific cases. In our example, owing to a symmetry, the Hamiltonian is block-diagonalized, and a crossing occurs during the QA, which leads to a complete failure of the ground-state search. Moreover, we show that, when we add a certain type of decoherence, we can obtain the ground state after QA for these cases. This is because, even when symmetry exists in isolated quantum systems, the environment breaks the symmetry. Our counter intuitive results provide a deep insight into the fundamental mechanism of QA.   

Adiabatic condition for quantum annealing revisited

Quantum annealing (QA) is a promising method for solving optimization problems. If the adiabatic condition is satisfied in the QA, the ground state of the problem Hamiltonian can be obtained. The adiabatic condition consists of a transition matrix of time derivative of Hamiltonian and an energy gap (EG) between the ground and excited states. It is supposed that scaling of the EG provides criteria for whether the optimization problem is hard or not. In this presentation, we propose a general framework that gives counter-examples to this criteria: QA with a constant annealing time fails although the EG is constant, i.e., O(L0) during QA, where L is the problem size. The key idea of our analysis is to add a penalty term in the Hamiltonian, which does not change the eigenstate of Hamiltonian but change the eigenvalue. We show a prescription to construct the case where the transition matrix becomes exponentially large with the penalty term. By adding such a penalty term in the adiabatic Grover search, we provide a concrete example, and we analytically show that the transition matrix becomes exponentially large and the magnetization has a discontinuity, i.e., first phase transition occurs despite an EG that scales as O(L0). Moreover, we show that, in this example, the success probability of QA becomes exponentially small as we increase the problem size L. This paper was based on results obtained from a project, JPNP16007, commissioned by the New Energy and Industrial Technology Development Organization (NEDO), Japan.   

Multiple Target Tracking and Filtering using Bayesian Diabatic Quantum Annealing

We present a hybrid quantum/classical algorithm to solve an NP-hard combinatorial problem called the multiple target data association (MTDA) and tracking problem. We use diabatic quantum annealing (DQA) to enumerate the low energy, or high probability, feasible assignments, and we use a classical computer to find the Bayesian expected mean track estimate by summing over these assignments. We demonstrate our hybrid quantum/classical approach on a simple example. This may be the first demonstration of a Bayesian hybrid quantum-classical multiple target tracking filter. We contrast our DQA method with the adiabatic quantum computing (AQC) approach to MTDA. We give a theoretical overview of DQA and characterize some of the technical limitations of using quantum annealers in this novel diabatic modality.   

Designing Quantum Annealing Schedules with Bayesian Optimization

In Quantum Annealing (QA) the ground state of a target Hamiltonian is prepared by continuously deforming an initial Hamiltonian, which has an easy-to-prepare ground state, into the target Hamiltonian. The time evolution generated by this time dependent Hamiltonian depends on the schedule by which this transformation is performed. We investigate the use of Bayesian Optimization (BO), a global optimization design strategy useful for optimizing expensive-to-evaluate functions, to design optimized QA schedules. We test different parametrizations of QA schedules and use BO to optimize them in terms of several figures of merit. We numerically demonstrate significant improvements using BO designed QA schedules for the p-spin model. In addition, BO is used to design paths for Reverse Annealing (RA), a variant of QA which uses an approximation of the final ground state as the initial state, which has been shown to enable an exponential speedup over QA for the p-spin model. BO is able to design a RA schedule which achieves such a speedup without a priori knowing the spectral properties of the system. Finally, we use BO designed QA to solve combinatorial optimization problems and benchmark our results using Simulated Annealing.

    

Robustness of diabatic speedup in quantum annealing

To avoid the exponential slowdown associated with closing gaps in quantum annealing, diabatic transitions to higher energy levels may be exploited in such a way that the system returns to the ground state before the end of the anneal. In certain cases, this is facilitated by the original annealing spectrum however the use of additional catalyst Hamiltonians has also been explored to produce a diabatic path to the ground state (see Feinstein et al., arXiv:2203.06779). Since the transitions depend on the evolution rate, it is important to consider the sensitivity of any potential speedup to the annealing time. 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 minimising the additional gap results in robustness to changes in the annealing time. However, as the gap size is increased, the final ground-state overlap becomes increasingly sharply peaked as a function of anneal time. This suggests a trade-off between the precision needed in the catalyst strength and the anneal time that is critical in diabatic annealing.    

Quantum critical dynamics in a 5000-qubit programmable spin glass

Over two decades ago, experiments on disordered alloys suggested that spin glasses can be brought into low-energy states faster by annealing quantum fluctuations than by conventional thermal annealing. Due to the importance of spin glasses as a paradigmatic computational testbed, reproducing this phenomenon in a programmable system has remained a central challenge in quantum optimization. Here we achieve this goal by realizing quantum critical spin-glass dynamics with a superconducting quantum annealer. We measure dynamics in 3D spin glasses on thousands of qubits, where simulation of many-body quantum dynamics is intractable. We extract critical exponents and show agreement with generalized Kibble-Zurek dynamics in the critical region. Finally, we experimentally and theoretically demonstrate scaling advantage of quantum annealing versus analogous Monte Carlo algorithms in reducing energy as a function of annealing time.