Recent tests performed on the D-Wave Two quantum annealer have revealed no clear evidence of speedup over conventional silicon-based technologies. Here we present results from classical parallel-tempering Monte Carlo simulations combined with isoenergetic cluster moves of the archetypal benchmark problem---an Ising spin glass---on the native chip topology. Using realistic uncorrelated noise models for the D-Wave Two quantum annealer, we study the best-case resilience, i.e., the probability that the ground-state configuration is not affected by random fields and random-bond fluctuations found on the chip. We thus compute classical upper-bound success probabilities for different types of disorder used in the benchmarks and predict that an increase in the number of qubits will require either error correction schemes or a drastic reduction of the intrinsic noise found in these devices. We restrict this study to the exact ground state, however, the approach can be trivially extended to the inclusion of excited states if the success metric is relaxed. We outline strategies to develop robust, as well as hard benchmarks for quantum annealing devices, as well as any other (black box) computing paradigm affected by noise.
Recent tests performed on the D-Wave Two quantum annealer have revealed no clear evidence of speedup over conventional silicon-based technologies. Here we present results from classical parallel-tempering Monte Carlo simulations combined with isoenergetic cluster moves of the archetypal benchmark problem---an Ising spin glass---on the native chip topology. Using realistic uncorrelated noise models for the D-Wave Two quantum annealer, we study the best-case resilience, i.e., the probability that the ground-state configuration is not affected by random fields and random-bond fluctuations found on the chip. We thus compute classical upper-bound success probabilities for different types of disorder used in the benchmarks and predict that an increase in the number of qubits will require either error correction schemes or a drastic reduction of the intrinsic noise found in these devices. We restrict this study to the exact ground state, however, the approach can be trivially extended to the inclusion of excited states if the success metric is relaxed. We outline strategies to develop robust, as well as hard benchmarks for quantum annealing devices, as well as any other (black box) computing paradigm affected by noise.
There has been considerable progress in the design and construction of quantum annealing devices. However, a conclusive detection of quantum speedup over traditional silicon-based machines remains elusive, despite multiple careful studies. In this work we outline strategies to design hard tunable benchmark instances based on insights from the study of spin glasses - the archetypal random benchmark problem for novel algorithms and optimization devices. We propose to complement head-to-head scaling studies that compare quantum annealing machines to state-of-the-art classical codes with an approach that compares the performance of different algorithms and/or computing architectures on different classes of computationally hard tunable spin-glass instances. The advantage of such an approach lies in having to only compare the performance hit felt by a given algorithm and/or architecture when the instance complexity is increased. Furthermore, we propose a methodology that might not directly translate into the detection of quantum speedup, but might elucidate whether quantum annealing has a "`quantum advantage" over corresponding classical algorithms like simulated annealing. Our results on a 496 qubit D-Wave Two quantum annealing device are compared to recently-used state-of-the-art thermal simulated annealing codes.
Spin glasses are experiencing a revival due to applications in quantum information\ntheory. In particular, they are the archetypal native benchmark problem for quantum annealing\nmachines. Furthermore, they find applications in fields as diverse as satisfiability,\nneural networks, and general combinatorial optimization problems. As such, developing\nand improving algorithms and methods to study these computationally complex systems\nis of paramount importance to many disciplines. This body of work attempts to attack\nthe problem of solving combinatorial optimization problems by simulating spin glasses\nfrom three sides: classical algorithm development, suggestions for quantum annealing\ndevice design, and improving measurements in realistic physical systems with inherent\nnoise. I begin with the introduction of a cluster algorithm based on Houdayer’s cluster algorithm\nfor two-dimensional Ising spin-glasses that is applicable to any space dimension\nand speeds up thermalization by several orders of magnitude at low temperatures where\nprevious algorithms have difficulty. I show improvement for the D-Wave chimera topology\nand the three-dimensional cubic lattice that increases with the size of the problem.\nOne consequence of adding cluster moves is that for problems with degenerate solutions,\nground-state sampling is improved. I demonstrate an ergodic algorithm to sample ground\nstates through the use of simple Monte Carlo with parallel tempering and cluster moves.\nIn addition, I present a non-ergodic algorithm to generate new solutions from a bank of\nknown solutions. I compare these results against results from quantum annealing utilizing\nthe D-Wave Inc. quantum annealing device. Finally, I present an algorithm for improving\nthe recovery of ground-state solutions from problems with noise by using thermal fluctuations\nto infer the correct solution at the Nishimori temperature. While this method has been\ndemonstrated analytically and numerically for trivial ferromagnetic and Gaussian distributions, a useful metric for more complex Gaussian distributions with added Gaussian noise\nis unavailable. We show improved recovery of numerical solutions on the chimera graph\nwith a ferromagnetic distribution and added Gaussian noise. Next, I direct my focus to the\ndesign of future generations of quantum annealers. The first design is the two-dimensional\nsquare-lattice bimodal spin glass with next-nearest ferrromagnetic interactions proposed\nby Lemke and Campbell claimed to exhibit a finite-temperature spin-glass state for a particular\nrelative strength of the next-nearest to nearest neighbor interactions. Our results\nfrom finite-temperature simulations show the system is in a paramagnetic state in the thermodynamic\nlimit, thus not useful for quantum annealing device designs that would benefit\nfrom a spin-glass phase transition. The second design is the diluted next-nearest neighbor\nIsing spin-glass with Gaussian interactions in an attempt to improve the estimation\nof critical parameter with smaller system sizes by implementing averaging of observables\nover different graph dilutions. To date, this model has shown no improvement. Finally,\nI make suggestions for the choice of distributions of interactions that are robust to noise\nand present a method for using previously unaccessible continuous distributions. I begin\nwith showing the best-case performance of quantum annealing devices. I show results for\nthe resilience, the probability that the ground-state solution has changed due to inherent\nanalog noise in the device, and present strategies for developing robust instance classes.\nThe analog noise is also detrimental to interactions chosen from continuous distributions.\nUsing Gaussian quadratures, I present a method for discretizing continuous distributions\nto reduce noise effects. Simulations on the D-Wave show that the average residual of\nthe ground-state energy with the true ground-state energy is calculated and shown to be\nsmaller in the case of the discrete distribution.
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.
Programmable quantum annealers can realize real-time dynamics of frustrated transverse-field Ising models on large, nontrivial graphs. Recent work by King et al. argued that the classical simulation of such experiments would require exponential computational resources for classical methods such as tensor networks and neural quantum states. Here, we numerically simulate the D-Wave spin-glass annealing protocol with time-dependent variational Monte Carlo (t-VMC) using a correlator state tailored to spin-glass dynamics. For the two-dimensional cylinder, three-dimensional dimer, diamond, and biclique instances considered, at annealing times of 7 and 20 ns, we show that systematically increasing the variational ansatz size enables t-VMC to approximate the final two-spin correlation errors of the quantum processing unit (QPU). We also perform an accurate large-scale simulation of a challenging biclique instance for which no other variational method is known to work, and we find close agreement with the quantum annealer. Through ablation studies, we identify poor Markov-chain mixing, high-variance local-energy estimators, and stochastic Runge-Kutta error estimates as the principal numerical failure modes. We address these numerical issues by using parallel tempering, blurred sampling and an importance-weighted differential equation solver, thereby clarifying the numerical requirements for stable, large-scale t-VMC simulations. Our results extend the frontier of classical simulation while providing a realistic assessment of the computational costs of simulating quantum dynamics at this scale.
Growing interest in quantum computers and artificial intelligence has fueled several innovations in recent years with regards to machine learning. With the construction of the first experimental quantum annealers by D-Wave, attaining the significant speedup provided by a quantum computer seems within reach. However, recent tests bring into question the degree to which these quantum effects are being utilized. The presence of temperature chaos when solving for the ground-state energy of a spin-glass system and the unfavorable scaling with classical hardness suggest that the D-Wave may really be a semiclassical machine. Using a state-of-the-art parallel tempering code and by using artificial neural networks and t-distributed stochastic neighbor embedding, we search for features in spin-glass instances that cause temperature chaos, and by extension attempt to gain some insight into the performance and scaling problems of the D-Wave quantum computer. As a result, we found that temperature chaos must be caused by structures deeper than the interactions themselves.
Abstract 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 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 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.