Trading Classical and Quantum Computational Resources

We propose examples of a hybrid quantum-classical simulation where a classical computer assisted by a small quantum processor can efficiently simulate a larger quantum system. First, we consider sparse quantum circuits such that each qubit participates in $O(1)$ two-qubit gates. It is shown that any sparse circuit on $n+k$ qubits can be simulated by sparse circuits on $n$ qubits and a classical processing that takes time $2^{O(k)}\mathrm{poly}(n)$. Second, we study Pauli-based computation (PBC), where allowed operations are nondestructive eigenvalue measurements of $n$-qubit Pauli operators. The computation begins by initializing each qubit in the so-called magic state. This model is known to be equivalent to the universal quantum computer. We show that any PBC on $n+k$ qubits can be simulated by PBCs on $n$ qubits and a classical processing that takes time $2^{O(k)}\mathrm{poly}(n)$. Finally, we propose a purely classical algorithm that can simulate a PBC on $n$ qubits in a time $2^{\alpha n}\mathrm{poly}(n)$, where $\alpha \approx 0.94$. This improves upon the brute-force simulation method, which takes time $2^n\mathrm{poly}(n)$. Our algorithm exploits the fact that $n$-fold tensor products of magic states admit a low-rank decomposition into $n$-qubit stabilizer states.

Popular Summary

Quantum computers promise a substantial speedup over classical computers for certain number-theoretic problems and the simulation of quantum systems. Recent experimental breakthroughs suggest that a small quantum processor with a few dozen qubits may soon become a reality. Here, we investigate how to add one virtual qubit to an existing quantum machine at the cost of increased classical and quantum running times but without modifying the machine hardware.

A processor with a few dozen qubits would be large enough such that its behavior is impossible to simulate classically, even with the help of modern supercomputers. At the same time, a few dozen qubits might not be enough to run quantum algorithms for practically interesting problem sizes. This quandary motivates the question of whether it is possible to add virtual qubits to an existing quantum machine, thereby enabling the implementation of larger quantum algorithms without having to redesign the machine’s hardware. Here, we theoretically show that, in certain circumstances, the addition of virtual qubits is indeed possible, provided that a quantum processor is combined with a large-scale classical computer to jointly solve a computational task. We provide two examples of when a hybrid quantum-classical computer such as above can mimic a larger quantum computer by making use of virtual qubits. We show that each extra virtual qubit comes at the cost of an increased classical and quantum running time.

We expect that our findings will inform many studies of computation as quantum computers become less of a theoretical construct and begin to approach reality.

Figure 1

Example of a PBC on $n=3$ qubits. Each step $t$ involves an eigenvalue measurement of a Pauli operator $P_t$ on $n$ qubits with an outcome ${\sigma }_t=\pm 1$. A choice of $P_t$ may depend on the outcomes of all previous measurements. A PBC on $n$ qubits can be described by a binary tree $\mathcal{T}$ of height $n$ such that internal nodes of $\mathcal{T}$ are labeled by $n$-qubit Pauli operators and leaves of $\mathcal{T}$ are labeled by 0 and 1. The latter represent the final output bit $b_{\mathrm{out}}$. We require that the label of any leaf node can be computed in time $\mathrm{poly}(n)$ on a classical computer.

Figure 2

Quantum circuit $R$ used to estimate the real part of $⟨{\varphi }_{\alpha }|\mathrm{\Pi }(y)|{\varphi }_{\beta }⟩$ in Eq. (3). The final output of the circuit is a random variable ${\sigma }_{y,\alpha ,\beta }^{\prime }=\pm 1$ such that ${\sigma }_{y,\alpha ,\beta }^{\prime }=1$ if and only if $b=0$ and $f(yz)=1$, where $f$: $\{0,1{\}}^{n+k}\to \{0,1\}$ is the Boolean function describing the postprocessing step in the original circuit $U$ on $n+k$ qubits. We construct a circuit $R$ as above for each triple $(y,\alpha ,\beta )$, with $y\in \{0,1{\}}^k$ and $\alpha ,\beta =1,\dots ,\chi$. A simple algebra shows that ${\sigma }_{y,\alpha ,\beta }^{\prime }$ is an unbiased estimator of $\mathrm{Re}[⟨{\varphi }_{\alpha }|\mathrm{\Pi }(y)|{\varphi }_{\beta }⟩]$.

Figure 3

Graphs $G^{\prime }$ and $G^{\prime \prime }$ used in the definition of stabilizer states ${\varphi }^{\prime }$ and ${\varphi }^{\prime \prime }$; see Eq. (11).

Figure 4

Implementation of the $T$ gate.