Simulating Large Quantum Circuits on a Small Quantum Computer

Limited quantum memory is one of the most important constraints for near-term quantum devices. Understanding whether a small quantum computer can simulate a larger quantum system, or execute an algorithm requiring more qubits than available, is both of theoretical and practical importance. In this Letter, we introduce cluster parameters $K$ and $d$ of a quantum circuit. The tensor network of such a circuit can be decomposed into clusters of size at most $d$ with at most $K$ qubits of inter-cluster quantum communication. We propose a cluster simulation scheme that can simulate any $(K,d)$-clustered quantum circuit on a $d$-qubit machine in time roughly $2^{O(K)}$, with further speedups possible when taking more fine-grained circuit structure into account. We show how our scheme can be used to simulate clustered quantum systems—such as large molecules—that can be partitioned into multiple significantly smaller clusters with weak interactions among them. By using a suitable clustered ansatz, we also experimentally demonstrate that a quantum variational eigensolver can still achieve the desired performance for estimating the energy of the ${\mathrm{BeH}}_2$ molecule while running on a physical quantum device with half the number of required qubits.

Figure 1

Four phases of our simulation: (1) the original quantum circuit, (2) the corresponding tensor network, (3) a collection of tensor networks obtained by cutting an edge, and (4) a collection of smaller quantum circuits.

Figure 2

A $(2,n+1)$-clustered circuit with three dense blocks. While any partition of its qubits induces $\mathrm{\Omega }(n)$ gates between different parts, merging blocks $B_1$ and $B_3$ into a single cluster results in only two qubits communicated between the two clusters. In this example, the size and the depth of the circuit after clustering are both reduced compared to the original circuit.

Figure 3

Interaction graph $G$ of a local Hamiltonian with four parties, each a square grid of size $\sqrt{n}\times \sqrt{n}$. Each pair of adjacent parties has a weak interaction, indicated by the red lines. Since the contraction complexity $cc(g)$ of the induced graph $g$ and the interaction strength $h$ are both $O(1)$, for short periods of time [e.g., $t=O(1)$], this $4n$-qubit system can be efficiently simulated on an $n$-qubit quantum computer.

Figure 4

Estimating the ground energy of ${\mathrm{BeH}}_2$ with interatomic distance of 1.7 Å by running the six-qubit VQE of [48] on ibmq ourense, a five-qubit device provided by the IBM quantum experience [58]. We use up to three qubits of the device. At the $k$th step, we employ the iterative optimization to update $\theta (k)$ based on the simultaneous perturbation stochastic approximation (SPSA) method, similar as [48]. In particular, each run of the six-qubit ansatz $U({\theta }_k)$ with $D=1$ layers is simulated by executing 12 different three-qubit circuits [59].