Search

Sampling a diverse set of high-quality solutions for hard optimization problems is of great practical relevance in many scientific disciplines and applications, such as artificial intelligence and operations research. One of the main open problems is the lack of ergodicity, or mode collapse, for typical stochastic solvers based on Monte Carlo techniques leading to poor generalization or lack of robustness to uncertainties. Currently, there is no universal metric to quantify such performance deficiencies across various solvers. Here, we introduce a new diversity measure for quantifying the number of independent approximate solutions for NP-hard optimization problems. To test this metric, we compare the sampling power of various quantum annealing strategies. We show that the inhomogeneous quantum annealing schedules can redistribute and suppress the emergence of topological defects by controlling space-time separated critical fronts, leading to an advantage over standard quantum annealing schedules with respect to both Time-To-Solution (TTS) and Time-To-Diversity (TTD) for finding rare solutions. Using Path-Integral Monte Carlo simulations for up to 1600 qubits, we demonstrate that non-equilibrium driving of quantum fluctuations, guided by efficient approximate tensor network contractions, can significantly reduce the fraction of hard instances for random frustrated 2D spin-glasses with local fields. Specifically, we observe that by creating a class of algorithmic quantum phase transitions the diversity of solutions can be enhanced by up to 40% with the fraction of hard-to-sample instances reducing by more than 25%., Comment: 12 pages, 4 figures, references updated

Realizing the potential of quantum computing will require achieving sufficiently low logical error rates. Many applications call for error rates in the $10^{-15}$ regime, but state-of-the-art quantum platforms typically have physical error rates near $10^{-3}$. Quantum error correction (QEC) promises to bridge this divide by distributing quantum logical information across many physical qubits so that errors can be detected and corrected. Logical errors are then exponentially suppressed as the number of physical qubits grows, provided that the physical error rates are below a certain threshold. QEC also requires that the errors are local and that performance is maintained over many rounds of error correction, two major outstanding experimental challenges. Here, we implement 1D repetition codes embedded in a 2D grid of superconducting qubits which demonstrate exponential suppression of bit or phase-flip errors, reducing logical error per round by more than $100\times$ when increasing the number of qubits from 5 to 21. Crucially, this error suppression is stable over 50 rounds of error correction. We also introduce a method for analyzing error correlations with high precision, and characterize the locality of errors in a device performing QEC for the first time. Finally, we perform error detection using a small 2D surface code logical qubit on the same device, and show that the results from both 1D and 2D codes agree with numerical simulations using a simple depolarizing error model. These findings demonstrate that superconducting qubits are on a viable path towards fault tolerant quantum computing.

Quantum many-body systems display rich phase structure in their low-temperature equilibrium states. However, much of nature is not in thermal equilibrium. Remarkably, it was recently predicted that out-of-equilibrium systems can exhibit novel dynamical phases that may otherwise be forbidden by equilibrium thermodynamics, a paradigmatic example being the discrete time crystal (DTC). Concretely, dynamical phases can be defined in periodically driven many-body localized systems via the concept of eigenstate order. In eigenstate-ordered phases, the entire many-body spectrum exhibits quantum correlations and long-range order, with characteristic signatures in late-time dynamics from all initial states. It is, however, challenging to experimentally distinguish such stable phases from transient phenomena, wherein few select states can mask typical behavior. Here we implement a continuous family of tunable CPHASE gates on an array of superconducting qubits to experimentally observe an eigenstate-ordered DTC. We demonstrate the characteristic spatiotemporal response of a DTC for generic initial states. Our work employs a time-reversal protocol that discriminates external decoherence from intrinsic thermalization, and leverages quantum typicality to circumvent the exponential cost of densely sampling the eigenspectrum. In addition, we locate the phase transition out of the DTC with an experimental finite-size analysis. These results establish a scalable approach to study non-equilibrium phases of matter on current quantum processors.

Genetic algorithms, which mimic evolutionary processes to solve optimization problems, can be enhanced by using powerful semi-local search algorithms as mutation operators. Here, we introduce reverse quantum annealing, a class of quantum evolutions that can be used for performing families of quasi-local or quasi-nonlocal search starting from a classical state, as novel sources of mutations. Reverse annealing enables the development of genetic algorithms that use quantum fluctuation for mutations and classical mechanisms for the crossovers -- we refer to these as Quantum-Assisted Genetic Algorithms (QAGAs). We describe a QAGA and present experimental results using a D-Wave 2000Q quantum annealing processor. On a set of spin-glass inputs, standard (forward) quantum annealing finds good solutions very quickly but struggles to find global optima. In contrast, our QAGA proves effective at finding global optima for these inputs. This successful interplay of non-local classical and quantum fluctuations could provide a promising step toward practical applications of Noisy Intermediate-Scale Quantum (NISQ) devices for heuristic discrete optimization., Comment: 13 pages, 5 figures, presented at AQC 2019

The promise of quantum computing lies in harnessing programmable quantum devices for practical applications such as efficient simulation of quantum materials and condensed matter systems. One important task is the simulation of geometrically frustrated magnets in which topological phenomena can emerge from competition between quantum and thermal fluctuations. Here we report on experimental observations of relaxation in such simulations, measured on up to 1440 qubits with microsecond resolution. By initializing the system in a state with topological obstruction, we observe quantum annealing (QA) relaxation timescales in excess of one microsecond. Measurements indicate a dynamical advantage in the quantum simulation over the classical approach of path-integral Monte Carlo (PIMC) fixed-Hamiltonian relaxation with multiqubit cluster updates. The advantage increases with both system size and inverse temperature, exceeding a million-fold speedup over a CPU. This is an important piece of experimental evidence that in general, PIMC does not mimic QA dynamics for stoquastic Hamiltonians. The observed scaling advantage, for simulation of frustrated magnetism in quantum condensed matter, demonstrates that near-term quantum devices can be used to accelerate computational tasks of practical relevance., Comment: 7 pages, 4 figures, 22 pages of supplemental material with 18 figures

Near term quantum computers with a high quantity (around 50) and quality (around 0.995 fidelity for two-qubit gates) of qubits will approximately sample from certain probability distributions beyond the capabilities of known classical algorithms on state-of-the-art computers, achieving the first milestone of so-called quantum supremacy. This has stimulated recent progress in classical algorithms to simulate quantum circuits. Classical simulations are also necessary to approximate the fidelity of multiqubit quantum computers using cross entropy benchmarking. Here we present numerical results of a classical simulation algorithm to sample universal random circuits, on a single workstation, with more qubits and depth than previously reported. For example, circuits with $5 \times 9$ qubits of depth 37, $7 \times 8$ qubits of depth 27, and $10 \times (\kappa > 10)$) qubits of depth 19 are all easy to sample. We also show up to what depth the sampling, or estimation of observables, is trivially parallelizable. The algorithm is related to the "Feynmann path" method to simulate quantum circuits. For low-depth circuits, the algorithm scales exponentially in the depth times the smaller lateral dimension, or the treewidth, as explained in Boixo et. al., and therefore confirms the bounds in that paper. In particular, circuits with $7 \times 7$ qubits and depth 40 remain currently out of reach. Follow up work on a supercomputer environment will tighten this bound., Comment: 12 pages, 6 figures. Added plot with simulations of a circuit of 7x8 qubits and depth 30, and appendices with pseudo-code and review of cross entropy benchmarking

Quantum tunneling, a phenomenon in which a quantum state traverses energy barriers above the energy of the state itself, has been hypothesized as an advantageous physical resource for optimization. Here we show that multiqubit tunneling plays a computational role in a currently available, albeit noisy, programmable quantum annealer. We develop a non-perturbative theory of open quantum dynamics under realistic noise characteristics predicting the rate of many-body dissipative quantum tunneling. We devise a computational primitive with 16 qubits where quantum evolutions enable tunneling to the global minimum while the corresponding classical paths are trapped in a false minimum. Furthermore, we experimentally demonstrate that quantum tunneling can outperform thermal hopping along classical paths for problems with up to 200 qubits containing the computational primitive. Our results indicate that many-body quantum phenomena could be used for finding better solutions to hard optimization problems., Comment: Complete rewrite, much shorter version of arXiv:1411.4036. 7 pages, 7 figures

Quantum tunneling is a phenomenon in which a quantum state traverses energy barriers above the energy of the state itself. Tunneling has been hypothesized as an advantageous physical resource for optimization. Here we present the first experimental evidence of a computational role of multiqubit quantum tunneling in the evolution of a programmable quantum annealer. We develop a theoretical model based on a NIBA Quantum Master Equation to describe the multiqubit dissipative tunneling effects under the complex noise characteristics of such quantum devices. We start by considering a computational primitive, an optimization problem consisting of just one global and one false minimum. The quantum evolutions enable tunneling to the global minimum while the corresponding classical paths are trapped in a false minimum. In our study the non-convex potentials are realized by frustrated networks of qubit clusters with strong intra-cluster coupling. We show that the collective effect of the quantum environment is suppressed in the "critical" phase during the evolution where quantum tunneling "decides" the right path to solution. In a later stage dissipation facilitates the multiqubit tunneling leading to the solution state. The predictions of the model accurately describe the experimental data from the D-Wave Two quantum annealer at NASA Ames. In our computational primitive the temperature dependence of the probability of success in the quantum model is opposite to that of the classical paths with thermal hopping. Specifically, we provide an analysis of an optimization problem with sixteen qubits, demonstrating eight qubit tunneling that increases success probabilities. Furthermore, we report results for larger problems with up to 200 qubits that contain the primitive as subproblems., Comment: Many minor updates, results unchanged. 33 pages, 35 figures

Quantum technology is maturing to the point where quantum devices, such as quantum communication systems, quantum random number generators and quantum simulators, may be built with capabilities exceeding classical computers. A quantum annealer, in particular, solves hard optimisation problems by evolving a known initial configuration at non-zero temperature towards the ground state of a Hamiltonian encoding a given problem. Here, we present results from experiments on a 108 qubit D-Wave One device based on superconducting flux qubits. The strong correlations between the device and a simulated quantum annealer, in contrast with weak correlations between the device and classical annealing or classical spin dynamics, demonstrate that the device performs quantum annealing. We find additional evidence for quantum annealing in the form of small-gap avoided level crossings characterizing the hard problems. To assess the computational power of the device we compare it to optimised classical algorithms., Comment: 23 pages, 38 figures. Revised version. Text rewritten for clarity, added comparison with spin dynamics model

We study the N��el to dimer transition driven by interlayer exchange coupling in spin-S Heisenberg antiferromagnets on bilayer square and honeycomb lattices for S=1/2, 1, 3/2. Using exact stochastic series expansion quantum Monte Carlo (QMC) calculations, we find that the critical value of the interlayer coupling, J_{\perp c}[S], increases with increasing S, with clear evidence that the transition is in the O(3) universality class for all S. Using bond operator mean field theory restricted to singlet and triplet states, we find J_{\perp c}[S] ~ S(S+1), in qualitative accord with QMC, but the resulting J_{\perp c} [S] is significantly smaller than the QMC value. For S=1/2, incorporating triplet-triplet interactions within a variational approach yields a critical interlayer coupling which agrees well with QMC. For higher spin, we argue that it is crucial to account for the high energy quintet modes, and show that including these within a perturbative scheme leads to reasonable agreement with QMC results for S=1,3/2. We discuss the broad implications of our results for systems such as the triangular lattice S=1 dimer compound Ba_3Mn_2O_8 and the S=3/2 bilayer honeycomb material Bi_3Mn_4O_{12}(NO_{3})., 14 pages, 7 figures, 2 tables. Updated data, corrected typos, added two paragraphs