Fetching the paper…
Reading the bibliography…
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.
“Quantum supremacy and random circuits”, 2019
Ramis Movassagh · 1909
Earlier work this paper cites.
“Limitations of Noisy Reversible Computation”, 1996
D. Aharonov, M. Ben-Or, R. Impagliazzo and N. Nisan · 1996
Earlier work this paper cites.
“Quantum Complexity Theory”
Ethan Bernstein and Umesh Vazirani · 1997
Earlier work this paper cites.
“Classical Simulation of Quantum Supremacy Circuits”, 2020
Cupjin Huang et al · 2005
Earlier work this paper cites.
“Random Quantum Circuits are Approximate 2-designs”
Aram. Harrow and Richard. Low · 2009
Earlier work this paper cites.
“Upper Bounds on the Noise Threshold for Fault-Tolerant Quantum Computing”
Julia Kempe, Oded Regev, Falk Uunger and Ronald de Wolf · 2010
Earlier work this paper cites.
“The Computational Complexity of Linear Optics”
Scott Aaronson and Alex Arkhipov · 2013
Earlier work this paper cites.
“Complexity-Theoretic Foundations of Quantum Supremacy Experiments”
Scott Aaronson and Lijie Chen · 2017
Earlier work this paper cites.
“Achieving quantum supremacy with sparse and noisy commuting quantum computations”
Michael. Bremner, Ashley Montanaro and Dan. Shepherd · 2017
Earlier work this paper cites.
“Characterizing quantum supremacy in near-term devices”
Sergio Boixo et al · 2018
Earlier work this paper cites.
“Efficient classical simulation of noisy quantum computation”, 2018
Xun Gao and Luming Duan · 2018
Earlier work this paper cites.
“Quantum supremacy using a programmable superconducting processor”
Frank Arute et al · 2019
Cited alongside, same era.
“On the complexity and verification of quantum random circuit sampling”
Adam Bouland, Bill Fefferman, Chinmay Nirkhe and Umesh Vazirani · 2019
Cited alongside, same era.
“On the Classical Hardness of Spoofing Linear Cross-Entropy Benchmarking”
Scott Aaronson and Sam Gunn · 2020
Cited alongside, same era.
“Spoofing Linear Cross-Entropy Benchmarking in Shallow Quantum Circuits”
Boaz Barak, Chi-Ning Chou and Xun Gao · 2021
Cited alongside, same era.
“Noise and the Frontier of Quantum Supremacy”
Adam Bouland, Bill Fefferman, Zeph Landau and Yunchao Liu · 2021
Cited alongside, same era.
“Random quantum circuits transform local noise into global white noise”, 2021
“Multi-Tensor Contraction for XEB Verification of Quantum Circuits”, 2021
Gleb Kalachev, Pavel Panteleev and Man-Hong Yung · 2021
Later among the works it cites.
“Classical Sampling of Random Quantum Circuits with Bounded Fidelity”, 2021
Gleb Kalachev, Pavel Panteleev, PengFei Zhou and Man-Hong Yung · 2021
Later among the works it cites.
“Strong Quantum Computational Advantage Using a Superconducting Quantum Processor”
Yulin Wu et al · 2021
Later among the works it cites.
“Quantum computational advantage via 60-qubit 24-cycle random circuit sampling”
Qingling Zhu et al · 2021
Later among the works it cites.
“Random Quantum Circuits Anticoncentrate in Log Depth”
Alexander. Dalzell, Nicholas Hunter-Jones and Fernando… Brandão · 2022
Closest in time.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Alexander. Dalzell, Nicholas Hunter-Jones and Fernando… Brandão · 2021
Cited alongside, same era.
“Tight bounds on the convergence of noisy random circuits to the uniform distribution”, 2021
Abhinav Deshpande et al · 2021
Cited alongside, same era.
“Hyper-optimized tensor network contraction”
Johnnie Gray and Stefanos Kourtis · 2021
Cited alongside, same era.
“Limitations of Linear Cross-Entropy as a Measure for Quantum Advantage”, 2021
Xun Gao et al · 2021
Cited alongside, same era.
“Quantum supremacy and hardness of estimating output probabilities of quantum circuits”
Yasuhiro Kondo, Ryuhei Mori and Ramis Movassagh · 2021
Cited alongside, same era.
Dominik Hangleiter and Jens Eisert · 2022
Closest in time.
Hari Krovi · 2022
Closest in time.
“Efficient Classical Simulation of Random Shallow 2D Quantum Circuits”
John. Napp et al · 2022
Closest in time.
“Solving the Sampling Problem of the Sycamore Quantum Circuits”
Feng Pan, Keyang Chen and Pan Zhang · 2022
Closest in time.
“Simulation of Quantum Circuits Using the Big-Batch Tensor Network Method”
Feng Pan and Pan Zhang · 2022
Closest in time.