Quantum supremacy using a programmable superconducting processor.

The promise of quantum computers is that certain computational tasks might be executed exponentially faster on a quantum processor than on a classical processor1. A fundamental challenge is to build a high-fidelity processor capable of running quantum algorithms in an exponentially large computational space. Here we report the use of a processor with programmable superconducting qubits2-7 to create quantum states on 53 qubits, corresponding to a computational state-space of dimension 253 (about 1016). Measurements from repeated experiments sample the resulting probability distribution, which we verify using classical simulations. Our Sycamore processor takes about 200 seconds to sample one instance of a quantum circuit a million times-our benchmarks currently indicate that the equivalent task for a state-of-the-art classical supercomputer would take approximately 10,000 years. This dramatic increase in speed compared to all known classical algorithms is an experimental realization of quantum supremacy8-14 for this specific computational task, heralding a much-anticipated computing paradigm.

Quantum Annealing via Environment-Mediated Quantum Diffusion.

We show that quantum diffusion near a quantum critical point can provide an efficient mechanism of quantum annealing. It is based on the diffusion-mediated recombination of excitations in open systems far from thermal equilibrium. We find that, for an Ising spin chain coupled to a bosonic bath and driven by a monotonically decreasing transverse field, excitation diffusion sharply slows down below the quantum critical region. This leads to spatial correlations and effective freezing of the excitation density. Still, obtaining an approximate solution of an optimization problem via the diffusion-mediated quantum annealing can be faster than via closed-system quantum annealing or Glauber dynamics.

Statistical mechanics of the quantum K -satisfiability problem.

We study the quantum version of the random K -satisfiability problem in the presence of an external magnetic field Gamma applied in the transverse direction. We derive the replica-symmetric free-energy functional within the static approximation and the saddle-point equation for the order parameter: the distribution P[h(m)] of functions of magnetizations. The order parameter is interpreted as the histogram of probability distributions of individual magnetizations. In the limit of zero temperature and small transverse fields, to leading order in Gamma magnetizations m approximately 0 become relevant in addition to purely classical values of m approximately +/-1 . Self-consistency equations for the order parameter are solved numerically using a quasi-Monte Carlo method for K=3 . It is shown that for an arbitrarily small Gamma quantum fluctuations destroy the phase transition present in the classical limit Gamma=0 , replacing it with a smooth crossover transition. The implications of this result with respect to the expected performance of quantum optimization algorithms via adiabatic evolution are discussed. The replica-symmetric solution of the classical random K -satisfiability problem is briefly reexamined. It is shown that the phase transition at T=0 predicted by the replica-symmetric theory is of continuous type with atypical critical exponents.

Zero-temperature quantum annealing bottlenecks in the spin-glass phase.

A promising approach to solving hard binary optimization problems is quantum adiabatic annealing in a transverse magnetic field. An instantaneous ground state-initially a symmetric superposition of all possible assignments of N qubits-is closely tracked as it becomes more and more localized near the global minimum of the classical energy. Regions where the energy gap to excited states is small (for instance at the phase transition) are the algorithm's bottlenecks. Here I show how for large problems the complexity becomes dominated by O(log N) bottlenecks inside the spin-glass phase, where the gap scales as a stretched exponential. For smaller N, only the gap at the critical point is relevant, where it scales polynomially, as long as the phase transition is second order. This phenomenon is demonstrated rigorously for the two-pattern Gaussian Hopfield model. Qualitative comparison with the Sherrington-Kirkpatrick model leads to similar conclusions.

Comparative study of the performance of quantum annealing and simulated annealing.

Relations of simulated annealing and quantum annealing are studied by a mapping from the transition matrix of classical Markovian dynamics of the Ising model to a quantum Hamiltonian and vice versa. It is shown that these two operators, the transition matrix and the Hamiltonian, share the eigenvalue spectrum. Thus, if simulated annealing with slow temperature change does not encounter a difficulty caused by an exponentially long relaxation time at a first-order phase transition, the same is true for the corresponding process of quantum annealing in the adiabatic limit. One of the important differences between the classical-to-quantum mapping and the converse quantum-to-classical mapping is that the Markovian dynamics of a short-range Ising model is mapped to a short-range quantum system, but the converse mapping from a short-range quantum system to a classical one results in long-range interactions. This leads to a difference in efficiencies that simulated annealing can be efficiently simulated by quantum annealing but the converse is not necessarily true. We conclude that quantum annealing is easier to implement and is more flexible than simulated annealing. We also point out that the present mapping can be extended to accommodate explicit time dependence of temperature, which is used to justify the quantum-mechanical analysis of simulated annealing by Somma, Batista, and Ortiz. Additionally, an alternative method to solve the nonequilibrium dynamics of the one-dimensional Ising model is provided through the classical-to-quantum mapping.