A Polynomial-Time Classical Algorithm for Noisy Random Circuit Sampling
Authors:
Top Cited Papers
Open Access
- 2 June 2023
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 945-957
Abstract
We give a polynomial time classical algorithm for sampling from the output distribution of a noisy random quantum circuit in the regime of anti-concentration to within inverse polynomial total variation distance. The algorithm is based on a quantum analog of noise induced low degree approximations of Boolean functions, which takes the form of the truncation of a Feynman path integral in the Pauli basis.Keywords
All Related Versions
This publication has 16 references indexed in Scilit:
- Quantum computational advantage via 60-qubit 24-cycle random circuit samplingScience Bulletin, 2022
- Simulation of Quantum Circuits Using the Big-Batch Tensor Network MethodPhysical Review Letters, 2022
- Strong Quantum Computational Advantage Using a Superconducting Quantum ProcessorPhysical Review Letters, 2021
- Hyper-optimized tensor network contractionQuantum, 2021
- Quantum supremacy using a programmable superconducting processorNature, 2019
- On the complexity and verification of quantum random circuit samplingNature Physics, 2018
- Characterizing quantum supremacy in near-term devicesNature Physics, 2018
- Achieving quantum supremacy with sparse and noisy commuting quantum computationsQuantum, 2017
- Random Quantum Circuits are Approximate 2-designsCommunications in Mathematical Physics, 2009
- Quantum Complexity TheorySIAM Journal on Computing, 1997