Source-linked AI summary
Simulating Large Quantum Circuits on a Small Quantum Computer
Tianyi Peng, Aram Harrow, Maris Ozols, Xiaodi Wu
TL;DR
Limited quantum memory raises whether smaller quantum devices can simulate larger clustered circuits. The paper introduces a cluster-based simulation scheme using a d-qubit device, and reports theorem-level runtime bounds plus VQE evidence for BeH2.
Problem
Limited quantum memory motivates determining whether larger clustered quantum circuits and algorithms can be simulated on smaller quantum devices.
Method
The paper cuts inter-cluster edges, replaces them with measurement-and-preparation decompositions, and executes the resulting cluster pieces on a d-qubit device.
Results
Theorem 1 gives runtime O(2^4K(n + m)/ϵ^2), while Theorem 2 gives a refined bound depending on d′(g), r, and ϵ; BeH2 VQE accuracy was similar to the full 6-qubit circuit.
Takeaways & Limitations
The scheme supports simulation with reduced quantum memory and demonstrates potential for reducing qubit requirements in near-term VQE applications.
Abstract
from arXiv · showhide
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 BeH$_2$ molecule while running on a physical quantum device with half the number of required qubits.
I: Table of Notation
The notation defines the circuit, graph, tensor, clustering, and contraction-complexity quantities used throughout the paper.
- C denotes the quantum circuit, while f denotes its classical post-processing function.
- y is the n-bit string obtained by measuring all qubits.
- G is the graph associated with the circuit or Hamiltonian, and A is its associated set of tensors.
- K denotes the number of edges between different clusters of G, while d is the number of qubits sufficient to simulate each cluster.
- g is obtained by contracting each cluster of G to one vertex, and cc(g) denotes its contraction complexity.
II: Tensor networks
The paper represents quantum circuits as tensor networks: graph vertices encode inputs, gates, and observables, while edges encode qubit flow and tensor indices encode matrix entries.
- Any quantum circuit becomes a directed graph whose vertices represent input states, quantum gates, and observables.
- Directed edges indicate qubit flow, and each vertex carries a tensor encoding the matrix entries of its associated circuit object.
- A tensor-network value is formed by summing products of tensor entries over all possible edge-index assignments.
- The index convention labels incident edges of k-qubit tensors, with subscript locations distinguishing incoming from outgoing qubits.
- Circuit simulation can therefore be performed by approximating the value of the corresponding tensor network.
- The proof framework cuts an edge and replaces it with eight measurement-and-preparation circuits whose combined values preserve the original tensor-network value.
Hoeffding’s inequality
Hoeffding’s inequality bounds the number of independent bounded samples needed for the sample average to approximate its expectation within additive error ϵ.
- For i.i.d. real random variables bounded by |X_i| ≤ a, Hoeffding’s inequality controls deviations of their average from the expectation.
IV: Proof of Theorem 1
Theorem 1 simulates a (K,d)-clustered circuit by cutting its K inter-cluster edges, executing resulting pieces sequentially on a d-qubit device, and averaging sampled outcomes.
- IV: Proof of Theorem 1: A (K,d)-clustered circuit can be simulated with precision ϵ using a d-qubit quantum device, with runtime scaling exponentially in K and polynomially in circuit size and 1/ϵ.
- IV: Proof of Theorem 1: The proof decomposes every inter-cluster edge, producing a modified network indexed by a string s of K decomposition choices.
- IV: Proof of Theorem 1: Each indexed network consists of r pieces executable sequentially on a d-qubit device, with initialization and measurement performed in specified bases.
- IV: Proof of Theorem 1: The simulator samples Pauli measurement outcomes and cluster output strings, then evaluates the classical post-processing function f.
- IV: Proof of Theorem 1: The sampling procedure estimates the tensor-network value by averaging independent samples, with Hoeffding’s inequality determining the required experiment count.
- IV: Proof of Theorem 1: The total classical and quantum runtime is O(2^4K(n + m)/ϵ^2), where n and m are the circuit’s qubit and gate counts.
V: Proof of Theorem 2
The proof estimates cluster tensors using a d-qubit device, then classically contracts the resulting approximate tensor network. Entrywise estimation accuracy and contraction complexity determine the simulator’s cost and precision.
- Tensor-network estimation: Theorem 2 simulates a clustered QC algorithm by estimating tensor entries on a d-qubit device and classically contracting the approximate network.The method targets the value T(g, a) by replacing the cluster tensor network (g, a) with an estimate (g, ã).
- Runtime: The simulator’s total cost combines quantum tensor-entry estimation with classical contraction and depends on the cluster graph’s degree, number of clusters, accuracy, and original circuit size.The proof bounds the number of tensor entries and repeated circuit executions before simplifying the runtime expression.
- Classical contraction: The approximate network is contracted classically in time poly(r)2^O(cc(g)), where cc(g) is the contraction complexity of the cluster graph.The proof obtains this cost using a near-optimal tree decomposition of the line graph of g.
- Tensor-network estimation: Each cluster tensor entry is estimated by repeatedly running a corresponding d-qubit quantum circuit, producing an approximation ã of the tensor collection a.The circuit measurements provide the entries needed for the reduced network.
- Error control: To achieve precision ϵ, tensor entries must be estimated to accuracy roughly 2^-O(K), where K is the number of inter-cluster edges.The proof uses concentration bounds and a union bound to make all tensor estimates simultaneously accurate with probability at least 2/3.
Appendix VI: Proof of Theorem 3
The proof applies nested Trotterization to Hamiltonian evolution and then uses clustered-circuit simulation to separate parties connected by inter-party interactions. Under efficient preparation and measurement assumptions, the resulting correlation function is approximable on a smaller quantum device.
- Hamiltonian simulation: Theorem 3 considers product initial states, local observables, and Hamiltonians whose terms act within or between parties.Each party contains at most d qubits, while each qubit is affected by at most a constant number of Hamiltonian terms.
- Circuit construction: Nested Trotter approximation converts the Hamiltonian evolution into a quantum circuit composed of one- and two-qubit operations.The construction first separates groups of Hamiltonian terms and then decomposes their evolutions into individual terms.
- Circuit construction: The resulting Trotter circuit uses O(Jh^2t^2/ϵ) gates when the number of Hamiltonian terms J is polynomial in the system size.This bound assumes the stated polynomial-size condition on J.
- Clustered simulation: Partitioning qubits by parties yields an interaction graph whose edges represent two-qubit gates between different parties, with contraction complexity related to the Hamiltonian interaction graph.The graph relation transfers the Hamiltonian’s interaction structure to the circuit used for simulation.
- Clustered simulation: Lemma 8 then provides a (2^O(K), d)-simulator, or a (2^O(cc(g′)), d)-simulator when the measurement function is decomposable.The proof constructs clusters for party-local tensors and separate clusters for cross-party gates.
Appendix VII: VQE experiments
The VQE experiment partitions a six-qubit circuit into two three-qubit clusters and decomposes the cross-cluster CZ gate so each cluster can run separately. The resulting energy estimate has accuracy similar to the full six-qubit implementation.
- Results: The experiment uses up to three qubits on the ibmq ourense device while targeting the BeH2 ground energy at an interatomic distance of 1.7 Å.The six-qubit VQE has 30 parameters for the D = 1 experiment.
- Experimental setup: The experiment evaluates a six-qubit VQE circuit using only three qubits by partitioning the qubits into {1,2,3} and {4,5,6}.The two-qubit CZ(3,4) gate is the cross-cluster interaction addressed by the decomposition.
- Experimental setup: The CZ(3,4) interaction is decomposed into operations that allow the two three-qubit circuits to run separately.The construction uses a gadget in which Z, RZ(π/2), and (I + aZ)/2 are single-qubit operations.
- Results: The three-qubit implementation achieves accuracy similar to the full six-qubit circuit, including evaluations at θ−(k), θ+(k), and θ(k).The comparison is shown in Fig. 5 for estimating the BeH2 ground energy.
Appendix VIII: Reducing cc(g) in VQE
The VQE experiments reduce contraction complexity by removing cross-partition entangling gates from selected layers. This creates a time–expressivity trade-off, while the tested partial replacement settings preserve performance more closely than reducing entanglement depth alone.
- Circuit modification: The proposed VQE modification partitions qubits, removes entangling gates crossing the partition, and replaces selected U_ENT occurrences with U′_ENT.The modified circuit is then evaluated through Pauli measurements and classical post-processing.
- Time–performance trade-off: The modification trades runtime against expressive power: lower cc(g) reduces simulation time but can degrade solution quality.The authors note that this trade-off may be justified when the true ground state obeys an area law.
- Circuit modification: Removing cross-partition gates decreases the inter-cluster gate structure and can reduce the simulation time.The modified circuit’s simulator depends on the contraction complexity of its induced cluster graph.
- Numerical comparison: For n = 6, the blue setting uses D = 9 and D1 = 9, the red setting D = 9 and D1 = 3, and the yellow setting D = 3 and D1 = 3.These settings compare full and partial replacement of the entangling sequence across circuit depths.
- Numerical comparison: The blue and red settings behave similarly, while both outperform the yellow setting in the reported numerical experiments.The comparison indicates that replacing some U_ENT by U′_ENT need not greatly influence VQE performance for this problem.