arXiv:2106.04864 · Physical Review A

Quantum annealing with trigger Hamiltonians: Application to 2-satisfiability and nonstoquastic problems

Vrinda Mehta, Fengping Jin, Hans A. De Raedt, Kristel F. L. Michielsen

Published Sep 27, 2021• 13 citations

Abstract

We study the performance of quantum annealing for two sets of problems, namely, 2-satisfiability (2-SAT) problems represented by Ising-type Hamiltonians and nonstoquastic problems which are obtained by adding extra couplings to the 2-SAT problem Hamiltonians. In addition, we add to the transverse Ising-type Hamiltonian used for quantum annealing a third term, the trigger Hamiltonian with ferromagnetic or antiferromagnetic couplings, which vanishes at the beginning and end of the annealing process. We also analyze some problem instances using the energy spectrum, average energy or overlap of the state during the evolution with the instantaneous low-lying eigenstates of the Hamiltonian, and identify some nonadiabatic mechanisms which can enhance the performance of quantum annealing.

DOI: 10.1103/physreva.104.032421

Related papers

Quantum annealing for hard 2-satisfiability problems: Distribution and scaling of minimum energy gap and success probability

Vrinda Mehta, Fengping Jin, Hans A. De Raedt +1 more

In recent years, quantum annealing has gained the status of being a promising candidate for solving various optimization problems. Using a set of hard 2-satisfiability (2-SAT) problems, consisting of problems of up to 18 variables, we analyze the scaling complexity of the quantum annealing algorithm and study the distributions of the minimum energy gap and the success probability. We extend the analysis of the standard quantum annealing Hamiltonian by introducing an additional term, the trigger Hamiltonian, which can be of two types: ferromagnetic and antiferromagnetic. We use these trigger Hamiltonians to study their influence on the success probability for solving the selected 2-SAT problems. We find that although the scaling of the runtime is exponential for the standard and modified quantum annealing Hamiltonians, the scaling constant in the case of adding the trigger Hamiltonians can be significantly smaller. Furthermore, certain choices for the trigger Hamiltonian and annealing times can result in a better scaling than that for simulated annealing. Finally, we also use the quantum annealers of D-Wave Systems Inc. to study their performance in solving the 2-SAT problems and compare it with the simulation results.

arXiv:2202.00118Physical Review AJun 3, 202211 citations

Quantum Annealing with Anneal Path Control: Application to 2-SAT Problems with Known Energy Landscapes

Ting-Jui Hsu, Fengping Jin, Christian Seidel +3 more

We study the effect of the anneal path control per qubit, a new user control feature offered on the D-Wave 2000Q quantum annealer, on the performance of quantum annealing for solving optimization problems by numerically solving the time-dependent Schrödinger equation for the time-dependent Hamiltonian modeling the annealing problems. The anneal path control is thereby modeled as a modified linear annealing scheme, resulting in an advanced and retarded scheme. The considered optimization problems are 2-SAT problems with 12 Boolean variables, a known unique ground state and a highly degenerate first excited state. We show that adjustment of the anneal path control can result in a widening of the minimal spectral gap by one or two orders of magnitude and an enhancement of the success probability of finding the solution of the optimization problem. We scrutinize various iterative methods based on the spin floppiness, the average spin value, and on the average energy and describe their performance in boosting the quantum annealing process.

arXiv:1810.00194Communications in Computational PhysicsApr 28, 201910 citations

Validating a two-qubit nonstoquastic Hamiltonian in quantum annealing

Tameem Albash

We propose a two-qubit experiment for validating tunable antiferromagnetic XX interactions in quantum annealing. Such interactions allow the time-dependent Hamiltonian to be nonstoquastic, and the instantaneous ground state can have negative amplitudes in the computational basis. Our construction relies on how the degeneracy of the Ising Hamiltonian's ground states is broken away from the end point of the anneal: above a certain value of the antiferromagnetic XX interaction strength, the perturbative ground state at the end of the anneal changes from a symmetric to an antisymmetric state. This change is associated with a suppression of one of the Ising ground states, which can then be detected using solely computational basis measurements. We show that a semiclassical approximation of the annealing protocol fails to reproduce this feature, making it a candidate ``quantum signature'' of the evolution.

arXiv:1909.06333Physical Review AJan 9, 20203 citations

Nonstoquastic Hamiltonians and quantum annealing of an Ising spin glass

Layla Hormozi, Ethan Brown, Giuseppe Carleo +1 more

Quantum annealers are computing machines that utilize quantum effects to solve hard optimization problems. Understanding the circumstances under which quantum annealers are more efficient than other optimization methods is a challenging open problem. A clue to this conundrum comes from studying the complexity of quantum annealers. In general, the complexity of a physical system relates to how efficiently the system can be simulated by classical algorithms. One then asks: if some class of quantum annealers are hard to simulate classically, are they also more powerful optimization machines? Here, the authors study quantum annealers belonging to two different complexity classes: the so-called ``stoquastic'' systems, which can be efficiently simulated with classical algorithms, and ``nonstoquastic'' systems, currently with no efficient classical treatment. Applied to a prototypical optimization problem, the authors observe that, on average, the stoquastic systems perform better on easier instances of the problem, while the more complex nonstoquastic annealers show significant advantage when applied to the hardest instances. The authors conjecture that the performance of the nonstoquastic Hamiltonians is closely related to their internal structure during the annealing process and elucidate how properties such as magnetic frustration can play a key role in devising more powerful quantum annealers.

arXiv:1609.06558Physical review. B./Physical review. BMay 15, 201797 citations

Message-passing Algorithm of Quantum Annealing with Nonstoquastic Hamiltonian

Masayuki Ohzeki

Quantum annealing (QA) is a generic method for solving optimization problems using fictitious quantum fluctuation. The current device performing QA involves controlling the transverse field; it is classically simulatable by using the standard technique for mapping the quantum spin systems to the classical ones. In this sense, the current system for QA is not powerful despite utilizing quantum fluctuation. Hence, we developed a system with a time-dependent Hamiltonian consisting of a combination of the formulated Ising model and the "driver" Hamiltonian with only quantum fluctuation. In the previous study, for a fully connected spin model, quantum fluctuation can be addressed in a relatively simple way. We proved that the fully connected antiferromagnetic interaction can be transformed into a fluctuating transverse field and is thus classically simulatable at sufficiently low temperatures. Using the fluctuating transverse field, we established several ways to simulate part of the nonstoquastic Hamiltonian on classical computers. We formulated a message-passing algorithm in the present study. This algorithm is capable of assessing the performance of QA with part of the nonstoquastic Hamiltonian having a large number of spins. In other words, we developed a different approach for simulating the nonstoquastic Hamiltonian without using the quantum Monte Carlo technique. Our results were validated by comparison to the results obtained by the replica method.

arXiv:1901.06901Journal of the Physical Society of JapanApr 17, 20197 citations

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

Takashi Imoto, Yuichiro Matsuzaki

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 non-stoquastic 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.

arXiv:2209.10983Sep 22, 20220 citations