Physical Review X

"What limits the simulation of quantum computers?"

November 23, 2020

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 F(1ϵ)ND with an error rate ϵ per operation as small as 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 ϵ 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 ϵ can be decreased at a polynomial cost in computing power down to a minimum error ϵ. Getting below ϵ requires computing resources that increase exponentially with ϵ/ϵ. 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.

Access to the paper:

Other Interesting Articles

Go to Editor View