Finite temperature quantum annealing solving exponentially small gap problem with non-monotonic success probability.

Closed-system quantum annealing is expected to sometimes fail spectacularly in solving simple problems for which the gap becomes exponentially small in the problem size. Much less is known about whether this gap scaling also impedes open-system quantum annealing. Here, we study the performance of a quantum annealing processor in solving such a problem: a ferromagnetic chain with sectors of alternating coupling strength that is classically trivial but exhibits an exponentially decreasing gap in the sector size. The gap is several orders of magnitude smaller than the device temperature. Contrary to the closed-system expectation, the success probability rises for sufficiently large sector sizes. The success probability is strongly correlated with the number of thermally accessible excited states at the critical point. We demonstrate that this behavior is consistent with a quantum open-system description that is unrelated to thermal relaxation, and is instead dominated by the system's properties at the critical point.

Temperature Scaling Law for Quantum Annealing Optimizers.

Physical implementations of quantum annealing unavoidably operate at finite temperatures. We point to a fundamental limitation of fixed finite temperature quantum annealers that prevents them from functioning as competitive scalable optimizers and show that to serve as optimizers annealer temperatures must be appropriately scaled down with problem size. We derive a temperature scaling law dictating that temperature must drop at the very least in a logarithmic manner but also possibly as a power law with problem size. We corroborate our results by experiment and simulations and discuss the implications of these to practical annealers.

Off-diagonal expansion quantum Monte Carlo.

We propose a Monte Carlo algorithm designed to simulate quantum as well as classical systems at equilibrium, bridging the algorithmic gap between quantum and classical thermal simulation algorithms. The method is based on a decomposition of the quantum partition function that can be viewed as a series expansion about its classical part. We argue that the algorithm not only provides a theoretical advancement in the field of quantum Monte Carlo simulations, but is optimally suited to tackle quantum many-body systems that exhibit a range of behaviors from "fully quantum" to "fully classical," in contrast to many existing methods. We demonstrate the advantages, sometimes by orders of magnitude, of the technique by comparing it against existing state-of-the-art schemes such as path integral quantum Monte Carlo and stochastic series expansion. We also illustrate how our method allows for the unification of quantum and classical thermal parallel tempering techniques into a single algorithm and discuss its practical significance.

Mean Field Analysis of Quantum Annealing Correction.

Quantum annealing correction (QAC) is a method that combines encoding with energy penalties and decoding to suppress and correct errors that degrade the performance of quantum annealers in solving optimization problems. While QAC has been experimentally demonstrated to successfully error correct a range of optimization problems, a clear understanding of its operating mechanism has been lacking. Here we bridge this gap using tools from quantum statistical mechanics. We study analytically tractable models using a mean-field analysis, specifically the p-body ferromagnetic infinite-range transverse-field Ising model as well as the quantum Hopfield model. We demonstrate that for p=2, where the phase transition is of second order, QAC pushes the transition to increasingly larger transverse field strengths. For p≥3, where the phase transition is of first order, QAC softens the closing of the gap for small energy penalty values and prevents its closure for sufficiently large energy penalty values. Thus QAC provides protection from excitations that occur near the quantum critical point. We find similar results for the Hopfield model, thus demonstrating that our conclusions hold in the presence of disorder.

Error-corrected quantum annealing with hundreds of qubits.

Quantum information processing offers dramatic speedups, yet is susceptible to decoherence, whereby quantum superpositions decay into mutually exclusive classical alternatives, thus robbing quantum computers of their power. This makes the development of quantum error correction an essential aspect of quantum computing. So far, little is known about protection against decoherence for quantum annealing, a computational paradigm aiming to exploit ground-state quantum dynamics to solve optimization problems more rapidly than is possible classically. Here we develop error correction for quantum annealing and experimentally demonstrate it using antiferromagnetic chains with up to 344 superconducting flux qubits in processors that have recently been shown to physically implement programmable quantum annealing. We demonstrate a substantial improvement over the performance of the processors in the absence of error correction. These results pave the way towards large-scale noise-protected adiabatic quantum optimization devices, although a threshold theorem such as has been established in the circuit model of quantum computing remains elusive.

Fluctuation theorems for quantum processes.

We present fluctuation theorems and moment generating function equalities for generalized thermodynamic observables and quantum dynamics described by completely positive trace preserving maps, with and without feedback control. Our results include the quantum Jarzynski equality and Crooks fluctuation theorem, and clarify the special role played by the thermodynamic work and thermal equilibrium states in previous studies. We show that for a specific class of generalized measurements, which include projective measurements, unitality replaces microreversibility as the condition for the physicality of the reverse process in our fluctuation theorems. We present an experimental application of our theory to the problem of extracting the system-bath coupling magnitude, which we do for a system of pairs of coupled superconducting flux qubits undergoing quantum annealing.

Experimental signature of programmable quantum annealing.

Quantum annealing is a general strategy for solving difficult optimization problems with the aid of quantum adiabatic evolution. Both analytical and numerical evidence suggests that under idealized, closed system conditions, quantum annealing can outperform classical thermalization-based algorithms such as simulated annealing. Current engineered quantum annealing devices have a decoherence timescale which is orders of magnitude shorter than the adiabatic evolution time. Do they effectively perform classical thermalization when coupled to a decohering thermal environment? Here we present an experimental signature which is consistent with quantum annealing, and at the same time inconsistent with classical thermalization. Our experiment uses groups of eight superconducting flux qubits with programmable spin-spin couplings, embedded on a commercially available chip with >100 functional qubits. This suggests that programmable quantum devices, scalable with current superconducting technology, implement quantum annealing with a surprising robustness against noise and imperfections.