Fast quantum circuit cutting with randomized measurements

1 Introduction

• Direct quantum execution is limited by available qubit counts, while classical simulation is believed to scale exponentially without favorable circuit structure.The paper motivates a hybrid approach using results from smaller quantum devices for estimation.Source: §1 · p. 1
• The method offers a quadratic overhead improvement over single-qubit Pauli-measurement cutting in certain cases, approximately doubling cut capacity at fixed runtime.The paper also derives an information-theoretic lower bound, making its overhead at most roughly quadratically worse than the best possible wire-cutting method.Source: §1 · p. 2
• Randomized measure-and-prepare channels make the post-measurement state separable across devices, with unitary 2-design measurements targeting MPS-like entanglement.The approach uses repeated mid-circuit measurements to classically simulate entanglement between qudits.Source: §1 · p. 2
• When the subcircuits’ communication graph contains a cycle, the method requires multiple spatially separated circuits rather than repeated execution on one device.The single-device repeated-execution option is described for circuits with an MPS-like structure.Source: §1 · p. 2
• With a small balanced vertex separator, p-layer QAOA circuits can be hybrid-simulated efficiently up to p = O(log n), and combined subcircuit outcomes can sample optimal-solution bitstrings.The paper presents this as addressing an open partitioning problem from Ref..Source: §1 · pp. 2–3
• Numerical experiments report practical speedups over the procedure in on small QAOA instances.The experiments use open-source circuit-cutting functionality in PennyLane.Source: §1 · p. 3
• Using fragments of at most 30 qubits, the authors evaluate a 129-qubit, two-layer QAOA variational energy and optimize 62-qubit, one- and two-layer circuits.The fragments run on a cluster of NVIDIA A100 40GB GPUs as simulator substitutes for quantum devices.Source: §1 · p. 3

• Randomized rank-1 POVM measurements followed by preparing the observed outcome define a measure-and-prepare channel used in the wire-cutting scheme.The channel uses a random unitary forming a unitary 2-design; the second channel considered is completely depolarizing.Source: §2 · p. 4
• O(4^k(m+k^2)/ε^2) time suffices to simulate a circuit split across overlapping qubit sets using a device with at most max{|A|, |B|} qubits.The sets overlap on at most k qubits, and the simulation is accurate to ε.Source: §2 · p. 4
• The runtime comparison assumes a device limited to n/2+k qubits and, for gate-cutting methods, cut qubits participating in at most D multi-qubit gates.Source: §2 · p. 5, Table 1 · p. 5
• Ω(2^k/ε^2) is a worst-case overhead lower bound for any procedure that bipartitions a circuit through wire cutting.Source: §2 · p. 5
• Repeated applications of the identity can cut multiple subsets of parallel wires, producing r disconnected sub-circuits executable on r devices.Each subset contains k_j wires; the cuts separate the original circuit into fragments.Source: §2 · pp. 5–6
• Overhead is comparatively large when every cut subset contains one wire, and cyclic communication graphs require classical communication between separate devices.Cycles can also prevent recycling qubits on one device between circuit fragments.Source: §2 · p. 6, Figure 2 · p. 6

3.1 Structure of QAOA circuits for circuit cutting

• Commuting edge-based ZZ rotations let the cost-unitary gates be ordered by partition, while a balanced vertex separator identifies cuts that divide the graph into roughly equal components.For clustered graphs, the separator size determines the number of cuts and the expectation-value overhead grows exponentially with that size.Source: §3.1 · p. 7
• With a known balanced vertex separator of size κ, p-layer Max-Cut QAOA can be simulated within accuracy ε using two non-entangled devices with n − Ω(n) qubits in time e^O(2^αpκ/ε²).The result gives sufficient conditions for efficient hybrid simulation when the graph has a small balanced separator.Source: §3.1 · p. 7
• When the minimum balanced separator is not known, a polynomial-time algorithm approximates it within O(√log κ), with the overhead theorem's exponent affected by that factor.Finding the minimal balanced vertex separator is NP-hard.Source: §3.1 · p. 7

3.2 Sampling from cut circuits

• The cutting analysis also supports sampling a bit string with cost at least μ, with expected waiting time that grows exponentially in the number of cut wires.The authors note that this sampling task had not been addressed in prior circuit-cutting work known to them.Source: §3.2 · p. 8

3.3 Numerical comparison for circuit bipartitions

• The randomized method converges faster and is more accurate than Pauli-based cutting across all tested graph sizes, cut sizes, and QAOA depths.At larger cut sizes and p = 2, it gives reliable cost estimates at 10^6 shots, while the Pauli method's standard deviations remain larger than the target interval.Source: §3.3 · p. 9, Figure 4 · p. 9

3.4 Large-scale simulations

• At p = 2, n = 25, and k = 1, the 77-, 103-, and 129-qubit circuits required 1,812, 3,540, and 5,268 fragments, respectively.The simulations used a cluster of GPU-based simulators; the 129-qubit circuit was evaluated using circuit cutting.Source: §3.4 · p. 10
• For the 62-qubit optimization, p = 1 reached the analytic optimal cost, while p = 2 produced a decreasing cost function that tended toward −0.51.No analytic global minimum was known for p = 2; the reported p = 1 optimal cost was −33.8.Source: §3.4 · p. 10

4 Conclusion and outlook

• Randomized-measurement circuit cutting provides a quadratic runtime improvement over the state of the art when multiple neighbouring wires are cut simultaneously.The method requires classical communication to coordinate measurements and preparations; general circuits require executions across multiple spatially separated devices.Source: §4 · p. 11
• The information-theoretic lower bound is quadratically lower than the method’s overhead, and whether it is achievable or can be tightened remains open.The authors present this as an open question for further improvement.Source: §4 · p. 11
• For p = 1, the 62-qubit optimization reached the global minimum of −33.8 in around 30 minutes; for p = 2, it took around 12 hours and reached a local minimum.The p = 2 result may improve with a careful choice of initial circuit parameters [38].Source: Figure 7 · p. 11
• The QAOA testbed includes an algorithm for randomized measure-and-prepare channels and a sampling procedure for cut circuits, with simulations indicating a large speedup over prior circuit-cutting work.The authors state that prior work focused on estimating expectation values rather than sampling cut circuits.Source: §4 · p. 11
• 129-qubit QAOA forward passes and full 62-qubit optimizations were demonstrated using GPUs as proxies for roughly 30-qubit devices.The authors report that the implementation enables small-scale devices to emulate results from larger circuits.Source: §4 · p. 11

A Preliminaries

• L(C^d) denotes square linear operators, H(C^d) the Hermitian operators, Psd(C^d) the positive semidefinite operators, and D(C^d) the unit-trace quantum states.U(C^d) denotes unitary operators, while S(C^d) denotes unit-norm vectors representing pure states.Source: A Preliminaries · p. 16
• The main theorem uses structured POVMs based on unitary 2-designs; for discrete designs, the ensemble pairs each unitary with its probability.Tr_j denotes the partial trace over the jth space, and Tr_S traces out the spaces corresponding to a set of qubits.Source: A Preliminaries · p. 16
• A unitary t-design is introduced as a random unitary U in U(C^d) satisfying a condition for every X in L(C^d)⊗t.The supplied definition also specifies that t and d are positive integers.Source: A Preliminaries · p. 16

B.1 Proof of Lemma 2.1

• The lemma defines a Bernoulli variable z that equals 1 with probability d/(2d + 1).The lemma concerns channels Ψ0 and Ψ1 acting on d-dimensional states.Source: §B.1 · p. 16
• The proof invokes the unitary 2-design assumption to evaluate an average involving a state vector and uses a swap-operator identity in its derivation.The text identifies W as the swap operator and cites the Haar-integral identity as.Source: §B.1 · p. 17
• Ψ0(X) equals [d Ψ1(X) + X] divided by d + 1 for every X in L(C^d).The passage identifies Ψ1(X) as Tr(X)1/d.Source: §B.1 · p. 17

B.2 Bipartitioning pseudocode

• The circuit C consists of sub-circuits C_A and C_B acting on wire sets A and B, with |A ∩ B| = k.The goal is to estimate Tr(O_f N(ρ^⊗n)).Source: §B.2 · p. 17
• For a function f mapping n-bit strings to [−1, 1], O_f is the diagonal observable whose entries are f(x).N denotes the channel implemented by the overall circuit.Source: §B.2 · p. 17
• The setup assumes A ∪ B = [n] for simplicity.Source: §B.2 · p. 17

B.3 Proof of Theorem 2.2

• O(4^k(m + k^2)/ε^2) time suffices to simulate a size-m circuit with overlap at most k on at most max{|A|, |B|} qubits.Theorem 2.2 states this bound for accuracy ε.Source: §B.3 · p. 17
• O(4^k/ε^2) iterations suffice because the estimator is bounded and Hoeffding’s inequality bounds the sample mean’s error.Each iteration takes O(m + k^2) time, including randomized Clifford sampling and reinitializing the device between circuit fragments.Source: §B.3 · p. 18
• Random Clifford operators implement one channel in the cutting procedure, while a second channel is implemented by measurement and conditional state preparation.The proof uses the random Cliffords’ 3-design property to justify the first channel.Source: §B.3 · p. 18

C An information-theoretic lower bound

• A successful wire-cutting procedure measures register B, prepares a state conditioned on the outcome, applies U2, and estimates an expectation using N independent samples.The procedure is defined for an unknown state ρ ⊗ σ and a fixed measurement strategy on B.Source: C An information-theoretic lower bound · p. 19
• The lower bound reduces estimation to distinguishing two states, with the required iterations bounded by the information gained from each measurement.The argument considers a single non-trivial register and repeats the measurement-and-prepare procedure on identical copies.Source: C An information-theoretic lower bound · pp. 19–20
• Ω(2^k/ε^2) iterations are necessary for a system of k qubits under the stated wire-cutting criteria.The proof uses mutual information and data-processing bounds to constrain information gained from measurement outcomes.Source: C An information-theoretic lower bound · pp. 20–22

D Proof of Theorem 3.1

• A known 2/3-balanced separator of size κ≤n/6 lets a p-layer Max-Cut QAOA circuit run on two non-entangled devices, each using at most 5n/6 qubits.The theorem’s simulation time is specified in its full statement.Source: D Proof of Theorem 3.1 · p. 23
• A single-layer partition yields fragments supported on the partition’s vertex sets, and extending it to p layers requires at most 2p−1 sets of κ parallel-wire cuts.The proof orders two-qubit gates to respect the edge partition, making wires between edge sets parallel.Source: D Proof of Theorem 3.1 · pp. 22–24
• The expected cost is estimated using randomized channels on the cut-wire groups, with at most 4^(2p−1)(κ+2)/ε^2 repetitions sufficient for additive error ε.The estimator is bounded in magnitude by (2^(κ+1)+1)^(2p−1).Source: D Proof of Theorem 3.1 · p. 24

E Circuit cutting complexity for QAOA with clustered graphs

• N(p, r, k) = 3pk4^(p−1)k + (r−2)12^(2p−1)k + 3(p−1)k4^pk gives the number of unique sub-circuits for p layers, r clusters, and k vertex separators.The formula is presented for a clustered problem graph with n nodes in each cluster.Source: E Circuit cutting complexity for QAOA… · p. 24
• Each fragment requires at most m = n + (3p−1)k qubits, including auxiliary qubits from mid-circuit measurements.The stated GPU-per-fragment target is m≤30.Source: E Circuit cutting complexity for QAOA… · p. 24
• Figure 9 plots execution time and relative speed-up against GPU-node count for a 79-qubit QAOA circuit and shows divergence from ideal strong scaling at large node counts.The plotted setup fixes p=1, r=3, n=25, and k=2.Source: Figure 9 · p. 25

F Analyzing the efficiency of simulated circuit cutting

• The appendix varies classical resources to examine circuit-cutting runtime for the problem graphs introduced in Section 3.1.Source: F Analyzing the efficiency of… · p. 25
• Approximately 15× speed-up was reached using 32 GPU nodes, with approximately 47% efficiency at the largest scale evaluation.The evaluation parallelized execution of the N circuit fragments.Source: F Analyzing the efficiency of… · p. 25
• Scheduling, transmission, device setup, and serial execution contribute to inefficiencies as GPU-node count increases.The passage says these overheads are expected to increase with additional GPU nodes.Source: F Analyzing the efficiency of… · p. 25