Fourier analysis of sampling from noisy chaotic quantum circuits

Abstract

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.

arXiv comment4+1 pages, 3 figures

Cited by in corpus (9)

• Rényi Entropies from Random Quenches in Atomic Hubbard and Spin Models
• A flexible high-performance simulator for verifying and benchmarking quantum circuits implemented on real hardware
• Approximate unitary $t$-designs by short random quantum circuits using nearest-neighbor and long-range gates
• Efficient classical simulation of noisy random quantum circuits in one dimension
• On the representation of Boolean and real functions as Hamiltonians for quantum computing
• Efficient classical simulation of noisy quantum computation
• Marginal probabilities in boson samplers with arbitrary input states
• Efficient approximation of experimental Gaussian boson sampling
• Sampling and the complexity of nature