Simulating Large Quantum Circuits on a Small Quantum Computer: A (K, d)-Clustered Circuit Is Simulated to Precision ε with Probability 2/3 by O(2^{4K} r/ε²) Runs of d-Qubit PiecesResearch Paper
Why simulate a large circuit with a small device
Near-term quantum processors have few qubits, while the circuits one would like to run (variational eigensolvers, sampling benchmarks, error-mitigated algorithms) often need more qubits than any single device has. Peng, Harrow, Ozols and Wu (arXiv:1904.00102, Phys. Rev. Lett. 125, 150504, 2020) show that a circuit which is only loosely connected (a few qubits pass between otherwise separate parts) can be simulated by running the parts separately on a smaller device and combining the outcomes classically. The overhead is exponential in the number of qubits that cross between parts and polynomial in everything else. The technique is now usually called circuit cutting or wire cutting.
Timeline:
- 2016: Bravyi, Smith and Smolin (Phys. Rev. X 6, 021043) simulate a large circuit with a smaller computer by partitioning its qubits; the cost depends on the number of gates acting across the partition.
- 2019–2020: Peng, Harrow, Ozols and Wu partition the circuit's tensor network instead and cut its edges. The cost is runs of a -qubit device, where is the number of qubits communicated between the clusters (Theorem 1). This is the result of this mission.
Setting
A tensor network is a finite directed multigraph with a complex tensor at every vertex. Every edge carries an index , with elementary matrix . A state , a gate and an observable on one qubit have the tensors
The value of the network is
For the network of a quantum circuit followed by a classical post-processing , the value is the expected output of the algorithm.
A clustering fixes the final observable vertex (no outgoing edges) and puts every other vertex into one of clusters . The cut edges are the edges between different clusters (edges into excluded). The qubit count is the number of input vertices ◁ of (vertices without incoming edges) plus the number of edges entering from other clusters. The network is -clustered if and for all .
Cutting an edge. With the Pauli matrices , the eight triples are , , , , , , and . For , the cut network replaces every cut edge by and , and .
The estimator. For each , running the pieces of on the device yields an outcome whose expectation is . One sample draws uniformly and outputs . The estimate is the average of independent samples.
Formalization targets
Goal: Theorem 1
For a -clustered network with clusters, any device laws as above and , let . Then
Moreover, every cut network splits into clusters with no edges between them, each needing at most qubits. Together, these give the paper's " runs of a -qubit device": samples, each running pieces.
Milestones, in the order the proof uses them
- eq. (21): every matrix equals ;
- eqs. (27)–(28): ;
- eqs. (23)–(30): ;
- Lemma 1: for one cut edge, with , states and Pauli observables with ;
- eqs. (31)–(32): for any set of cut edges;
- eq. (33): , and ;
- Hoeffding's inequality in the paper's form, for ;
- the pieces claim: every cut network falls into pieces of at most qubits;
- eqs. (35)–(36): one sample is unbiased for and bounded by .
Significance
The theorem turns the qubit budget of a device into a parameter of the simulation: a circuit on qubits can be run on qubits at a cost of , which is efficient whenever only qubits pass between clusters. Its edge-cutting identity (Lemma 1) is the basic quasi-probability decomposition of the identity channel. It is reused in the paper's own Theorem 2 (decomposable post-processing, contraction-complexity bounds) and in its Hamiltonian-simulation application.
The theorem has a complete proof with explicit constants on pp. 8–10 of the paper. No machine-checked proof of the theorem or of its edge-cutting lemma is known. Formalizing it gives a machine-checked tensor-network semantics for the cut, the Pauli measure-and-prepare decomposition, and a concrete Monte Carlo guarantee. The general two-sided Hoeffding bound is already proved on the platform (Concentration.hoeffding_two_sided) and is included as a reference.
Difficulty
The decomposition of the identity channel is a finite matrix identity. The difficulty is in carrying it through the network. Cutting edges at once changes the vertex and edge types of the graph, and the sum over must be re-indexed over the new edge set. The obvious route, cutting one edge at a time, changes the type of the graph at every step and does not compose cleanly. The statement is therefore made for a set of edges at once.
A second difficulty is probabilistic. The samples are drawn from a mixture over strings of pushforwards of device laws. Applying Hoeffding's inequality requires the product law of such samples, a bound on their support, and the identification of their mean with the complex value .
Formalization scope
- Edge indices are
Fin 2 × Fin 2. Single-qubit operators areMatrix (Fin 2) (Fin 2) ℂ. The eight cases areFin 8, and Lean's is the paper's . - A network has finite vertex and edge types,
src tgt : E → V, and tensorsA : V → (E → Π) → ℂthat read a full edge labelling. Locality is not imposed, so all statements hold for slightly more general networks than the paper's. Vertex kinds are not recorded: a ◁ is a vertex without incoming edges. - The cut for a set has vertices and edges . The observable ▷ sits on the source side of the edge and reads the original edge. The state ◁ sits on the target side and feeds the target through the new edge. Only the target vertex is rerouted.
- Clusters are labels in
Fin r, and empty clusters are allowed. The qubit count is #◁ plus the incoming cut edges. This is the paper's p. 3 form; the paper's "out-degree" phrasing on p. 2 is not used. - The device is modelled only by its laws: for each , a probability measure on , almost surely in , with mean . This is p. 10's "Note that", taken as a hypothesis. Eq. (10), , is cited in the paper and not formalized. The run-time clause is not formalized (there is no cost model).
- is the paper's with , rounded up. The samples are the coordinates of the -fold product of the one-sample law. The real estimate is compared with the complex in ; no real part is taken.
- Corrections. Eq. (24) cites Eq. (7) for the identity-gate tensor where Eq. (6) is meant; the identity is formalized with (6). Lemma 1's existential "there is a set of eight coefficients …" is stated for the paper's own data, with "valid quantum circuit" pinned down as: positive semidefinite, trace one and idempotent; Hermitian with ; and .
- Ruled out. The cut network is constructed from , and , not assumed. The device laws have mean , not . is explicit, not "some ". The -qubit claim is part of the goal.
- Reusable beyond this mission: the tensor-network value, the edge cut and the Pauli measure-and-prepare data. Contributions of general lemmas on re-indexing sums over are welcome.
Selected references
- T. Peng, A. W. Harrow, M. Ozols, X. Wu, Simulating Large Quantum Circuits on a Small Quantum Computer, arXiv:1904.00102v2 (2020); Phys. Rev. Lett. 125, 150504 (2020). https://arxiv.org/abs/1904.00102
- S. Bravyi, G. Smith, J. A. Smolin, Trading Classical and Quantum Computational Resources, Phys. Rev. X 6, 021043 (2016). https://doi.org/10.1103/PhysRevX.6.021043
- W. Hoeffding, Probability Inequalities for Sums of Bounded Random Variables, J. Amer. Statist. Assoc. 58, 13–30 (1963). https://doi.org/10.1080/01621459.1963.10500830