Abstract
The quantum circuits that declare quantum supremacy, such as Google Sycamore [Nature 574, 505 (2019)], raises a paradox in building reliable result references. While simulation on traditional computers seems the sole way to provide reliable verification, the required run time is doomed with an exponentially-increasing compute complexity. To find a way to validate current "quantum-supremacy" circuits with more than 50 qubits, we propose a simulation method that exploits the "classical advantage" (the inherent "store-and-compute" operation mode of von Neumann machines) of current supercomputers, and computes uncorrelated amplitudes of a random quantum circuit with an optimal reuse of the intermediate results and a minimal memory overhead throughout the process. Such a reuse strategy reduces the original linear scaling of the total compute cost against the number of amplitudes to a sublinear pattern, with greater reduction for more amplitudes. Based on a well-optimized implementation of this method on a new-generation Sunway supercomputer, we directly verify Sycamore by computing three million exact amplitudes for the experimentally generated bitstrings, obtaining an XEB fidelity of 0.191% which closely matches the estimated value of 0.224%. Our computation scales up to 41,932,800 cores with a sustained single-precision performance of 84.8 Pflops, which is accomplished within 8.5 days. Our method has a far-reaching impact in solving quantum many-body problems, statistical problems as well as combinatorial optimization problems where one often needs to contract many tensor networks which share a significant portion of tensors in common.
Introduction
In 2019, Google’s 53-qubit Sycamore processor performed a random quantum circuit (RQC) sampling task in 200 seconds—a feat estimated to take the world’s fastest supercomputer 10,000 years. This milestone, termed "quantum supremacy," challenged the limits of classical computation. However, verifying such claims requires calculating exact amplitudes for the bitstrings produced by the quantum device—a task whose complexity grows exponentially with qubit count and circuit depth. While previous classical methods could compute correlated batches of amplitudes, the challenge of computing millions of uncorrelated amplitudes for a full-scale Sycamore circuit remained a significant barrier to direct verification.
Methodology: Multiple-Amplitude Tensor Network Contraction
To address this, we introduce the Multiple-Amplitude Tensor Network Contraction (ma-TNC) algorithm. Unlike quantum computers, which are limited by the no-cloning theorem, classical von Neumann machines can store and reuse intermediate results. We exploit this "classical advantage" by organizing the tensor network contraction into a hierarchical reuse tree.
As shown in Figure 1, the computation is divided into three stages:
- Trunk: Common intermediate tensor results shared across all target amplitudes are computed once.
- Branch: Intermediate results shared by subsets of amplitudes are computed and cached.
- Twig: The final, unique contractions for individual bitstrings are performed.
This static reuse strategy ensures predictable memory and compute costs, facilitating massive parallelization. Furthermore, we implemented a fused tensor network contraction algorithm to mitigate data movement bottlenecks on heterogeneous supercomputers. By performing successive contractions locally on each core, we significantly increased compute density.
Performance and Scaling
The ma-TNC approach transforms the computational scaling of amplitude calculation. Traditionally, the cost of computing $k$ amplitudes scales linearly ($O(k)$). By optimizing the reuse tree, our method achieves sublinear scaling.
As illustrated in Figure 2, for $k \approx 10^6$ amplitudes, the computational complexity is reduced by over three orders of magnitude compared to single-amplitude methods (sa-TNC). This efficiency gain narrowed the gap between classical and quantum performance to a factor of only ~2.5x per amplitude for the Sycamore task.
Verification of the Sycamore Experiment
We deployed our optimized implementation on the new-generation Sunway supercomputer, utilizing nearly 42 million cores. Over 8.5 days, we computed 3 million exact amplitudes for the depth-20 Sycamore RQC samples.
The resulting Cross-Entropy Benchmarking (XEB) fidelity was 0.191%, closely aligning with Google’s original estimate of 0.224%. This result provides a rigorous classical verification of the Sycamore experiment. Additionally, the calculated amplitudes followed the expected Porter-Thomas distribution, further confirming the integrity of the quantum sampling.
Conclusion
Our work demonstrates that advanced tensor network contraction algorithms, coupled with exascale classical computing power, can effectively verify current quantum supremacy experiments. While newer quantum experiments continue to push the boundaries of complexity, the ma-TNC and fused contraction techniques provide a powerful framework for solving complex problems in quantum many-body physics, statistical mechanics, and combinatorial optimization.
Summary updated