What Limits the Simulation of Quantum Computers?

An ultimate goal of quantum computing is to perform calculations beyond the reach of any classical computer. It is therefore 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. This difficulty has triggered recent experiments on deep, random circuits that aim to demonstrate that quantum devices may already perform tasks beyond the reach of classical computing. These real quantum computing devices, however, suffer from many sources of decoherence and imprecision which limit the degree of entanglement that can actually be reached to a fraction of its theoretical maximum. They 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 with several dozen qubits or even smaller for smaller devices. In this work, we provide new insight on the computing capabilities of real quantum computers by demonstrating that they 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 wave functions using matrix product states, which are able to 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$ in sharp contrast with exact simulation algorithms. 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 3 for similar computing time. Our results suggest that, despite the high fidelity reached by quantum devices, only a tiny fraction $(\sim {10}^{-8})$ of the system Hilbert space is actually being exploited.

Popular Summary

One of the main goals in quantum computing is to demonstrate “quantum supremacy”—completion of a task that cannot be done in any feasible amount of time on a traditional computer. Recently, Google claimed they had developed a quantum device that quickly solved a problem that would require ten thousand years on the largest supercomputers. That claim was challenged by others, who said the task would need only two days. This disparity highlights the challenges inherent to benchmarks of quantum-computing performance. To address that challenge, we develop algorithms that show that real quantum computers—plagued by interference from their environment—can be simulated at a tiny fraction of the computational cost that is needed for a perfect quantum device.

Simulating a quantum computer on a classical one does indeed require a phenomenal amount of resources when no approximations are made and noise is not considered. Exact algorithms for simulating quantum computers require time or memory that grows exponentially with the number of qubits or other physical resources. Here, we discuss a class of algorithms that has attracted little attention in the context of quantum-computing simulations. These algorithms use quantum state compression and are exponentially faster than their exact counterparts. In return, they possess a finite fidelity (or finite compression rate, similar to that in image compression), very much as in a real quantum computer.

We find that these approximate algorithms can reach a finite fidelity comparable with state-of-the-art experiments at a very modest computational cost, thus providing a key perspective to the computational power actually harvested by a quantum device.

Figure 1

(a) Sketch of the quantum circuit with $N$ qubits. The colored squares indicate arbitrary 1-qubit gates while the dots connected to a cross indicate a 2-qubit gate such as control-not or control-$Z$. The depth $D$ counts the number of 2-qubit gates performed in the sequence. (b) Structure of the matrix product states (MPS) for 1D circuits. Red lines indicate bond (or virtual) indices while thin black lines correspond to physical indices. (c) MPS structure for quasi-one-dimensional structures.

Figure 2

(a) Applying a single qubit gate to a MPS can be done without approximation by multiplying the gate by a single MPS tensor. (b) To apply a 2-qubit gate to qubits $n$ and $n+1$, one contracts the corresponding tensors together, then applies the gate. To restore the MPS form, the resulting tensor is decomposed with a SVD truncated to keep the largest $\chi$ singular values, and the matrix of singular values is multiplied into one of the unitary factors $X$ or $Y$.

Figure 3

Cumulative distribution $P(p_x<\rho )$, where $p_x=|⟨x|\mathrm{\Psi }⟩{|}^2$ for $N=15$. The dashed line corresponds to the Porter-Thomas distribution, $P_{\mathrm{PT}}(\rho )=1-(1-\rho {)}^{2^N-1}$. Main panel: MPS simulations with truncation, $D=24$, and various MPS truncation levels $\chi =2$ (blue line), 8 (orange line), and 32 (green line). Inset: exact results (i.e., simulations without truncations) for $D=4$ (blue line), 16 (orange line), and 24 (green line). A single realization of the circuit has been used for each distribution.

Figure 4

Effective 2-qubit gate fidelity $f_n$ as a function of the depth $D$ of the circuit for $\chi =64$ and the control-$Z$ gate for $N=40$ (red) and $N=60$ (magenta). The thin lines correspond to the geometric average of $f_n$ over one full sequence, i.e., all the 2-qubit gates performed between depth $D-2$ and depth $D$ ($N-1$ 2-qubit gates). The thick dashed lines correspond to $f_{\mathrm{av}}$, the geometric average of $f_n$ over all 2-qubit gates since the beginning of the circuit up to depth $D$. A single realization of the circuit has been used for each curve.

Figure 5

Geometric average of the residual error per gate ${\epsilon }_{\mathrm{av}}=1-f_{\mathrm{av}}$ as a function of the bond dimension $\chi$. The average is performed over the entire circuit except for the black curves ($D=\infty$) where the average is restricted to the regime where the fidelity has reached its asymptotic value ($100\le D\le 200$); see Fig. 4. For the largest system $N=240$, we have also excluded the gates on the edges of the system in our calculation as they have by construction perfect fidelity. The fluctuations of the average fidelity with different circuits are smaller than the size of the symbols.

Figure 6

Geometric average of the fidelity per gate $f_{\mathrm{av}}$ as a function of the gate position $n$. Only an enlargement close to one edge of the MPS is shown. The average is restricted to the regime where the fidelity has reached its asymptotic value ($100\le D\le 200$); see Fig. 4. A single realization of the circuit has been used, hence the fluctuations. These fluctuations become very small upon further averaging on $n$ as done in Fig. 5.

Figure 7

Fidelity $\mathcal{F}$ versus depth $D$ for $N=20$ and various values of $\chi =10$, 20, 50. The symbols correspond to a direct calculation of $\mathcal{F}$ obtained by comparing with an exact calculation (i.e., without truncation). The lines correspond to the right-hand side of Eq. (17).

Figure 8

Comparison between the fidelity $\mathcal{F}$ (lines) and the XEB metric $\mathcal{B}$ (markers) as a function of depth $D$. Different colors label different levels of noise on the 2-qubit gates, respectively, $f=99.5\%$ (red), $f=99\%$ (green), and $f=98\%$ (blue). The calculations were performed for the 1D random circuit with $N=20$ qubits.

Figure 9

Squared singular values $S_{\mu }^2$ of the matrix $T^{\prime }$ obtained from the GTE ensemble. We find a perfect scaling of the form $S_{\mu }^2=g(\mu /\chi )/\chi$, where $\mu$ is the index of the $\mu$th singular value. The two bundles of curves correspond respectively to the $C_X$,$C_Z$ gates (two nonzero eigenvalues) and the $i{S}_{\pi /6}/iS$ gates (four nonzero eigenvalues). Within one bundle, the different curves are indistinguishable.

Figure 10

Squared singular values $S_{\mu }^2$ of the matrix $T^{\prime }$ obtained from the MPS simulations of $N=30$ qubits and a depth of $D=60$ for various values of $\chi$. The singular values correspond to a gate $C_X$ performed in the middle of the system. Dotted line: squared singular values of the $M$ matrix in the GTE. Dashed line: squared singular values of $T^{\prime }$ in the GTE.

Figure 11

Main steps for applying a gate which acts across two grouped MPS tensors, as described in Eqs. (34) and (35). In (a) the grouped MPS tensors $M(n)$ and $M(n+1)$ are exactly factorized using $QR$ decompositions, such that the $R(n)$ and $R(n+1)$ tensors carry the qubit indices acted on by the gate and the newly introduced indices $\sigma$ and ${\sigma }^{\prime }$ range over $2\chi$ values. In (b) the gate acts on the product of $R(n)$ and $R(n+1)$, and the resulting tensor is factorized using a SVD truncated to $\chi$ singular values. Finally, to update the MPS (not shown), one computes the new tensors $M^{\prime }(n)=Q(n)R^{\prime }(n)$ and $M^{\prime }(n+1)=R^{\prime }(n+1)Q(n+1)$, which diagrammatically looks like step (a) but in reverse.

Figure 12

(a) Sketch of the quantum circuit with 54 qubits in a 2D grid. The qubits are represented by the black dots while the 2-qubit gates by the color links. (b) The circuit alternates 1-qubit gates (black dots) with 2-qubit gates (here the control-$Z$ gate). The depth $D$ counts the number of 2-qubit gates per qubit. (c) Different grouping strategies for the group MPS algorithm. $[1^{12}]$ corresponds to a grouping in 12 blocks counting 1 column each; $[4,2,2,4]$ corresponds to a grouping in 4 blocks counting, respectively, 4, 2, 2, and 4 columns.

Figure 13

Residual error per gate ${\epsilon }_{\mathrm{av}}=1-f_{\mathrm{av}}$ as a function of the bond dimension $\chi$ for the 2D circuit of Fig. 12 for a depth $D=20$. The different curves correspond to different groupings. The horizontal dashed line corresponds to the error rate associated with a global fidelity $\mathcal{F}=0.002$.

Figure 14

Schematic of the split-and-merge algorithm for the $[4,2,2,4]\leftrightarrow [5,2,5]$. The 2-qubit gates shown in red and dark green are performed in the $[4,2,2,4]$ configuration and one switches to the $[5,2,5]$ to perform the light green and purple gates.

Figure 15

Residual error per gate ${\epsilon }_{\mathrm{av}}=1-f_{\mathrm{av}}$ as a function of the bond dimension $\chi$ for the $i{S}_{\theta }$ gate for a 2D circuit with $N=54$ qubits and a depth $D=20$. The different curves correspond to different groupings. The horizontal dashed line corresponds to the error rate associated with a global fidelity $\mathcal{F}=0.002$. The orange line is just a guide to the eye.