Outperforming classical supercomputers in a well-defined computational task is an important milestone in the long-term quest for practical quantum computing. I will argue that this milestone has been reached for the task of random quantum circuit sampling. I will review recent advances in complexity theory and classical algorithms related to this experiment. BosonSampling is another important proposal for early beyond-classical demonstrations. I will review recent BosonSampling experiments and algorithms.
Outperforming classical supercomputers in a well-defined computational task is an important milestone in the long-term quest for practical quantum computing. I will argue that this milestone has been reached for the task of random quantum circuit sampling. I will review recent advances in complexity theory and classical algorithms related to this experiment. BosonSampling is another important proposal for early beyond-classical demonstrations. I will review recent BosonSampling experiments and algorithms.
As Moore's law reaches its limits, quantum computers are emerging with the promise of dramatically outperforming classical computers. We have witnessed the advent of quantum processors with over 50 quantum bits (qubits), which are expected to be beyond the reach of classical simulation. Quantum supremacy is the event at which the old Extended Church-Turing Thesis is overturned: A quantum computer performs a task that is practically impossible for any classical (super)computer. The demonstration requires both a solid theoretical guarantee and an experimental realization. The lead candidate is Random Circuit Sampling (RCS), which is the task of sampling from the output distribution of random quantum circuits. Google recently announced a 53−qubit experimental demonstration of RCS. Soon after, classical algorithms appeared that challenge the supremacy of random circuits by estimating their outputs. How hard is it to classically simulate the output of random quantum circuits? We prove that estimating the output probabilities of random quantum circuits is formidably hard (#P-Hard) for any classical computer. This makes RCS the strongest candidate for demonstrating quantum supremacy relative to all other proposals. The robustness to the estimation error that we prove may serve as a new hardness criterion for the performance of classical algorithms. To achieve this, we introduce the Cayley path interpolation between any two gates of a quantum computation and convolve recent advances in quantum complexity and information with probability and random matrices. Furthermore, we apply algebraic geometry to generalize the well-known Berlekamp-Welch algorithm that is widely used in coding theory and cryptography. Our results imply that there is an exponential hardness barrier for the classical simulation of most quantum circuits.
Abstract There is a large body of evidence for the potential of greater computational power using information carriers that are quantum mechanical over those governed by the laws of classical mechanics. But the question of the exact nature of the power contributed by quantum mechanics remains only partially answered. Furthermore, there exists doubt over the practicality of achieving a large enough quantum computation that definitively demonstrates quantum supremacy. Recently the study of computational problems that produce samples from probability distributions has added to both our understanding of the power of quantum algorithms and lowered the requirements for demonstration of fast quantum algorithms. The proposed quantum sampling problems do not require a quantum computer capable of universal operations and also permit physically realistic errors in their operation. This is an encouraging step towards an experimental demonstration of quantum algorithmic supremacy. In this paper, we will review sampling problems and the arguments that have been used to deduce when sampling problems are hard for classical computers to simulate. Two classes of quantum sampling problems that demonstrate the supremacy of quantum algorithms are BosonSampling and Instantaneous Quantum Polynomial-time Sampling. We will present the details of these classes and recent experimental progress towards demonstrating quantum supremacy in BosonSampling.
Abstract The achievement of quantum computational advantage, also known as quantum supremacy, is a major milestone at which a quantum computer can solve a problem significantly faster than the world's most powerful classical computers. Two tasks, boson sampling and random quantum circuit sampling, have experimentally exhibited quantum advantages on photonic and superconducting platforms respectively. Classical benchmarking is essential, yet challenging, because these tasks are intractable for classical computers. This study reviews models, algorithms and large‐scale simulations of these two sampling tasks. These approaches continue to hold substantial significance for research in both current noisy intermediate‐scale quantum (NISQ) systems and future fault‐tolerant quantum computing.
Exploiting the coherence and entanglement of quantum many-qubit states, quantum computing can significantly surpass classical algorithms, making it possible to factor large numbers, solve linear equations, simulate many-body quantum systems, etc., in a reasonable time. With the rapid development of quantum computing hardware, many attention has been drawn to explore how quantum computers could go beyond the limit of classical computation. Owing to the need of a universal fault-tolerant quantum computer for many existing quantum algorithms, such as Shor’s factoring algorithm, and considering the limit of near-term quantum devices with small qubit numbers and short coherence times, many recent works focused on the exploration of demonstrating quantum advantages using noisy intermediate-scaled quantum devices and shallow circuits, and hence some sampling problems have been proposed as the candidates for quantum advantage demonstration. This review summarizes quantum advantage problems that are realizable on current quantum hardware. We focus on two notable problems—random circuit simulation and boson sampling—and consider recent theoretical and experimental progresses. After the respective demonstrations of these two types of quantum advantages on superconducting and optical quantum platforms, we expect current and near-term quantum devices could be employed for demonstrating quantum advantages in general problems.
Recent experiments completed by collaborating research groups from Google, NASA Ames, UC Santa Barbara, and others provided compelling evidence that quantum supremacy has finally been achieved on a superconducting quantum processor. The theoretical basis for these experiments depends on sampling the output distributions of random quantum circuits; unfortunately, understanding how this theoretical basis can be used to define quantum supremacy is an extremely difficult task. Anyone attempting to understand how this sampling task relates to quantum supremacy must study concepts from random matrix theory, mathematical analysis, quantum chaos, computational complexity, and probability theory. Resources connecting these concepts in the context of quantum supremacy are scattered and often difficult to find. This article is an attempt to alleviate this difficulty in those who wish to understand the theoretical basis of Google's quantum supremacy experiments, by carefully walking through a derivation of their precise mathematical definition of quantum supremacy. It's designed for advanced undergraduate or graduate students who want more information than can be provided in popular science articles, but who might not know where to begin when tackling the many research papers related to quantum supremacy.
Depending on time, I'll discuss some subset of the following results. (1) There exists an oracle relative to which classical and quantum computers can solve the same approximate sampling problems in polynomial time, and yet the polynomial hierarchy is infinite. This means that any "BosonSampling-type theorem" will need to be non-relativizing. (2) Can P be separated from BQP by an efficiently-computable oracle (one in P/poly)? Yes if quantum-resistant one-way functions exist; no if P=PSPACE. The latter builds on recent results in quantum query complexity by myself and Shalev Ben-David. (3) How hard is it to approximately sample the output distribution of a random quantum circuit? One can do it (and even calculate the probabilities) in polynomial space and m^O(n) time, where m is the number of gates and n is the number of qubits. But if that's essentially optimal for estimating probabilities, then approximate sampling also requires exponential time. Joint work with Lijie Chen (Tsinghua University)