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:1805.01450

Classical Simulation of Intermediate-Size Quantum Circuits

Jianxin Chen, Fang Zhang, Cupjin Huang, Michael Newman, Yaoyun Shi

Published May 3, 2018• 77 citations
arXivHTMLPDF

Abstract

We introduce a distributed classical simulation algorithm for general quantum circuits, and present numerical results for calculating the output probabilities of universal random circuits. We find that we can simulate more qubits to greater depth than previously reported using the cluster supported by the Data Infrastructure and Search Technology Division of the Alibaba Group. For example, computing a single amplitude of an $8\times 8$ qubit circuit with depth $40$ was previously beyond the reach of supercomputers. Our algorithm can compute this within $2$ minutes using a small portion ($\approx$ 14% of the nodes) of the cluster. Furthermore, by successfully simulating quantum supremacy circuits of size $9\times 9\times 40$, $10\times 10\times 35 $, $11\times 11\times 31$, and $12\times 12\times 27 $, we give evidence that noisy random circuits with realistic physical parameters may be simulated classically. This suggests that either harder circuits or error-correction may be vital for achieving quantum supremacy from random circuit sampling.

DOI
10.48550/arxiv.1805.01450

Related papers

Simulation of low-depth quantum circuits as complex undirected graphical models

Sergio Boixo, Sergei V. Isakov, Vadim Smelyanskiy +1 more

Near term quantum computers with a high quantity (around 50) and quality (around 0.995 fidelity for two-qubit gates) of qubits will approximately sample from certain probability distributions beyond the capabilities of known classical algorithms on state-of-the-art computers, achieving the first milestone of so-called quantum supremacy. This has stimulated recent progress in classical algorithms to simulate quantum circuits. Classical simulations are also necessary to approximate the fidelity of multiqubit quantum computers using cross entropy benchmarking. Here we present numerical results of a classical simulation algorithm to sample universal random circuits, on a single workstation, with more qubits and depth than previously reported. For example, circuits with $5 \times 9$ qubits of depth 37, $7 \times 8$ qubits of depth 27, and $10 \times (κ> 10)$) qubits of depth 19 are all easy to sample. We also show up to what depth the sampling, or estimation of observables, is trivially parallelizable. The algorithm is related to the "Feynmann path" method to simulate quantum circuits. For low-depth circuits, the algorithm scales exponentially in the depth times the smaller lateral dimension, or the treewidth, as explained in Boixo et. al., and therefore confirms the bounds in that paper. In particular, circuits with $7 \times 7$ qubits and depth 40 remain currently out of reach. Follow up work on a supercomputer environment will tighten this bound.

arXiv:1712.05384•Dec 14, 2017•73 citations

Quantum supremacy and random circuits

Ramis Movassagh

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.

arXiv:1909.06210•Sep 11, 2019•23 citations

Quantum Supremacy Circuit Simulation on Sunway TaihuLight

Riling Li, Bujiao Wu, Mingsheng Ying +2 more

With the rapid progress made by industry and academia, quantum computers with dozens of qubits or even larger size are being realized. However, the fidelity of existing quantum computers often sharply decreases as the circuit depth increases. Thus, an ideal quantum circuit simulator on classical computers, especially on high-performance computers, is needed for benchmarking and validation. We design a large-scale simulator of universal random quantum circuits, often called “quantum supremacy circuits”, and implement it on Sunway TaihuLight. The simulator can be used to accomplish the following two tasks: 1) Computing a complete output state-vector; 2) Calculating one or a few amplitudes. We target the simulation of 49-qubit circuits. For task 1), we successfully simulate such a circuit of depth 39, and for task 2) we reach the 55-depth level. To the best of our knowledge, both of the simulation results reach the largest depth for 49-qubit quantum supremacy circuits.

arXiv:1804.04797•IEEE Transactions on Parallel and Distributed Systems•Oct 15, 2019•71 citations

Can Chaotic Quantum Circuits Maintain Quantum Supremacy under Noise?

Man‐Hong Yung, Xun Gao

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.

arXiv:1706.08913•Jun 27, 2017•8 citations

Efficient Classical Simulation of Random Shallow 2D Quantum Circuits

John C. Napp, Rolando L. La Placa, Alexander M. Dalzell +2 more

A central question of quantum computing is determining the source of the advantage of quantum computation over classical computation.Even though simulating quantum dynamics on a classical computer is thought to require exponential overhead in the worst case, efficient simulations are known to exist in several special cases.It was widely assumed that these easy-to-simulate cases as well as any yetundiscovered ones could be avoided by choosing a quantum circuit at random.We prove that this intuition is false by showing that certain families of constant-depth, 2D random circuits can be approximately simulated on a classical computer in time only linear in the number of qubits and gates, even though the same families are capable of universal quantum computation and are hard to exactly simulate in the worst case (under standard hardness assumptions).While our proof applies to specific random circuit families, we demonstrate numerically that typical instances of more general families of sufficiently shallow constantdepth 2D random circuits are also efficiently simulable.We propose two classical simulation algorithms.One is based on first simulating spatially local regions which are then "stitched" together via recovery maps.The other reduces the 2D simulation problem to a problem of simulating a form of 1D dynamics consisting of alternating rounds of random local unitaries and weak measurements.Similar processes have recently been the subject of an intensive research focus, which has observed that the dynamics generally undergo a phase transition from a low-entanglement (and efficient-to-simulate) regime to a highentanglement (and inefficient-to-simulate) regime as measurement strength is varied.Via a mapping from random quantum circuits to classical statistical mechanical models, we give analytical evidence that a similar computational phase transition occurs for both of our algorithms as parameters of the circuit architecture like the local Hilbert space dimension and circuit depth are varied and, additionally, that the effective 1D dynamics corresponding to sufficiently shallow random quantum circuits falls within the efficient-to-simulate regime.Implementing the latter algorithm for the depth-3 "brickwork" architecture, for which exact simulation is hard, we find that a laptop could simulate typical instances on a 409 × 409 grid with a total variation distance error less than 0.01 in approximately one minute per sample, a task intractable for previously known circuit simulation algorithms.Numerical results support our analytic evidence that the algorithm is asymptotically efficient.

arXiv:2001.00021•Physical Review X•Apr 27, 2022•140 citations

Improved robustness of quantum supremacy for random circuit sampling

Y. Kondo, Ryuhei Mori, Ramis Movassagh

Motivated by the recent experimental demonstrations of quantum supremacy, proving the hardness of the output of random quantum circuits is an imperative near term goal. We prove under the complexity theoretical assumption of the non-collapse of the polynomial hierarchy that approximating the output probabilities of random quantum circuits to within $\exp(-\Omega(m\log m))$ additive error is hard for any classical computer, where $m$ is the number of gates in the quantum computation. More precisely, we show that the above problem is $\#\mathsf{P}$-hard under $\mathsf{BPP}^{\mathsf{NP}}$ reduction. In the recent experiments, the quantum circuit has $n$-qubits and the architecture is a two-dimensional grid of size $\sqrt{n}\times\sqrt{n}$. Indeed for constant depth circuits approximating the output probabilities to within $2^{-\Omega(n\log{n})}$ is hard. For circuits of depth $\log{n}$ or $\sqrt{n}$ for which the anti-concentration property holds, approximating the output probabilities to within $2^{-\Omega(n\log^2{n})}$ and $2^{-\Omega(n^{3/2}\log n)}$ is hard respectively. We made an effort to find the best proofs and proved these results from first principles, which do not use the standard techniques such as the Berlekamp--Welch algorithm, the usual Paturi's lemma, and Rakhmanov's result.

•Feb 3, 2021•5 citations
We introduce a distributed classical simulation algorithm for general quantum circuits, and present numerical results for calculating the output probabilities of universal random circuits. We find that we can simulate more qubits to greater depth than previously reported using the cluster supported by the Data Infrastructure and Search Technology Division of the Alibaba Group. For example, computing a single amplitude of an 8×88\times 88×8 qubit circuit with depth 404040 was previously beyond the reach of supercomputers. Our algorithm can compute this within 222 minutes using a small portion (≈\approx≈ 14% of the nodes) of the cluster. Furthermore, by successfully simulating quantum supremacy circuits of size 9×9×409\times 9\times 409×9×40, 10×10×3510\times 10\times 35 10×10×35, 11×11×3111\times 11\times 3111×11×31, and 12×12×2712\times 12\times 27 12×12×27, we give evidence that noisy random circuits with realistic physical parameters may be simulated classically. This suggests that either harder circuits or error-correction may be vital for achieving quantum supremacy from random circuit sampling.
Near term quantum computers with a high quantity (around 50) and quality (around 0.995 fidelity for two-qubit gates) of qubits will approximately sample from certain probability distributions beyond the capabilities of known classical algorithms on state-of-the-art computers, achieving the first milestone of so-called quantum supremacy. This has stimulated recent progress in classical algorithms to simulate quantum circuits. Classical simulations are also necessary to approximate the fidelity of multiqubit quantum computers using cross entropy benchmarking. Here we present numerical results of a classical simulation algorithm to sample universal random circuits, on a single workstation, with more qubits and depth than previously reported. For example, circuits with 5×95 \times 95×9 qubits of depth 37, 7×87 \times 87×8 qubits of depth 27, and 10×(κ>10)10 \times (κ> 10)10×(κ>10)) qubits of depth 19 are all easy to sample. We also show up to what depth the sampling, or estimation of observables, is trivially parallelizable. The algorithm is related to the "Feynmann path" method to simulate quantum circuits. For low-depth circuits, the algorithm scales exponentially in the depth times the smaller lateral dimension, or the treewidth, as explained in Boixo et. al., and therefore confirms the bounds in that paper. In particular, circuits with 7×77 \times 77×7 qubits and depth 40 remain currently out of reach. Follow up work on a supercomputer environment will tighten this bound.
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 505050 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−53-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\#P#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.
With the rapid progress made by industry and academia, quantum computers with dozens of qubits or even larger size are being realized. However, the fidelity of existing quantum computers often sharply decreases as the circuit depth increases. Thus, an ideal quantum circuit simulator on classical computers, especially on high-performance computers, is needed for benchmarking and validation. We design a large-scale simulator of universal random quantum circuits, often called “quantum supremacy circuits”, and implement it on Sunway TaihuLight. The simulator can be used to accomplish the following two tasks: 1) Computing a complete output state-vector; 2) Calculating one or a few amplitudes. We target the simulation of 49-qubit circuits. For task 1), we successfully simulate such a circuit of depth 39, and for task 2) we reach the 55-depth level. To the best of our knowledge, both of the simulation results reach the largest depth for 49-qubit quantum supremacy circuits.
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.
A central question of quantum computing is determining the source of the advantage of quantum computation over classical computation.Even though simulating quantum dynamics on a classical computer is thought to require exponential overhead in the worst case, efficient simulations are known to exist in several special cases.It was widely assumed that these easy-to-simulate cases as well as any yetundiscovered ones could be avoided by choosing a quantum circuit at random.We prove that this intuition is false by showing that certain families of constant-depth, 2D random circuits can be approximately simulated on a classical computer in time only linear in the number of qubits and gates, even though the same families are capable of universal quantum computation and are hard to exactly simulate in the worst case (under standard hardness assumptions).While our proof applies to specific random circuit families, we demonstrate numerically that typical instances of more general families of sufficiently shallow constantdepth 2D random circuits are also efficiently simulable.We propose two classical simulation algorithms.One is based on first simulating spatially local regions which are then "stitched" together via recovery maps.The other reduces the 2D simulation problem to a problem of simulating a form of 1D dynamics consisting of alternating rounds of random local unitaries and weak measurements.Similar processes have recently been the subject of an intensive research focus, which has observed that the dynamics generally undergo a phase transition from a low-entanglement (and efficient-to-simulate) regime to a highentanglement (and inefficient-to-simulate) regime as measurement strength is varied.Via a mapping from random quantum circuits to classical statistical mechanical models, we give analytical evidence that a similar computational phase transition occurs for both of our algorithms as parameters of the circuit architecture like the local Hilbert space dimension and circuit depth are varied and, additionally, that the effective 1D dynamics corresponding to sufficiently shallow random quantum circuits falls within the efficient-to-simulate regime.Implementing the latter algorithm for the depth-3 "brickwork" architecture, for which exact simulation is hard, we find that a laptop could simulate typical instances on a 409 × 409 grid with a total variation distance error less than 0.01 in approximately one minute per sample, a task intractable for previously known circuit simulation algorithms.Numerical results support our analytic evidence that the algorithm is asymptotically efficient.
Motivated by the recent experimental demonstrations of quantum supremacy, proving the hardness of the output of random quantum circuits is an imperative near term goal. We prove under the complexity theoretical assumption of the non-collapse of the polynomial hierarchy that approximating the output probabilities of random quantum circuits to within exp⁡(−Ω(mlog⁡m))\exp(-\Omega(m\log m))exp(−Ω(mlogm)) additive error is hard for any classical computer, where mmm is the number of gates in the quantum computation. More precisely, we show that the above problem is #P\#\mathsf{P}#P-hard under BPPNP\mathsf{BPP}^{\mathsf{NP}}BPPNP reduction. In the recent experiments, the quantum circuit has nnn-qubits and the architecture is a two-dimensional grid of size n×n\sqrt{n}\times\sqrt{n}n​×n​. Indeed for constant depth circuits approximating the output probabilities to within 2−Ω(nlog⁡n)2^{-\Omega(n\log{n})}2−Ω(nlogn) is hard. For circuits of depth log⁡n\log{n}logn or n\sqrt{n}n​ for which the anti-concentration property holds, approximating the output probabilities to within 2−Ω(nlog⁡2n)2^{-\Omega(n\log^2{n})}2−Ω(nlog2n) and 2−Ω(n3/2log⁡n)2^{-\Omega(n^{3/2}\log n)}2−Ω(n3/2logn) is hard respectively. We made an effort to find the best proofs and proved these results from first principles, which do not use the standard techniques such as the Berlekamp--Welch algorithm, the usual Paturi's lemma, and Rakhmanov's result.