Quantum Supremacy and the Complexity of Random Circuit Sampling

2018/03/12 by Adam Bouland, Bill Fefferman, Chinmay Nirkhe +1 · 2 voices · 11 citations
Computer Science · Engineering · Physics and Astronomy · #Computability, Logic, AI Algorithms #Low-power high-performance VLSI design #Quantum Computing Algorithms and Architecture #cs.CC #quant-ph

paper · pdf · doi:10.1038/s41567-018-0318-2

arxiv created 2018/03/12 · arxiv published 2018/03/12 · openalex publication_date 2018/10/16 · openalex created_date 2018/10/26 · arxiv updated 2020/11/13 · openalex updated_date 2026/08/04

Abstract

A critical milestone on the path to useful quantum computers is quantum supremacy - a demonstration of a quantum computation that is prohibitively hard for classical computers. A leading near-term candidate, put forth by the Google/UCSB team, is sampling from the probability distributions of randomly chosen quantum circuits, which we call Random Circuit Sampling (RCS). In this paper we study both the hardness and verification of RCS. While RCS was defined with experimental realization in mind, we show complexity theoretic evidence of hardness that is on par with the strongest theoretical proposals for supremacy. Specifically, we show that RCS satisfies an average-case hardness condition - computing output probabilities of typical quantum circuits is as hard as computing them in the worst-case, and therefore #P-hard. Our reduction exploits the polynomial structure in the output amplitudes of random quantum circuits, enabled by the Feynman path integral. In addition, it follows from known results that RCS satisfies an anti-concentration property, making it the first supremacy proposal with both average-case hardness and anti-concentration.

Citations

• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• A blueprint for demonstrating quantum supremacy with superconducting qubits
• On the Complexity of Random Quantum Computations and the Jones Polynomial
• Quantum Computing in the NISQ era and beyond

Cited by

• Theory of the Matchgate Commutant
• Quantum coherence and counterdiabatic quantum computing
• Principle of majorization: Application to random quantum circuits
• Growth of genuine multipartite entanglement in random unitary circuits
• Low-overhead error detection with spacetime codes
• The Hardness of Learning Quantum Circuits and its Cryptographic Applications
• Expressibility and trainability of parametrized analog quantum systems for machine learning applications
• Theory of quantum path computing with Fourier optics and future applications for quantum supremacy, neural networks and nonlinear Schrödinger equations
• Quantum solvability of noisy linear problems by divide-and-conquer strategy
• Quantum supremacy using a programmable superconducting processor
• Locality-aware Pauli-based computation for local magic state preparation

Discussions

• danke herzlichst für den brainburn… arxiv.org/pdf/1803.04402 [bsky, 2 points, 1 comments]
• So, specifically they're doing random circuit sampling, where you apply a pseudorandom sequence of gates to a quantum circuit and sample the output. arxiv.org/pdf/1803.04402 is pretty readable if you [bsky, 1 points, 2 comments]

Related

• Quantum supremacy and random circuits
• Complexity-Theoretic Foundations of Quantum Supremacy Experiments
• A Polynomial-Time Classical Algorithm for Noisy Random Circuit Sampling
• Hardness and Complexity Transition of Noisy Random Circuit Sampling
• The power of quantum circuits in sampling