Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2112.15083

Classical Sampling of Random Quantum Circuits with Bounded Fidelity

Gleb Vyacheslavovich Kalachev, Pavel Panteleev, Pengfei Zhou, Man‐Hong Yung

Published Dec 30, 2021• 2 citations
arXivHTMLPDF

Abstract

Random circuit sampling has become a popular means for demonstrating the superiority of quantum computers over classical supercomputers. While quantum chips are evolving rapidly, classical sampling algorithms are also getting better and better. The major challenge is to generate bitstrings exhibiting an XEB fidelity above that of the quantum chips. Here we present a classical sampling algorithm for producing the probability distribution of any given random quantum circuit, where the fidelity can be rigorously bounded. Specifically, our algorithm performs rejection sampling after the introduced very recently multi-tensor contraction algorithm. We show that the fidelity can be controlled by partially contracting the dominant paths in the tensor network and by adjusting the number of batches used in the rejection sampling. As a demonstration, we classically produced 1 million samples with the fidelity bounded by 0.2%, based on the 20-cycle circuit of the Sycamore 53-qubit quantum chip. Though this task was initially estimated to take 10,000 years on the Summit supercomputer, it took about 14.5 days using our algorithm on a relatively small cluster with 32 GPUs (Tesla V100 16GB). Furthermore, we estimate that for the Zuchongzhi 56-qubit 20-cycle circuit one can produce 1M samples with fidelity 0.066% using the Selene supercomputer with 4480 GPUs (Tesla A100 80GB) in about 4 days.

DOI
10.48550/arxiv.2112.15083

Related papers

Solving the Sampling Problem of the Sycamore Quantum Circuits

Feng Ping Pan, Keyang Chen, Pan Zhang

We study the problem of generating independent samples from the output distribution of Google's Sycamore quantum circuits with a target fidelity, which is believed to be beyond the reach of classical supercomputers and has been used to demonstrate quantum supremacy. We propose a method to classically solve this problem by contracting the corresponding tensor network just once, and is massively more efficient than existing methods in generating a large number of uncorrelated samples with a target fidelity. For the Sycamore quantum supremacy circuit with 53 qubits and 20 cycles, we have generated 1×10^{6} uncorrelated bitstrings s which are sampled from a distribution P[over ^](s)=|ψ[over ^](s)|^{2}, where the approximate state ψ[over ^] has fidelity F≈0.0037. The whole computation has cost about 15 h on a computational cluster with 512 GPUs. The obtained 1×10^{6} samples, the contraction code and contraction order are made public. If our algorithm could be implemented with high efficiency on a modern supercomputer with ExaFLOPS performance, we estimate that ideally, the simulation would cost a few dozens of seconds, which is faster than Google's quantum hardware.

arXiv:2111.03011•Physical Review Letters•Aug 22, 2022•142 citations

Multi-Tensor Contraction for XEB Verification of Quantum Circuits

Gleb Vyacheslavovich Kalachev, Pavel Panteleev, Man‐Hong Yung

The computational advantage of noisy quantum computers has been demonstrated by sampling the bitstrings of quantum random circuits. An important issue is how the performance of quantum devices could be quantified in the so-called "supremacy regime". The standard approach is through the linear cross entropy benchmark (XEB), where the theoretical value of the probability is required for each bitstring. However, the computational cost of XEB grows exponentially. So far, random circuits of the 53-qubit Sycamore chip were verified up to 10 cycles of gates only; the XEB fidelities of deeper circuits were approximated with simplified circuits instead. Here we present a multi-tensor contraction algorithm for speeding up the calculations of XEB for quantum circuits, where the computational cost can be significantly reduced through some form of memoization. As a demonstration, we analyzed the experimental data of the 53-qubit Sycamore chip and obtained the exact values of the corresponding XEB fidelities up to 16 cycles using only moderate computing resources (few GPUs). If the algorithm was implemented on the Summit supercomputer, we estimate that for the supremacy (20 cycles) circuits, it would only cost 7.5 days, which is several orders of magnitude lower than previously estimated in the literature.

arXiv:2108.05665•Aug 12, 2021•9 citations

Quantum computational advantage in random-circuit sampling on IBM superconducting quantum computers

Tigran Sedrakyan, Yuxuan Zhang, Hovnatan Karapetyan +3 more

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 $\sim$$10^{22}$ complex operations. At $F_{\mathrm{XEB}}(36)=2.3\times10^{-3}$ under favorable memory assumptions this implies $1.2\times10^{27}$ machine operations within the bounded-fidelity rejection-sampling model --- more than a century of runtime on the Frontier supercomputer --- to collect a $10^{6}$-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.

quant-pharXiv:2609.28657•Sep 25, 2026•0 citations

Recursive Multi-Tensor Contraction for XEB Verification of Quantum Circuits

Gleb Vyacheslavovich Kalachev, Pavel Panteleev, Man‐Hong Yung

The computational advantage of noisy quantum computers have been demonstrated by sampling the bitstrings of quantum random circuits. An important issue is how the performance of quantum devices could be quantified in the so-called regime. The standard approach is through the linear cross entropy (XEB), where the theoretical value of the probability is required for each bitstring. However, the computational cost of XEB grows exponentially. So far, random circuits of the 53-qubit Sycamore chip was verified up to 10 cycles of gates only; the XEB fidelities of deeper circuits were approximated with simplified circuits instead. Here we present a multi-tensor contraction algorithm for speeding up the calculations of XEB of quantum circuits, where the computational cost can be significantly reduced through a recursive manner with some form of memoization. As a demonstration, we analyzed the experimental data of the 53-qubit Sycamore chip and obtained the exact values of the corresponding XEB fidelities up to 16 cycles using only moderate computing resources (few GPUs). If the algorithm was implemented on the Summit supercomputer, we estimate that for the 20-cycles supremacy circuits, it would only cost 7.5 days, which is several orders of magnitudes lower than previously estimated in the literature.

•Aug 12, 2021•1 citation

Simulating the Sycamore quantum supremacy circuits

Feng Ping Pan, Pan Zhang

We propose a general tensor network method for simulating quantum circuits. The method is massively more efficient in computing a large number of correlated bitstring amplitudes and probabilities than existing methods. As an application, we study the sampling problem of Google's Sycamore circuits, which are believed to be beyond the reach of classical supercomputers and have been used to demonstrate quantum supremacy. Using our method, employing a small computational cluster containing 60 graphical processing units (GPUs), we have generated one million correlated bitstrings with some entries fixed, from the Sycamore circuit with 53 qubits and 20 cycles, with linear cross-entropy benchmark (XEB) fidelity equals 0.739, which is much higher than those in Google's quantum supremacy experiments.

arXiv:2103.03074•Mar 4, 2021•46 citations

Race for Quantum Advantage using Random Circuit Sampling

Sangchul Oh, Sabre Kais

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.

arXiv:2211.13267•Nov 23, 2022•0 citations
Random circuit sampling has become a popular means for demonstrating the superiority of quantum computers over classical supercomputers. While quantum chips are evolving rapidly, classical sampling algorithms are also getting better and better. The major challenge is to generate bitstrings exhibiting an XEB fidelity above that of the quantum chips. Here we present a classical sampling algorithm for producing the probability distribution of any given random quantum circuit, where the fidelity can be rigorously bounded. Specifically, our algorithm performs rejection sampling after the introduced very recently multi-tensor contraction algorithm. We show that the fidelity can be controlled by partially contracting the dominant paths in the tensor network and by adjusting the number of batches used in the rejection sampling. As a demonstration, we classically produced 1 million samples with the fidelity bounded by 0.2%, based on the 20-cycle circuit of the Sycamore 53-qubit quantum chip. Though this task was initially estimated to take 10,000 years on the Summit supercomputer, it took about 14.5 days using our algorithm on a relatively small cluster with 32 GPUs (Tesla V100 16GB). Furthermore, we estimate that for the Zuchongzhi 56-qubit 20-cycle circuit one can produce 1M samples with fidelity 0.066% using the Selene supercomputer with 4480 GPUs (Tesla A100 80GB) in about 4 days.
We study the problem of generating independent samples from the output distribution of Google's Sycamore quantum circuits with a target fidelity, which is believed to be beyond the reach of classical supercomputers and has been used to demonstrate quantum supremacy. We propose a method to classically solve this problem by contracting the corresponding tensor network just once, and is massively more efficient than existing methods in generating a large number of uncorrelated samples with a target fidelity. For the Sycamore quantum supremacy circuit with 53 qubits and 20 cycles, we have generated 1×10^{6} uncorrelated bitstrings s which are sampled from a distribution P[over ^](s)=|ψ[over ^](s)|^{2}, where the approximate state ψ[over ^] has fidelity F≈0.0037. The whole computation has cost about 15 h on a computational cluster with 512 GPUs. The obtained 1×10^{6} samples, the contraction code and contraction order are made public. If our algorithm could be implemented with high efficiency on a modern supercomputer with ExaFLOPS performance, we estimate that ideally, the simulation would cost a few dozens of seconds, which is faster than Google's quantum hardware.
The computational advantage of noisy quantum computers has been demonstrated by sampling the bitstrings of quantum random circuits. An important issue is how the performance of quantum devices could be quantified in the so-called "supremacy regime". The standard approach is through the linear cross entropy benchmark (XEB), where the theoretical value of the probability is required for each bitstring. However, the computational cost of XEB grows exponentially. So far, random circuits of the 53-qubit Sycamore chip were verified up to 10 cycles of gates only; the XEB fidelities of deeper circuits were approximated with simplified circuits instead. Here we present a multi-tensor contraction algorithm for speeding up the calculations of XEB for quantum circuits, where the computational cost can be significantly reduced through some form of memoization. As a demonstration, we analyzed the experimental data of the 53-qubit Sycamore chip and obtained the exact values of the corresponding XEB fidelities up to 16 cycles using only moderate computing resources (few GPUs). If the algorithm was implemented on the Summit supercomputer, we estimate that for the supremacy (20 cycles) circuits, it would only cost 7.5 days, which is several orders of magnitude lower than previously estimated in the literature.
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 ∼\sim∼102210^{22}1022 complex operations. At FXEB(36)=2.3×10−3F_{\mathrm{XEB}}(36)=2.3\times10^{-3}FXEB​(36)=2.3×10−3 under favorable memory assumptions this implies 1.2×10271.2\times10^{27}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 10610^{6}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.
The computational advantage of noisy quantum computers have been demonstrated by sampling the bitstrings of quantum random circuits. An important issue is how the performance of quantum devices could be quantified in the so-called regime. The standard approach is through the linear cross entropy (XEB), where the theoretical value of the probability is required for each bitstring. However, the computational cost of XEB grows exponentially. So far, random circuits of the 53-qubit Sycamore chip was verified up to 10 cycles of gates only; the XEB fidelities of deeper circuits were approximated with simplified circuits instead. Here we present a multi-tensor contraction algorithm for speeding up the calculations of XEB of quantum circuits, where the computational cost can be significantly reduced through a recursive manner with some form of memoization. As a demonstration, we analyzed the experimental data of the 53-qubit Sycamore chip and obtained the exact values of the corresponding XEB fidelities up to 16 cycles using only moderate computing resources (few GPUs). If the algorithm was implemented on the Summit supercomputer, we estimate that for the 20-cycles supremacy circuits, it would only cost 7.5 days, which is several orders of magnitudes lower than previously estimated in the literature.
We propose a general tensor network method for simulating quantum circuits. The method is massively more efficient in computing a large number of correlated bitstring amplitudes and probabilities than existing methods. As an application, we study the sampling problem of Google's Sycamore circuits, which are believed to be beyond the reach of classical supercomputers and have been used to demonstrate quantum supremacy. Using our method, employing a small computational cluster containing 60 graphical processing units (GPUs), we have generated one million correlated bitstrings with some entries fixed, from the Sycamore circuit with 53 qubits and 20 cycles, with linear cross-entropy benchmark (XEB) fidelity equals 0.739, which is much higher than those in Google's quantum supremacy experiments.
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.