A critical question for the field of quantum computing in the near future is whether quantum devices without error correction can perform a well-defined computational task beyond thecapabilities of state-of-the-art classical computers, achieving so-called quantum supremacy. We study the task of sampling from the output distributions of (pseudo-)random quantum circuits, a natural task for benchmarking quantum computers. Crucially, sampling this distribution classically requires a direct numerical simulation of the circuit, with computational cost exponential in the number of qubits. This requirement is typical of chaotic systems. We extend previous results in computational complexity to argue more formally that this sampling task must take exponential time in a classical computer. We study the convergence to the chaotic regime using extensive supercomputer simulations, modeling circuits with up to 42 qubits – the largest quantum circuits simulated to date for a computational task that approaches quantum supremacy. We argue that while chaotic states are extremely sensitive to errors, quantum supremacy can be achieved in the near-term with approximately fifty superconducting qubits. We introduce cross entropy as a useful benchmark of quantum circuits which approximates the circuit fidelity. We show that the cross entropy can be efficiently measured when circuit simulations are available. Beyond the classically tractable regime, the cross entropy can be extrapolated and compared with theoretical estimates of circuit fidelity to define a practical quantum supremacy test.
Calibration of quantum computing technologies is essential to the effective utilization of their quantum resources. Specifically, the performance of quantum annealers is likely to besignificantly impaired by noise in their programmable parameters, effectively misspecification of the computational problem to be solved, often resulting in spurious suboptimal solutions. We developed a strategy to determine and correct persistent, systematic biases between the actual values of the programmable parameters and their user-specified values. We applied the recalibration strategy to two D-Wave Two quantum annealers, one at NASA Ames Research Center in Moffett Field, California, and another at D-Wave Systems in Burnaby, Canada. We show that the recalibration procedure not only reduces the magnitudes of the biases in the programmable parameters but also enhances the performance of the device on a set of random benchmark instances.
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 foroptimization. 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.
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 physicalresource 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, the simplest non-convex optimization problem consisting of just one global and one local 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.
We report on a case study in programming an early quantum annealer to attack optimization problems related to operational planning. While a number of studies have looked at the performanceof quantum annealers on problems native to their architecture, and others have examined performance of select problems stemming from an application area, ours is one of the first studies of a quantum annealer’s performance on parametrized families of hard problems from a practical domain. We explore two different general mappings of planning problems to quadratic unconstrained binary optimization (QUBO) problems, and apply them to two parametrized families of planning problems, navigation-type and scheduling-type. We also examine two more compact, but problem-type specific, mappings to QUBO, one for the navigation-type planning problems and one for the scheduling-type planning problems. We study embedding properties and parameter setting, and examine their effect on the efficiency with which the quantum annealer solves these problems. From these results we derive insights useful for the programming and design of future quantum annealers: problem choice, the mapping used, the properties of the embedding, and the annealing profile all matter, each significantly affecting the performance.
In this article, we show how to map a sampling of the hardest artificial
intelligence problems in space exploration onto equivalent Ising models that
then can be attacked using quantumannealing implemented in D-Wave machine. We
overview the existing results as well as propose new Ising model
implementations for quantum annealing. We review supervised and unsupervised
learning algorithms for classification and clustering with applications to
feature identification and anomaly detection. We introduce algorithms for data
fusion and image matching for remote sensing applications. We overview planning
problems for space exploration mission applications and algorithms for
diagnostics and recovery with applications to deep space missions. We describe
combinatorial optimization algorithms for task assignment in the context of
autonomous unmanned exploration. Finally, we discuss the ways to circumvent the
limitation of the Ising mapping using a „blackbox“ approach based on ideas from
probabilistic computing. In this article we describe the architecture of the
D-Wave One machine and report its benchmarks. Results on random ensemble of
problems in the range of up to 96 qubits show improved scaling for median core
quantum annealing time compared with classical algorithms; whether this scaling
persists for larger problem sizes is an open question. We also review previous
results of D-Wave One benchmarking studies for solving binary classification
problems with a quantum boosting algorithm which is shown to outperform
AdaBoost. We review quantum algorithms for structured learning for multi-label
classification and introduce a hybrid classical/quantum approach for learning
the weights. Results of D-Wave One benchmarking studies for learning structured
labels on four different data sets show a better performance compared with an
independent Support Vector Machine approach with linear kernel.