Explore the vast range of titles available.

Quantum many-body systems whose Hamiltonians are non-stoquastic, i.e., have positive off-diagonal matrix elements in a given basis, are known to pose severe limitations on the efficiency of Quantum Monte Carlo algorithms designed to simulate them, due to the infamous sign problem. We study the computational complexity associated with ‘curing’ non-stoquastic Hamiltonians, i.e., transforming them into sign-problem-free ones. We prove that if such transformations are limited to single-qubit Clifford group elements or general single-qubit orthogonal matrices, finding the curing transformation is NP-complete. We discuss the implications of this result. Non-stoquastic Hamiltonians are known to be hard to simulate due to the infamous sign problem. Here, the authors study the computational complexity of transforming such Hamiltonians into stoquastic ones and prove that the task is NP-complete even for the simplest class of transformations.

Recent advances in quantum technology have led to the development and manufacturing of experimental programmable quantum annealing optimizers that contain hundreds of quantum bits. These optimizers, commonly referred to as ‘D-Wave’ chips, promise to solve practical optimization problems potentially faster than conventional ‘classical’ computers. Attempts to quantify the quantum nature of these chips have been met with both excitement and skepticism but have also brought up numerous fundamental questions pertaining to the distinguishability of experimental quantum annealers from their classical thermal counterparts. Inspired by recent results in spin-glass theory that recognize ‘temperature chaos’ as the underlying mechanism responsible for the computational intractability of hard optimization problems, we devise a general method to quantify the performance of quantum annealers on optimization problems suffering from varying degrees of temperature chaos: A superior performance of quantum annealers over classical algorithms on these may allude to the role that quantum effects play in providing speedup. We utilize our method to experimentally study the D-Wave Two chip on different temperature-chaotic problems and find, surprisingly, that its performance scales unfavorably as compared to several analogous classical algorithms. We detect, quantify and discuss several purely classical effects that possibly mask the quantum behavior of the chip.

Quantum annealing has the potential to provide a speedup over classical algorithms in solving optimization problems. Just as for any other quantum device, suppressing Hamiltonian control errors will be necessary before quantum annealers can achieve speedups. Such analog control errors are known to lead to J-chaos, wherein the probability of obtaining the optimal solution, encoded as the ground state of the intended Hamiltonian, varies widely depending on the control error. Here, we show that J-chaos causes a catastrophic failure of quantum annealing, in that the scaling of the time-to-solution metric becomes worse than that of a deterministic (exhaustive) classical solver. We demonstrate this empirically using random Ising spin glass problems run on the two latest generations of the D-Wave quantum annealers. We then proceed to show that this doomsday scenario can be mitigated using a simple error suppression and correction scheme known as quantum annealing correction (QAC). By using QAC, the time-to-solution scaling of the same D-Wave devices is improved to below that of the classical upper bound, thus restoring hope in the speedup prospects of quantum annealing.

The Dyson series is an infinite sum of multi-dimensional time-ordered integrals, which serves as a formal representation of the quantum time-evolution operator in the interaction-picture. Using the mathematical tool of divided differences, we introduce an alternative representation for the series that is entirely free from both time ordering and integrals. In this new formalism, the Dyson expansion is given as a sum of efficiently-computable divided differences of the exponential function, considerably simplifying the calculation of the Dyson expansion terms, while also allowing for time-dependent perturbation calculations to be performed directly in the Schrödinger-picture. We showcase the utility of this novel representation by studying a number of use cases. We also discuss several immediate applications.

Estimating the density of states (DOS) of systems with rugged free energy landscapes is a notoriously difficult task of the utmost importance in many areas of physics ranging from spin glasses to biopolymers. DOS estimation has also recently become an indispensable tool for the benchmarking of quantum annealers when these function as samplers. Some of the standard approaches suffer from a spurious convergence of the estimates to metastable minima, and these cases are particularly hard to detect. Here, we introduce a sampling technique based on population annealing enhanced with a multi-histogram analysis and report on its performance for spin glasses. We demonstrate its ability to overcome the pitfalls of other entropic samplers, resulting in some cases in large scaling advantages that can lead to the uncovering of new physics. The new technique avoids some inherent difficulties in established approaches and can be applied to a wide range of systems without relevant tailoring requirements. Benchmarking of the studied techniques is facilitated by the introduction of several schemes that allow us to achieve exact counts of the degeneracies of the tested instances.

The debate around the potential superiority of quantum annealers over their classical counterparts has been ongoing since the inception of the field. Recent technological breakthroughs, which have led to the manufacture of experimental prototypes of quantum annealing optimizers with sizes approaching the practical regime, have reignited this discussion. However, the demonstration of quantum annealing speedups remains to this day an elusive albeit coveted goal. We examine the power of quantum annealers to provide a different type of quantum enhancement of practical relevance, namely, their ability to serve as useful samplers from the ground-state manifolds of combinatorial optimization problems. We study, both numerically by simulating stoquastic and non-stoquastic quantum annealing processes, and experimentally, using a prototypical quantum annealing processor, the ability of quantum annealers to sample the ground-states of spin glasses differently than thermal samplers. We demonstrate that (i) quantum annealers sample the ground-state manifolds of spin glasses very differently than thermal optimizers (ii) the nature of the quantum fluctuations driving the annealing process has a decisive effect on the final distribution, and (iii) the experimental quantum annealer samples ground-state manifolds significantly differently than thermal and ideal quantum annealers. We illustrate how quantum annealers may serve as powerful tools when complementing standard sampling algorithms.

The quantum adiabatic unstructured search algorithm is one of only a handful of quantum adiabatic optimization algorithms to exhibit provable speedups over their classical counterparts. With no fault tolerance theorems to guarantee the resilience of such algorithms against errors, understanding the impact of imperfections on their performance is of both scientific and practical significance. We study the robustness of the algorithm against various types of imperfections: limited control over the interpolating schedule, Hamiltonian misspecification, and interactions with a thermal environment. We find that the unstructured search algorithm's quadratic speedup is generally not robust to the presence of any one of the above non-idealities, and in some cases we find that it imposes unrealistic conditions on how the strength of these noise sources must scale to maintain the quadratic speedup.

We describe an optimized, self-correcting procedure for the Bayesian inference of pure quantum states. By analyzing the history of measurement outcomes at each step, the procedure returns the most likely pure state, as well as the optimal basis for the measurement that is to follow. The latter is chosen to maximize, on average, the fidelity of the most likely state after the measurement. We also consider a practical variant of this protocol, where the available measurement bases are restricted to certain limited sets of bases. We demonstrate the success of our method by considering in detail the single-qubit and two-qubit cases, and comparing the performance of our method against other existing methods.

An amendment to this paper has been published and can be accessed via a link at the top of the paper.