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.
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.
Random quantum circuit sampling, a task to sample bit strings from a random quantum circuit, is considered a suitable benchmark task to demonstrate the outperformance of quantum computers even with noisy qubits. Recently, random quantum circuit sampling was performed on the Sycamore quantum processor with 53 qubits [Nature (London) 574, 505 (2019)] and on the Zuchongzhi quantum processor with 56 qubits [Phys. Rev. Lett. 127, 180501 (2021)]. Here, we analyze and compare the statistical properties of the outputs of the random quantum circuit sampling by the Sycamore and Zuchongzhi processors. Using the Marchenko-Pastur law of random matrices of bit strings and the Wasssertein distances between bit strings, we find that the statistical properties of Sycamore bit strings are quite different from those of Zuchongzhi bit strings, while both processors score similar values of linear cross-entropy fidelity for random circuit sampling. Some bit strings sampled by the Zuchongzhi processor pass the NIST random number tests while both Sycamore and Zuchongzhi processors show similar patterns in the heat maps of bit strings. Zuchongzhi bit strings are much closer to classical uniform random bits than those of Sycamore. It is shown that the statistical properties of bit strings of both random quantum circuits change little as the depth of the random quantum circuits increases. Our findings raise a question about the computational reliability of noisy quantum processors because two quantum processors with similar noise levels and similar qubit structures produced statistically different outputs for the same random quantum circuit sampling.
Porter-Thomas statistics are a characteristic feature of the output distribution of random quantum states and, more broadly, chaotic quantum many-body systems. Convergence to Porter-Thomas plays a central role in random circuit sampling and experimental demonstrations of quantum advantage, where the output statistics of low-depth random quantum circuits are expected to be approximately Porter-Thomas, despite the absence of a rigorous proof of convergence. We show that the output distribution of polynomial-depth brickwork random circuits converges inverse-polynomially in total variation distance to the Porter-Thomas distribution. Specifically, consider the output probability distribution over a fixed bitstring of a local random quantum circuit, constructed from nearest-neighbor Haar random gates. Then, for any m≥0, the distribution corresponding to circuits of depth O(n2m+1log(n)) is at most O(1/nm) far in total variation distance from the Porter-Thomas distribution. Our proof uses moment bounds from approximate designs, analytic estimates for characteristic functions, and a local anticoncentration property for inverse moments.
Although the emergence of a fully-functional quantum computer may still be far away from today, in the near future, it is possible to have medium-size, special-purpose, quantum devices that can perform computational tasks not efficiently simulable with any classical computer. This status is known as quantum supremacy (or quantum advantage), where one of the promising approaches is through the sampling of chaotic quantum circuits. Sampling of ideal chaotic quantum circuits has been argued to require an exponential time for classical devices. A major question is whether quantum supremacy can be maintained under noise without error correction, as the implementation of fault-tolerance would cost lots of extra qubits and quantum gates. Here we show that, for a family of chaotic quantum circuits subject to Pauli errors, there exists an non-exponential classical algorithm capable of simulating the noisy chaotic quantum circuits with bounded errors. This result represents a serious challenge to a previous result in the literature suggesting the failure of classical devices in simulating noisy chaotic circuits with about 48 qubits and depth 25. Moreover, even though our model does not cover all types of experimental errors, from a practical point view, our result describes a well-defined setting where quantum supremacy can be tested against the challenges of classical rivals, in the context of chaotic quantum circuits.
Random circuit sampling, the task to sample bit strings from a random unitary operator, has been performed to demonstrate quantum advantage on the Sycamore quantum processor with 53 qubits and on the Zuchongzhi quantum processor with 56 and 61 qubits. Recently, it has been claimed that classical computers using tensor network simulation could catch on current noisy quantum processors for random circuit sampling. While the linear cross entropy benchmark fidelity is used to certify all these claims, it may not capture in detail statistical properties of outputs. Here, we compare the bit strings sampled from classical computers using tensor network simulation by Pan et al. [Phys. Rev. Lett. 129, 090502 (2022)] and by Kalachev et al. [arXiv:2112.15083 (2021)] and from the Sycamore and Zuchongzhi quantum processors. It is shown that all Kalachev et al.'s samples pass the NIST random number tests. The heat maps of bit strings show that Pan et al.'s and Kalachev et al.'s samples are quite different from the Sycamore or Zuzhongzhi samples. The analysis with the Marchenko-Pastur distribution and the Wasssertein distances demonstrates that Kalachev et al.'s samples are statistically close to the Sycamore samples than Pan et al.'s while the three datasets have similar values of the linear cross entropy fidelity. Our finding implies that further study is needed to certify or beat the claims of quantum advantage for random circuit sampling.
The recent paper [F. Arute et al. Nature {\bf 574}, 505 (2019)] considered exact classical sampling of the output probability distribution of the globally depolarized random quantum circuit. In this paper, we show three results. First, we consider the case when the fidelity F is constant. We show that if the distribution is classically sampled in polynomial time within a constant multiplicative error, then BQP⊆SBP, which means that BQP is in the second level of the polynomial-time hierarchy. We next show that for any F≤1/2, the distribution is classically trivially sampled by the uniform distribution within the multiplicative error F2n+2, where n is the number of qubits. We finally show that for any F, the distribution is classically trivially sampled by the uniform distribution within the additive error 2F. These last two results show that if we consider realistic cases, both F∼2−m and m≫n, or at least F∼2−m, where m is the number of gates, quantum supremacy does not exist for approximate sampling even with the exponentially-small errors. We also argue that if F∼2−m and m≫n, the standard approach will not work to show quantum supremacy even for exact sampling.
Random circuit sampling, the task of sampling bit strings from a random unitary operator, has been implemented to demonstrate quantum advantage on the Sycamore quantum processor with 53 qubits and on the Zuchongzhi quantum processor with 56 and 61 qubits. Recently, it was claimed that classical computers using tensor network simulation could catch on to current noisy quantum processors for random circuit sampling. While the linear cross-entropy benchmark fidelity was used to certify all these claims, it may not capture statistical properties of outputs in detail. Here, we compare the bit strings sampled from classical computers using tensor network simulation by Pan et al. [F. Pan, K. Chen, and P. Zhang, Phys. Rev. Lett. 129, 090502 (2022)] and by Kalachev et al. [G. Kalachev, P. Panteleev, P. Zhou, and M.-H. Yung, arXiv:2112.15083] with the bit strings from the Sycamore quantum processor. It is shown that all of Kalachev et al.'s samples passed the NIST random number tests. The heat maps of bit strings show that Pan et al.'s and Kalachev et al.'s samples are quite different from the Sycamore or Zuchongzhi samples. The analysis with the Marchenko-Pastur distribution and the Wasssertein distances demonstrates that Kalachev et al.'s samples are statistically closer to the Sycamore samples than Pan et al.'s while the three datasets have similar values for the linear cross-entropy fidelity. Our finding implies that further study is needed to certify or beat the claims of quantum advantage using random circuit sampling.