Explore the vast range of titles available.

The use of quantum computing for machine learning is among the most exciting prospective applications of quantum technologies. However, machine learning tasks where data is provided can be considerably different than commonly studied computational tasks. In this work, we show that some problems that are classically hard to compute can be easily predicted by classical machines learning from data. Using rigorous prediction error bounds as a foundation, we develop a methodology for assessing potential quantum advantage in learning tasks. The bounds are tight asymptotically and empirically predictive for a wide range of learning models. These constructions explain numerical results showing that with the help of data, classical machine learning models can be competitive with quantum models even if they are tailored to quantum problems. We then propose a projected quantum model that provides a simple and rigorous quantum speed-up for a learning problem in the fault-tolerant regime. For near-term implementations, we demonstrate a significant prediction advantage over some classical models on engineered data sets designed to demonstrate a maximal quantum advantage in one of the largest numerical tests for gate-based quantum machine learning to date, up to 30 qubits. Expectations for quantum machine learning are high, but there is currently a lack of rigorous results on which scenarios would actually exhibit a quantum advantage. Here, the authors show how to tell, for a given dataset, whether a quantum model would give any prediction advantage over a classical one.

Many experimental proposals for noisy intermediate scale quantum devices involve training a parameterized quantum circuit with a classical optimization loop. Such hybrid quantum-classical algorithms are popular for applications in quantum simulation, optimization, and machine learning. Due to its simplicity and hardware efficiency, random circuits are often proposed as initial guesses for exploring the space of quantum states. We show that the exponential dimension of Hilbert space and the gradient estimation complexity make this choice unsuitable for hybrid quantum-classical algorithms run on more than a few qubits. Specifically, we show that for a wide class of reasonable parameterized quantum circuits, the probability that the gradient along any reasonable direction is non-zero to some fixed precision is exponentially small as a function of the number of qubits. We argue that this is related to the 2-design characteristic of random circuits, and that solutions to this problem must be studied. Gradient-based hybrid quantum-classical algorithms are often initialised with random, unstructured guesses. Here, the authors show that this approach will fail in the long run, due to the exponentially-small probability of finding a large enough gradient along any direction.

Emerging reinforcement learning techniques using deep neural networks have shown great promise in control optimization. They harness non-local regularities of noisy control trajectories and facilitate transfer learning between tasks. To leverage these powerful capabilities for quantum control optimization, we propose a new control framework to simultaneously optimize the speed and fidelity of quantum computation against both leakage and stochastic control errors. For a broad family of two-qubit unitary gates that are important for quantum simulation of many-electron systems, we improve the control robustness by adding control noise into training environments for reinforcement learning agents trained with trusted-region-policy-optimization. The agent control solutions demonstrate a two-order-of-magnitude reduction in average-gate-error over baseline stochastic-gradient-descent solutions and up to a one-order-of-magnitude reduction in gate time from optimal gate synthesis counterparts. These significant improvements in both fidelity and runtime are achieved by combining new physical understandings and state-of-the-art machine learning techniques. Our results open a venue for wider applications in quantum simulation, quantum chemistry and quantum supremacy tests using near-term quantum devices.

Contemporary quantum computers have relatively high levels of noise, making it difficult to use them to perform useful calculations, even with a large number of qubits. Quantum error correction is expected to eventually enable fault-tolerant quantum computation at large scales, but until then, it will be necessary to use alternative strategies to mitigate the impact of errors. We propose a near-term friendly strategy to mitigate errors by entangling and measuringMcopies of a noisy stateρ. This enables us to estimate expectation values with respect to a state with dramatically reduced errorρM/Tr(ρM)without explicitly preparing it, hence the name “virtual distillation.” AsMincreases, this state approaches the closest pure state toρexponentially quickly. We analyze the effectiveness of virtual distillation and find that it is governed in many regimes by the behavior of this pure state (corresponding to the dominant eigenvector of ρ). We numerically demonstrate that virtual distillation is capable of suppressing errors by multiple orders of magnitude and explain how this effect is enhanced as the system size grows. Finally, we show that this technique can improve the convergence of randomized quantum algorithms, even in the absence of device noise.

The development of small-scale quantum devices raises the question of how to fairly assess and detect quantum speedup. Here, we show how to define and measure quantum speedup and how to avoid pitfalls that might mask or fake such a speedup. We illustrate our discussion with data from tests run on a D-Wave Two device with up to 503 qubits. By using random spin glass instances as a benchmark, we found no evidence of quantum speedup when the entire data set is considered and obtained inconclusive results when comparing subsets of instances on an instance-by-instance basis. Our results do not rule out the possibility of speedup for other classes of problems and illustrate the subtle nature of the quantum speedup question.

Quantum annealing (QA) has been proposed as a quantum enhanced optimization heuristic exploiting tunneling. Here, we demonstrate how finite-range tunneling can provide considerable computational advantage. For a crafted problem designed to have tall and narrow energy barriers separating local minima, the D-Wave 2X quantum annealer achieves significant runtime advantages relative to simulated annealing (SA). For instances with 945 variables, this results in a time-to-99%-success-probability that is ∼108 times faster than SA running on a single processor core. We also compare physical QA with the quantum Monte Carlo algorithm, an algorithm that emulates quantum tunneling on classical processors. We observe a substantial constant overhead against physical QA: D-Wave 2X again runs up to ∼108 times faster than an optimized implementation of the quantum Monte Carlo algorithm on a single core. We note that there exist heuristic classical algorithms that can solve most instances of Chimera structured problems in a time scale comparable to the D-Wave 2X. However, it is well known that such solvers will become ineffective for sufficiently dense connectivity graphs. To investigate whether finite-range tunneling will also confer an advantage for problems of practical interest, we conduct numerical studies on binary optimization problems that cannot yet be represented on quantum hardware. For random instances of the number partitioning problem, we find numerically that algorithms designed to simulate QA scale better than SA. We discuss the implications of these findings for the design of next-generation quantum annealers.

Quantum tunnelling is a phenomenon in which a quantum state traverses energy barriers higher than the energy of the state itself. Quantum tunnelling has been hypothesized as an advantageous physical resource for optimization in quantum annealing. However, computational multiqubit tunnelling has not yet been observed, and a theory of co-tunnelling under high- and low-frequency noises is lacking. Here we show that 8-qubit tunnelling plays a computational role in a currently available programmable quantum annealer. We devise a probe for tunnelling, a computational primitive where classical paths are trapped in a false minimum. In support of the design of quantum annealers we develop a nonperturbative theory of open quantum dynamics under realistic noise characteristics. This theory accurately predicts the rate of many-body dissipative quantum tunnelling subject to the polaron effect. Furthermore, we experimentally demonstrate that quantum tunnelling outperforms thermal hopping along classical paths for problems with up to 200 qubits containing the computational primitive. Quantum tunnelling may be advantageous for quantum annealing, but multiqubit tunnelling has not yet been observed or characterized theoretically. Here, the authors demonstrate that 8-qubit tunnelling plays a role in a D-Wave Two device through a nonperturbative theory and experimental data.

Here we present qFlex, a flexible tensor network-based quantum circuit simulator. qFlex can compute both the exact amplitudes, essential for the verification of the quantum hardware, as well as low-fidelity amplitudes, to mimic sampling from Noisy Intermediate-Scale Quantum (NISQ) devices. In this work, we focus on random quantum circuits (RQCs) in the range of sizes expected for supremacy experiments. Fidelity f simulations are performed at a cost that is 1/f lower than perfect fidelity ones. We also present a technique to eliminate the overhead introduced by rejection sampling in most tensor network approaches. We benchmark the simulation of square lattices and Google’s Bristlecone QPU. Our analysis is supported by extensive simulations on NASA HPC clusters Pleiades and Electra. For our most computationally demanding simulation, the two clusters combined reached a peak of 20 Peta Floating Point Operations per Second (PFLOPS) (single precision), i.e., 64% of their maximum achievable performance, which represents the largest numerical computation in terms of sustained FLOPs and the number of nodes utilized ever run on NASA HPC clusters. Finally, we introduce a novel multithreaded, cache-efficient tensor index permutation algorithm of general application.

We address the long-standing problem of the structure of the low-energy eigenstates and long-time coherent dynamics in quantum spin-glass models. Below the spin-glass freezing transition, the energy landscape of the spin system is characterized by a proliferation of local minima where classical dynamics gets trapped. A theoretical description of quantum dynamics in this regime is challenging due to the complex nature of the distribution of the tunneling matrix elements between the local minima of the energy landscape. We study the transverse-field-induced quantum dynamics of the following “impurity band” (IB) spin model: zero energy of all spin configurations except for a small fraction of spin configurations (“marked states”) that form a narrow band at a large negative energy. At a zero transverse field, the IB model demonstrates the freezing transition at inverse temperatureβf∼1characterized by a nonzero value of the Edwards-Anderson order parameter. At a finite transverse field, the low-energy dynamics can be described by the effective down-folded Hamiltonian that acts in the Hilbert subspace involving only the marked states. We obtain in an explicit form the heavy-tailed probability distribution of the off-diagonal matrix elements of the down-folded Hamiltonian. This Hamiltonian is dense and belongs to the class of preferred basis Levy matrices. Analytically solving nonlinear cavity equations for the ensemble of down-folded Hamiltonians allows us to describe the statistical properties of the eigenstates. In a broad interval of transverse fields, they are nonergodic, albeit extended. It means that the band of marked states splits into a set of narrow minibands. Accordingly, the quantum evolution that starts from a particular marked state leads to a linear combination of the states belonging to a particular miniband. An analytical description of this qualitatively new type of quantum dynamics is a key result of our paper. Based on our analysis, we propose the population transfer (PT) algorithm: The quantum evolution under constant transverse fieldB⊥starts at a low-energy spin configuration and ends up in a superposition ofΩspin configurations inside a narrow energy window. This algorithm crucially relies on the nonergodic nature of delocalized low-energy eigenstates. In the considered model, the run-time of the best classical algorithm (exhaustive search) istcl=2n/Ω. Forn≫B⊥≫1, the typical run-time of the quantum PT algorithmtclen/(2B⊥2)scales withnandΩas that of Grover’s quantum search, except for the small correction to the exponent. Unlike the Hamiltonians proposed for analog quantum unstructured search algorithms, the model we consider is nonintegrable and the transverse field delocalizes the marked states. As a result, our PT protocol does not require fine-tuning of the transverse field and may be initialized in a computational basis state. We find that the run-times of the PT algorithm are distributed according to the alpha-stable Levy law with tail index 1. We argue that our approach can be applied to study the PT protocol in other transverse-field spin-glass models, with a potential quantum advantage over classical algorithms.

Google’s quantum supremacy experiment heralded a transition point where quantum computers can evaluate a computational task, random circuit sampling, faster than classical supercomputers. We examine the constraints on the region of quantum advantage for quantum circuits with a larger number of qubits and gates than experimentally implemented. At near-term gate fidelities, we demonstrate that quantum supremacy is limited to circuits with a qubit count and circuit depth of a few hundred. Larger circuits encounter two distinct boundaries: a return of a classical advantage and practically infeasible quantum runtimes. Decreasing error rates cause the region of a quantum advantage to grow rapidly. At error rates required for early implementations of the surface code, the largest circuit size within the quantum supremacy regime coincides approximately with the smallest circuit size needed to implement error correction. Thus, the boundaries of quantum supremacy may fortuitously coincide with the advent of scalable, error-corrected quantum computing.