Quantum computational advantage is a critical milestone for near-term quantum technologies and a crucial step toward building practical quantum computers. Recent successful demonstrations of quantum computational advantage owe much to specially designed random quantum circuit (RQC) protocols that enable hardware-friendly implementation and, more importantly, pose great challenges for classical simulation. Here, we report an automated protocol-design approach for determining the optimal RQC in the Zuchongzhi quantum computational advantage experiment. Without a carefully designed protocol, the classical simulation cost of the Zuchongzhi 56-qubit 20-cycle RQC experiment would not be considerably higher than Google’s 53-qubit 20-cycle experiment, even though more qubits are involved. For Google’s latest RQC experiment using 70 qubits and 24 cycles, we estimate that the classical simulation cost can be increased by at least one order of magnitude using the proposed approach. The proposed method can be applied to generic planar quantum processor architectures and addresses realistic imperfections such as processor defects, underpinning quantum computational advantage experiments in future generations of quantum processors.
Quantum computational advantage is a critical milestone for near-term quantum technologies and a crucial step toward building practical quantum computers. Recent successful demonstrations of quantum computational advantage owe much to specially designed random quantum circuit (RQC) protocols that enable hardware-friendly implementation and, more importantly, pose great challenges for classical simulation. Here, we report an automated protocol-design approach for determining the optimal RQC in the Zuchongzhi quantum computational advantage experiment. Without a carefully designed protocol, the classical simulation cost of the Zuchongzhi 56-qubit 20-cycle RQC experiment would not be considerably higher than Google’s 53-qubit 20-cycle experiment, even though more qubits are involved. For Google’s latest RQC experiment using 70 qubits and 24 cycles, we estimate that the classical simulation cost can be increased by at least one order of magnitude using the proposed approach. The proposed method can be applied to generic planar quantum processor architectures and addresses realistic imperfections such as processor defects, underpinning quantum computational advantage experiments in future generations of quantum processors.
Scaling up to a large number of qubits with high-precision control is essential in the demonstrations of quantum computational advantage to exponentially outpace the classical hardware and algorithmic improvements. Here, we develop a two-dimensional programmable superconducting quantum processor, Zuchongzhi, which is composed of 66 functional qubits in a tunable coupling architecture. To characterize the performance of the whole system, we perform random quantum circuits sampling for benchmarking, up to a system size of 56 qubits and 20 cycles. The computational cost of the classical simulation of this task is estimated to be 2-3 orders of magnitude higher than the previous work on 53-qubit Sycamore processor [Nature 574, 505 (2019)NATUAS0028-083610.1038/s41586-019-1666-5. We estimate that the sampling task finished by Zuchongzhi in about 1.2 h will take the most powerful supercomputer at least 8 yr. Our work establishes an unambiguous quantum computational advantage that is infeasible for classical computation in a reasonable amount of time. The high-precision and programmable quantum computing platform opens a new door to explore novel many-body phenomena and implement complex quantum algorithms.
We report forward random-circuit sampling (RCS) on the 120-qubit Nighthawk r2 superconducting processor (ibm_phoenix) with square-lattice connectivity, using 61 qubits, native CZ gates, and the standard cloud execution stack with no benchmark-specific calibration. Two independent fidelity estimators---mirror benchmarking and three- and four-patch cross-entropy benchmarking (XEB)---agree with each other at every measured depth, the mirror from 4 to 40 cycles and the patched estimators from 20 to 40 cycles, across more than two orders of magnitude of fidelity decay, and exceed the first-generation Nighthawk r1 device by more than an order of magnitude at fixed depth. The 36-cycle circuits sit at the depth where tensor-network contraction cost saturates at system size: a contraction-cost estimator validated against the published Sycamore and Zuchongzhi networks places the single-amplitude cost at ∼1022 complex operations. At FXEB(36)=2.3×10−3 under favorable memory assumptions this implies 1.2×1027 machine operations within the bounded-fidelity rejection-sampling model --- more than a century of runtime on the Frontier supercomputer --- to collect a 106-sample ensemble, which takes only 19\,s on Nighthawk r2. To our knowledge, this is the first demonstration of quantum advantage for a vanilla random-circuit sampling on a commercially and broadly accessible quantum processor that most non-expert quantum computer users can easily replicate.
In the relentless pursuit of quantum computational advantage, we present a significant advancement with the development of Zuchongzhi 3.0. This superconducting quantum computer prototype, comprising 105 qubits, achieves high operational fidelities, with single-qubit gates, two-qubit gates, and readout fidelity at 99.90%, 99.62%, and 99.13%, respectively. Our experiments with an 83-qubit, 32-cycle random circuit sampling on the Zuchongzhi 3.0 highlight its superior performance, achieving 1×10^{6} samples in just a few hundred seconds. This task is estimated to be infeasible on the most powerful classical supercomputers, Frontier, which would require approximately 5.9×10^{9} yr to replicate the task. This leap in processing power places the classical simulation cost 6 orders of magnitude beyond Google's SYC-67 and SYC-70 experiments [Morvan et al., Nature 634, 328 (2024)10.1038/s41586-024-07998-6], firmly establishing a new benchmark in quantum computational advantage. Our work not only advances the frontiers of quantum computing but also lays the groundwork for a new era where quantum processors play an essential role in tackling sophisticated real-world challenges.
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.
Demonstrating quantum advantage on current quantum hardware is a central goal of quantum computing, and random quantum circuits underpin many leading proposals. Yet sampling-based demonstrations are often difficult to verify, while observable-based approaches face a different challenge: concentration can suppress differences between circuit instances. Recent experiments have put forward the estimation of out-of-time-order correlators (OTOCs) in random circuits as a promising task for verifiable quantum advantage, yet whether their circuit-to-circuit fluctuations survive concentration as system size grows has remained open. Here we show that they do. For broad classes of local random circuits in any fixed spatial dimension, we prove inverse-polynomial fluctuations of fixed-order OTOCs at system-scale depths. In one-dimensional Haar-random brickwork circuits, we further show that macroscopically many gates contribute to these fluctuations, yet in each layer they remain confined to a sublinear-width region. As a byproduct, we develop a classical algorithm exhibiting the first rigorous improvement over brute-force classical simulation of OTOCs in 1D. Although classical hardness remains open, our results rule out strong concentration as an obstruction to OTOC-based proposals for verifiable quantum advantage.
As Moore's law reaches its limits, quantum computers are emerging with the promise of dramatically outperforming classical computers. We have witnessed the advent of quantum processors with over 50 quantum bits (qubits), which are expected to be beyond the reach of classical simulation. Quantum supremacy is the event at which the old Extended Church-Turing Thesis is overturned: A quantum computer performs a task that is practically impossible for any classical (super)computer. The demonstration requires both a solid theoretical guarantee and an experimental realization. The lead candidate is Random Circuit Sampling (RCS), which is the task of sampling from the output distribution of random quantum circuits. Google recently announced a 53−qubit experimental demonstration of RCS. Soon after, classical algorithms appeared that challenge the supremacy of random circuits by estimating their outputs. How hard is it to classically simulate the output of random quantum circuits? We prove that estimating the output probabilities of random quantum circuits is formidably hard (#P-Hard) for any classical computer. This makes RCS the strongest candidate for demonstrating quantum supremacy relative to all other proposals. The robustness to the estimation error that we prove may serve as a new hardness criterion for the performance of classical algorithms. To achieve this, we introduce the Cayley path interpolation between any two gates of a quantum computation and convolve recent advances in quantum complexity and information with probability and random matrices. Furthermore, we apply algebraic geometry to generalize the well-known Berlekamp-Welch algorithm that is widely used in coding theory and cryptography. Our results imply that there is an exponential hardness barrier for the classical simulation of most quantum circuits.