Quantum supremacy and random circuits

Abstract

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.

27 pages. 8 Figures Former title, "Cayley path and quantum computational supremacy: A proof of average-case $\#P-$hardness of Random Circuit Sampling with quantified robustness"

References in corpus (5)

• Quantum algorithm for solving linear systems of equations
• Black holes as mirrors: quantum information in random subsystems
• Obstacles to State Preparation and Variational Optimization from Symmetry Protection
• Efficient classical simulation of random shallow 2D quantum circuits
• Classical Simulation of Quantum Supremacy Circuits

Cited by in corpus (12)

• Noisy intermediate-scale quantum (NISQ) algorithms
• Introduction to Haar Measure Tools in Quantum Information: A Beginner's Tutorial
• Prospects for Quantum Enhancement with Diabatic Quantum Annealing
• Quantum Computational Advantage via High-Dimensional Gaussian Boson Sampling
• Efficient classical simulation of noisy random quantum circuits in one dimension
• NISQ Computers: A Path to Quantum Supremacy
• Fermion Sampling: a robust quantum computational advantage scheme using fermionic linear optics and magic input states
• Noise and the frontier of quantum supremacy
• Quantum supremacy and quantum phase transitions
• On Certified Randomness from Fourier Sampling or Random Circuit Sampling
• Efficient approximation of experimental Gaussian boson sampling
• Classical simulation of bosonic linear-optical random circuits beyond linear light cone