PaperlayerView exact revision on arXiv

Source-linked AI summary

Qubit-reuse compilation with mid-circuit measurement and reset

Matthew DeCross, Eli Chertkov, Megan Kohagen, Michael Foss-Feig

arXiv:2210.08039v1quant-ph

TL;DR

Mid-circuit measurement and reset can reduce the number of qubits needed to execute quantum circuits, but automated qubit-reuse compilation has been lacking. This paper develops exact and greedy compilation methods based on causal structure. It compresses an 80-qubit QAOA circuit to 20 qubits for execution on Quantinuum H1-1, while the compressed circuit preserves measurement distributions rather than generally reproducing the original pre-measurement state for further quantum processing.

Abstract

from arXiv · show

A number of commercially available quantum computers, such as those based on trapped-ion or superconducting qubits, can now perform mid-circuit measurements and resets. In addition to being crucial for quantum error correction, this capability can help reduce the number of qubits needed to execute many types of quantum algorithms by measuring qubits as early as possible, resetting them, and reusing them elsewhere in the circuit. In this work, we introduce the idea of qubit-reuse compilation, which takes as input a quantum circuit and produces as output a compiled circuit that requires fewer qubits to execute due to qubit reuse. We present two algorithms for performing qubit-reuse compilation: an exact constraint programming optimization model and a greedy heuristic. We introduce the concept of dual circuits, obtained by exchanging state preparations with measurements and vice versa and reversing time, and show that optimal qubit-reuse compilation requires the same number of qubits to execute a circuit as its dual. We illustrate the performance of these algorithms on a variety of relevant near-term quantum circuits, such as one-dimensional and two-dimensional time-evolution circuits, and numerically benchmark their performance on the quantum adiabatic optimization algorithm (QAOA) applied to the MaxCut problem on random three-regular graphs. To demonstrate the practical benefit of these techniques, we experimentally realize an 80-qubit QAOA MaxCut circuit on the 20-qubit Quantinuum H1-1 trapped ion quantum processor using qubit-reuse compilation algorithms.

INTRODUCTION

Qubit reuse uses mid-circuit measurement and reset to reduce the qubits needed to execute circuits, but automating this compilation has been underexplored. The paper develops compilation methods based on causal structure and demonstrates their use on hardware.

INTRODUCTION

  • Qubit-reuse compilation converts a circuit into an equivalent circuit that uses fewer qubits by measuring, resetting, and reusing qubits.The compressed circuit produces the same measurement distribution as the original, though it does not generally reproduce the pre-measurement quantum state for further quantum processing.Source: INTRODUCTION · p. 1, QUBIT REUSE VIA MID-CIRCUIT MEASUREMENT · p. 2
  • The paper presents an exact CP-SAT method and a polynomial-scaling greedy heuristic for determining qubit-reuse measurement orders.The exact method does not scale well with qubit number, while the greedy heuristic runs quickly at large qubit counts.Source: INTRODUCTION · p. 1
  • An 80-qubit QAOA MaxCut circuit was compressed to 20 qubits and experimentally executed on Quantinuum H1-1.The processor is a trapped-ion quantum computer.Source: INTRODUCTION · p. 1

QUBIT REUSE VIA MID-CIRCUIT MEASUREMENT

  • Earlier qubit-reuse examples often relied on inspecting simple circuits; the proposed algorithms automate measurement ordering using causal cones.A qubit's state depends only on gates and qubits in its past causal cone, which can identify when it can be measured and reused.Source: QUBIT REUSE VIA MID-CIRCUIT MEASUREMENT · p. 2
  • On architectures without arbitrary-qubit interactions, the original and compressed circuits may need different numbers and placements of SWAP gates.The circuits contain the same set of gates only when the device supports fully connected interactions.Source: QUBIT REUSE VIA MID-CIRCUIT MEASUREMENT · p. 2

ALGORITHMS FOR OPTIMIZING QUBIT REUSE

The exact optimization model chooses a measurement order that minimizes the peak number of qubits needed during execution. Its constraints encode causal-cone dependencies and when qubits cease to be needed.

Exact Solution by Constraint Programming

  • CP-SAT can find globally optimal measurement orders, but its worst-case runtime is superpolynomial, making exact solutions suited to small circuits.The model uses binary variables and constraints to represent the measurement order and the qubits required over time.Source: Exact Solution by Constraint Programming · pp. 2–3
  • A qubit can be measured and reused when its required causal-cone operations have been executed, as illustrated by the circuit examples.Figure 1 depicts a one-qubit reduction; Figure 2 shows q2 measured and reset after gates among q1–q4, then reused as q5.Source: Figure 1 · p. 3, Figure 2 · p. 3
  • The CP-SAT model minimizes the maximum number of qubits required at any point in the circuit.Its constraints encode measurement order, causal-cone dependencies, and when measured qubits are no longer needed.Source: Exact Solution by Constraint Programming · pp. 3–4
  • The authors solve the model with Google OR-Tools CP-SAT and use its measurement-time variables to extract the prescribed qubit order.Depending on instance size, the solver typically either finds an exact solution or cannot find a feasible solution or improve on a hint within a reasonable time.Source: Exact Solution by Constraint Programming · p. 4

A Local Greedy Heuristic Algorithm

The greedy heuristic builds a measurement order by repeatedly selecting qubits whose causal cones add the fewest new input qubits. It addresses the poor scaling of the exact model, with an optional search over starting qubits to improve compression.

A Local Greedy Heuristic Algorithm

  • The CP-SAT model uses O(N^2) variables and O(N^4) constraints, becoming prohibitive in the N ≈ 100–1000 qubit regime.This motivates a heuristic that can produce useful approximate solutions in reasonable time.Source: A Local Greedy Heuristic Algorithm · p. 4
  • The heuristic first measures the qubit with the smallest causal cone, then repeatedly chooses one adding the fewest new input qubits.The procedure continues against the union of causal cones for qubits already measured.Source: A Local Greedy Heuristic Algorithm · p. 4
  • Searching all possible first qubits adds an O(N) runtime factor and significantly improves compression with a modest performance penalty.For each starting qubit, the heuristic constructs a full order and retains the one requiring the fewest total qubits.Source: A Local Greedy Heuristic Algorithm · p. 4

Dual Circuits

A dual circuit reverses time and exchanges state preparations with measurements. The paper relates compression of a circuit to compression of its dual, including an equality for the optimal qubit count.

Dual Circuits

  • A dual circuit is formed by replacing preparations with measurements and measurements with preparations, then reading the circuit in reverse.Measurements with discarded results include qubits traced out at the end of the circuit.Source: Dual Circuits · p. 4
  • Compression rearranges preparations later and measurements earlier, while preserving the order of operations with shared support.Each measurement may be connected to a later preparation to reduce the required qubit count.Source: Dual Circuits · pp. 4–5
  • Optimal qubit-reuse compression of a circuit and its dual always requires the same number of qubits.Figure 3 illustrates that the greedy heuristic can use four qubits on C but three on the dual-compression route.Source: Dual Circuits · p. 5, Figure 3 · p. 5
  • Because the greedy heuristic need not compress a circuit and its dual equally, the authors recommend applying it to both and selecting the better result.In the illustrated example, R(C) uses four qubits while the dual of R(C⋆) uses three.Source: Dual Circuits · p. 5, Figure 3 · p. 5

ANALYTIC RESULTS FOR QUBIT-REUSE COMPILATION

For structured circuits, analytical reuse orders can be optimal; 1D brickwork admits a linear measurement order using 4k qubits when 4k < N, independent of N.

ANALYTIC RESULTS FOR QUBIT-REUSE COMPILATION

  • Analytical measurement orders can outperform numerical approximations in some structured circuits; in several cases they match the greedy heuristic and are provably optimal.This establishes exactness of the heuristic for some practically relevant circuits and quantifies their compression scaling.Source: ANALYTIC RESULTS FOR QUBIT-REUSE… · p. 5

Local Brickwork Circuits in 1D

  • 4k qubits suffice for 1D brickwork circuits when 4k < N, using a linear measurement order that reuses measured outputs as later inputs.The optimal order may start at any qubit under periodic boundary conditions; without that symmetry, it starts at a chain edge.Source: Local Brickwork Circuits in 1D · pp. 5–6, Figure 4 · p. 6
  • Many 1D measurement orders achieve the same 4k-qubit requirement, but their choices trade off memory-error exposure against average qubit active time.The consequences of this trade-off are left for future study.Source: Local Brickwork Circuits in 1D · p. 6

Local Brickwork Circuits in 2D

In 2D brickwork circuits, causal-cone tiling yields optimal qubit reuse; the compiled-qubit count extends to rectangular lattices and cases where cones span a dimension.

Local Brickwork Circuits in 2D

  • The analysis states that circuits defined on O(N^d) qubits in d dimensions require O(N^(d−1)) qubits to execute.The 2D brickwork construction illustrates this reduction through causal-cone tiling.Source: Local Brickwork Circuits in 2D · pp. 6–7
  • Each output qubit’s causal cone contains 16k² inputs, and grouping qubits with shared or overlapping cones makes column-by-column greedy measurement optimal.The strategy measures blocks of four adjacent input qubits to tile successive columns.Source: Local Brickwork Circuits in 2D · p. 6, Figure 5 · p. 7
  • (4k−2)N+8k qubits are required for the tiled first column and the entire square-grid circuit when 4k < N.The square-grid analysis uses periodic boundary conditions and even N.Source: Local Brickwork Circuits in 2D · pp. 6–7
  • For rectangular Nx×Ny lattices, the compiled count is (4k−2) min(Nx, Ny)+8k when 4k < min(Nx, Ny), NxNy when 4k > max(Nx, Ny), and 4k min(Nx, Ny) otherwise.Choosing the shorter dimension first minimizes overhead; the piecewise count also covers cones that span one or more dimensions.Source: Local Brickwork Circuits in 2D · p. 7

Matrix Product State Preparation (MPS)

Qubit reuse exploits the sequential structure of tensor-network circuits to reduce the physical qubits needed to sample their outputs. The required count is explicit for MPS and binary TTN preparation.

Matrix Product State Preparation (MPS)

Tree Tensor Networks (TTN)

  • A depth-D binary TTN output can be sampled using D + 1 qubits, by reusing the same qubits to sample each depth-D subtree in turn.For classical product-state inputs, the dual TTN classifier can also be executed using D + 1 qubits.Source: Tree Tensor Networks (TTN) · pp. 8–9

Multiscale Entanglement Renormalization Ansatz (MERA)

These structured circuits can be sampled with qubit reuse by following their causal cones and recycling measured qubits. The required resources are bounded for MERA and QCNN circuits, while Bernstein–Vazirani needs only two physical qubits.

Multiscale Entanglement Renormalization Ansatz (MERA)

  • For open-boundary MERA, measuring outputs greedily from left to right achieves the optimal 2D−1-qubit requirement for sampling the full output.The method uses overlapping causal cones and a reuse queue; near the right boundary, fewer qubits may be needed.Source: Multiscale Entanglement… · p. 9

Quantum Convolutional Neural Networks (QCNN)

  • With product-state inputs, the QCNN construction described is dual to the corresponding MERA and can be executed using 2D−1 qubits in the worst case.For quantum-data inputs, achievable compression depends on the input state's entanglement structure.Source: Quantum Convolutional Neural Networks… · pp. 9–10

Bernstein-Vazirani Algorithm

  • The Bernstein–Vazirani algorithm can run on two physical qubits for any register size: one persistent ancilla and one repeatedly measured and reused register qubit.This follows because each register qubit interacts only with itself and the shared ancilla in the stated oracle realization.Source: Bernstein-Vazirani Algorithm · p. 11
  • Across the analytically treated circuits, compiled qubit counts scale parametrically below those of the original circuits.The section summarizes these structured-circuit results in Table I.Source: Bernstein-Vazirani Algorithm · p. 11, Table I · p. 11

NUMERICAL EXPERIMENTS AND BENCHMARKING

The benchmarks study qubit-reuse compilation for QAOA MaxCut on random unweighted three-regular graphs, comparing exact CP-SAT and greedy heuristics across circuit sizes and depths. The enhanced greedy heuristic improves compression at moderate scale, while deeper circuits offer little savings.

NUMERICAL EXPERIMENTS AND BENCHMARKING

EXPERIMENTAL DEMONSTRATION

The experiment used qubit reuse to run an 80-qubit, p=1 QAOA MaxCut optimization on Quantinuum H1-1 with 20 qubits. For random U3R instances, circuits averaged 21.1 ± 1.5 qubits, and the run’s best cut was 101 against an exact value of 110.

EXPERIMENTAL DEMONSTRATION

  • Across 1,000 random U3R N=80, p=1 instances, reuse required 21.1 ± 1.5 qubits on average, with 32% at 20 or fewer.The first sampled graph compressed to the H1-1 limit of twenty qubits.Source: EXPERIMENTAL DEMONSTRATION · p. 14, Figure 20 · p. 14
  • The optimizer ran 78 circuits before meeting its convergence criterion, with 100 shots per circuit and roughly three minutes of machine time per circuit.The shot count was selected in simulation to balance measuring objective decreases against feasible machine time.Source: EXPERIMENTAL DEMONSTRATION · p. 14
  • After brief exploration, the optimizer converged rapidly around the tenth circuit; later circuits supplied additional samples at near-optimal parameters.The trajectory is overlaid on noiseless and noisy energy landscapes, each generated from 900 simulations.Source: EXPERIMENTAL DEMONSTRATION · p. 15, Figure 24 · p. 16
  • The QAOA run’s best cut was 101 (91.8% of exact 110), versus the Goemans–Williamson algorithm’s cut 104 (94.5% approximation ratio).The QAOA run took about eleven hours on H1-1; the exact classical solver took 0.12 seconds on a laptop.Source: EXPERIMENTAL DEMONSTRATION · p. 15
  • The cut-value distribution was narrow: the best observed cut, 101, was slightly above the average expected result, while 98 was the most likely cut.The figure uses best-shot cut values from 100 circuits with 5,000 shots each as a proxy for the full optimization procedure.Source: EXPERIMENTAL DEMONSTRATION · p. 15

DISCUSSION

Qubit-reuse compilation reduces the qubit count using mid-circuit measurements and resets, and the paper demonstrates an 80-qubit QAOA instance running on 20 qubits. The discussion notes depth and memory-error trade-offs, explains sampling equivalence, and identifies further reductions and circuit-ordering opportunities.

DISCUSSION

  • The full N=80, p=1 MaxCut QAOA optimization was experimentally run on Quantinuum H1-1 using 20 qubits.The method compiles circuits to use fewer qubits via mid-circuit measurements and resets.Source: DISCUSSION · p. 16
  • Reuse preserves gate count, so compression generally increases circuit depth and may expose qubits to more memory errors before measurement.The paper recommends compressing only to the qubit count required by the target device.Source: DISCUSSION · p. 16
  • In the absence of errors, the compressed circuit samples from the original circuit’s measurement distribution, although it does not implement the same overall operator.The argument relies on completing each measured qubit’s causal cone before measuring and reusing it.Source: DISCUSSION · p. 16
  • When only a few output-qubit correlations are needed, compiling just their causal cones may reduce the required qubit count further.The same qubit-reuse algorithms can be applied to this restricted circuit.Source: DISCUSSION · p. 16
  • For commuting ZZ gates, edge coloring gives a layering with at most one more layer than the interaction graph’s maximum degree; preliminary study suggests this can improve reuse compression.The paper says the broader effects of circuit depth and gate ordering merit further study.Source: DISCUSSION · p. 17

Constraints in the CP-SAT Model

The CP-SAT model and its constraints are used by the exact qubit-reuse algorithm; their numbering corresponds to the main text’s verbal constraint descriptions.

Constraints in the CP-SAT Model

Loading 2210.08039v1…