Characterizing quantum supremacy in near-term devices

By Sergio Boixo, Sergei V. Isakov, Vadim N. Smelyanskiy, Ryan Babbush, Nan Ding, Zhang Jiang, Michael J. Bremner, John M. Martinis, Hartmut Neven. Nature Physics, 2016

1,354 citations recorded by the source corpus.

A critical question for quantum computing in the near future is whether quantum devices without error correction can perform a well-defined computational task beyond the capabilities of supercomputers. Such a demonstration of what is referred to as quantum supremacy requires a reliable evaluation of the resources required to solve tasks with classical approaches. Here, we propose the task of sampling from the output distribution of random quantum circuits as a demonstration of quantum supremacy. We extend previous results in computational complexity to argue that this sampling task must take exponential time in a classical computer. We introduce cross-entropy benchmarking to obtain the experimental fidelity of complex multiqubit dynamics. This can be estimated and extrapolated to give a success metric for a quantum supremacy demonstration. We study the computational cost of relevant classical algorithms and conclude that quantum supremacy can be achieved with circuits in a two-dimensional lattice of 7 × 7 qubits and around 40 clock cycles. This requires an error rate of around 0.5% for two-qubit gates (0.05% for one-qubit gates), and it would demonstrate the basic building blocks for a fault-tolerant quantum computer. As a benchmark for the development of a future quantum computer, sampling from random quantum circuits is suggested as a task that will lead to quantum supremacy—a calculation that cannot be carried out classically.

Subfields: Artificial Intelligence

View Paper: https://www.semanticscholar.org/paper/a68a7a57efa3de462b6f4884573f69dd4cf0f815

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

QuEST and High Performance Simulation of Quantum Computers (2018, methodology): “An example of a depth 10 random circuit on 5 qubits, of the linear topology described in [38].”
Qulacs: a fast and versatile quantum circuit simulator for research purpose (2020, background): “For example, several verification methods for large quantum devices [1, 53] require a full simulation of large quantum systems.”
Software Mitigation of Crosstalk on Noisy Intermediate-Scale Quantum Computers (2020, background): “In Rigetti and Google Bristlecone systems, the hardware scheduler disables simultaneous nearby gates entirely to avoid crosstalk [5, 6], irrespective of other hardware or application characteristics.”
Towards quantum machine learning with tensor networks (2018, background): “It now appears that we stand on the eve of the first experimental demonstration of a quantum advantage [1].”
Quantum certification and benchmarking (2019, background): “Allowing for exponential time in classical post-processing, one can also sample-efﬁciently verify coarse-grained versions of the target distribution [16], make use of certain complexity-theoretic assumptions [3], or assumptions on the noise in the quantum device [15, 16, 32].”
Barren plateaus in quantum neural network training landscapes (2018, background): “In the quantum case, the number of paths is exponential in the number of gates, and also have random signs [31].”
Low-Depth Quantum Simulation of Materials (2017, methodology): “Variational algorithms were experimentally demonstrated in [41] and [40] using superconducting qubit platforms from industrial quantum computing groups which are expected to reach the quantum supremacy threshold in the near-future [35].”
Simulation of quantum circuits by low-rank stabilizer decompositions (2018, background): “Several tensor-based simulators have been developed [17, 39, 48] for geometrically local shallow quantum circuits that include only nearest-neighbor gates on a 2D grid of qubits [9].”
Circuit-centric quantum classifiers (2018, background): “[31] Sergio Boixo, Sergei V Isakov, Vadim N Smelyanskiy, Ryan Babbush, Nan Ding, Zhang Jiang, John M Martinis, and Hartmut Neven.”
Efficient representation of quantum many-body states with deep neural networks (2017, neutral): “It is related to classical-hardness for simulating distribution from random quantum circuit and is supported by both quantum chaos theory and extensive numerical simulations [33].”