What Limits the Simulation of Quantum Computers?

By Yiqing Zhou, E. Stoudenmire, X. Waintal. Physical Review X, 2020

296 citations recorded by the source corpus.

It is imperative that useful quantum computers be very difficult to simulate classically; otherwise classical computers could be used for the applications envisioned for the quantum ones. Perfect quantum computers are unarguably exponentially difficult to simulate: the classical resources required grow exponentially with the number of qubits $N$ or the depth $D$ of the circuit. Real quantum computing devices, however, are characterized by an exponentially decaying fidelity $\mathcal{F} \sim (1-\epsilon)^{ND}$ with an error rate $\epsilon$ per operation as small as $\approx 1\%$ for current devices. In this work, we demonstrate that real quantum computers can be simulated at a tiny fraction of the cost that would be needed for a perfect quantum computer. Our algorithms compress the representations of quantum wavefunctions using matrix product states (MPS), which capture states with low to moderate entanglement very accurately. This compression introduces a finite error rate $\epsilon$ so that the algorithms closely mimic the behavior of real quantum computing devices. The computing time of our algorithm increases only linearly with $N$ and $D$. We illustrate our algorithms with simulations of random circuits for qubits connected in both one and two dimensional lattices. We find that $\epsilon$ can be decreased at a polynomial cost in computing power down to a minimum error $\epsilon_\infty$. Getting below $\epsilon_\infty$ requires computing resources that increase exponentially with $\epsilon_\infty/\epsilon$. For a two dimensional array of $N=54$ qubits and a circuit with Control-Z gates, error rates better than state-of-the-art devices can be obtained on a laptop in a few hours. For more complex gates such as a swap gate followed by a controlled rotation, the error rate increases by a factor three for similar computing time.

Subfields: Artificial Intelligence, Atomic and Molecular Physics, and Optics

View Paper: https://www.semanticscholar.org/paper/21da1ece3dc07374e9e9be264c0c711bb7f3cd0a

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Atomic and Molecular Physics, and Optics

Citations in the corpus

Harnessing the Power of the Second Quantum Revolution (2020, background): “Zhou et al. have shown that one can eﬃciently simulate a class of quasi-1D random circuits by truncating the bond dimension of a matrix-product-state (MPS) representation and achieve a global ﬁdelity of F ≥ 0.002 for depth-20 1D random quantum circuits with 54 qubits [133].”
Evidence for the utility of quantum computing before fault tolerance (2023, methodology): “For example, it was recently argued that the finite-χ truncation error introduced by tensor-product compression mimics experimental gate errors 34 .”
The ITensor Software Library for Tensor Network Calculations (2020, methodology): “46,47]. ITensor was also used in a recent study by Zhou et al. which shows that if a quantum computing device is suciently noisy, experiments performed with it can be eciently simulated classically [48]. A rather dierent application area of tensor networks is applied mathematics and machine learning”