2017/08/06 by Sergio Boixo, Vadim Smelyanskiy, Boixo, Sergio +3 · 1 citation
Computer Science · Physics and Astronomy · #FOS: Physical sciences #Neural Networks and Applications #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #Statistical Mechanics and Entropy
paper · pdf · doi:10.48550/arxiv.1708.01875
openalex publication_date 2017/08/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Sampling from the output distribution of chaotic quantum evolutions, and of pseudo-random universal quantum circuits in particular, has been proposed as a prominent milestone for near-term quantum supremacy. The same paper notes that chaotic distributions are very sensitive to noise, and under quite general noise models converge to the uniform distribution over bit-strings exponentially in the number of gates. On the one hand, for increasing number of gates, it suffices to choose bit-strings at random to approximate the noisy distribution with fixed statistical distance. On the other hand, cross-entropy benchmarking can be used to gauge the fidelity of an experiment, and the distance to the uniform distribution. We estimate that state-of-the-art classical supercomputers would fail to simulate high-fidelity chaotic quantum circuits with approximately fifty qubits and depth forty. A recent interesting paper proposed a different approximation algorithm to a noisy distribution, extending previous results on the Fourier analysis of commuting quantum circuits. Using the statistical properties of the Porter-Thomas distribution, we show that this new approximation algorithm does not improve random guessing, in polynomial time. Therefore, it confirms previous results and does not represent an additional challenge to the suggested failure stated above.