1. Bibliographic Information

• Title: CaQR: A Compiler-Assisted Approach for Qubit Reuse through Dynamic Circuit
• Authors: Fei Hua, Yuwei Jin, Yanhao Chen, Suhas Vittal, Kevin Krsulich, Lev S. Bishop, John Lapeyre, Ali Javadi-Abhari, and Eddy Z. Zhang.
• Affiliations: The authors are from Rutgers University, Georgia Institute of Technology, and IBM T. J. Watson Research Center. The collaboration between academia and a leading quantum hardware company (IBM) suggests that the research is both academically rigorous and grounded in practical hardware realities.
• Journal/Conference: The paper was published in the Proceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 3 (ASPLOS '23). ASPLOS is a premier conference in computer architecture, known for its high standards and focus on the intersection of hardware, software, and systems. Its inclusion in this venue highlights the growing importance of quantum computer architecture and compiler design.
• Publication Year: 2023
• Abstract: The paper introduces CaQR, a compiler-assisted tool that leverages new hardware support for dynamic circuits—specifically mid-circuit measurement and reset—to enable qubit reuse. By automatically identifying opportunities to reuse qubits, CaQR can reduce the number of qubits required for a given quantum application. The tool analyzes the complex trade-offs between qubit savings, circuit fidelity, gate count, and circuit duration. Experiments on real IBM quantum hardware with benchmark applications like Bernstein-Vazirani show resource reductions of up to 80% and fidelity improvements up to 20%, demonstrating the practical benefits of this approach.
• Original Source Link: /files/papers/68f72d43b5728723472281bd/paper.pdf. The paper is a formally published conference paper.

2. Executive Summary

• Background & Motivation (Why):

  • Core Problem: The number of available qubits is a primary bottleneck for current and near-term quantum computers. The limited scale of these devices restricts the size and complexity of problems that can be solved.
  • Importance & Gap: Historically, all quantum measurements had to be performed at the end of a circuit's execution. However, recent hardware advancements, particularly from IBM, have introduced support for dynamic circuits, which allow for mid-circuit measurement and reset. This feature enables a qubit to be measured, reset to its initial state ($|0>$), and then reused for subsequent operations within the same circuit. While this capability exists, there was a lack of automated compiler tools to systematically identify and exploit these reuse opportunities. Manually transforming circuits is tedious, error-prone, and not scalable.
  • Innovation: This paper introduces a compiler-assisted approach, CaQR, to automatically transform quantum circuits to take advantage of qubit reuse. CaQR is novel because it explores the full trade-off space, considering not just qubit savings but also the impact on circuit fidelity (by avoiding noisy qubits), SWAP gate count (by improving qubit mapping), and overall circuit duration.

• Main Contributions / Findings (What):

  • A Compiler-Assisted Tool (CaQR): The paper presents a fully automated tool that identifies valid qubit reuse opportunities in general quantum applications and transforms the circuit accordingly.
  • Comprehensive Trade-off Analysis: The work discovers and analyzes the complex interplay between qubit reuse and other critical performance metrics. It reveals that qubit reuse can, counter-intuitively, sometimes reduce circuit duration by minimizing the need for costly SWAP gates and by allowing the compiler to avoid faulty hardware components.
  • Two Optimization Strategies: CaQR is implemented in two distinct versions to target different optimization goals:
    1. QS-CaQR (Qubit Saving CaQR): Prioritizes reducing the qubit count to a user-specified budget, exploring the trade-off between savings and circuit depth.
    2. SR-CaQR (SWAP Reduction CaQR): Prioritizes reducing SWAP gates and improving fidelity, using qubit reuse as a means to achieve better qubit-to-hardware mapping, particularly when qubit count is not the primary constraint.
  • Significant Empirical Improvements: The authors demonstrate the effectiveness of CaQR through extensive experiments on simulators and real IBM quantum hardware. They report qubit usage reductions up to 80%, SWAP gate reductions, and fidelity improvements up to 20% on various benchmarks, proving the practical value of their approach.

3. Prerequisite Knowledge & Related Work

• Foundational Concepts:

  • Qubit: The fundamental unit of quantum information. Unlike a classical bit (0 or 1), a qubit can exist in a superposition of both states simultaneously.

  • Quantum Circuit: A sequence of quantum gates (operations) applied to a set of qubits to perform a computation. It is typically visualized as a diagram where horizontal lines represent qubits and blocks represent gates.

  • Quantum Measurement: The process of extracting a classical outcome (0 or 1) from a qubit. This action collapses the qubit's quantum state.

  • Dynamic Circuits: Quantum circuits that incorporate classical control flow conditioned on the results of mid-circuit measurements. This allows the circuit's subsequent operations to change based on intermediate outcomes, a feature not available in traditional "static" circuits where all measurements occur at the end.

  • Mid-circuit Measurement and Reset: A key feature of dynamic circuits. A qubit can be measured partway through the computation, and a reset operation can force its state back to the ground state ($|0>$), making it available for new, independent computations. The authors improve upon the standard implementation by using a measurement followed by a classically controlled X-gate (a NOT gate), which is about twice as fast.

    Image 11: A comparison of two methods for measurement and reset. (a) The built-in Qiskit operations. (b) The authors' more efficient implementation using a classically-controlled gate, which halves the execution time.

  • SWAP Gate: A three-CNOT-gate operation that swaps the states of two qubits. It is necessary when a two-qubit gate must be applied between logical qubits that are mapped to non-adjacent physical qubits on the hardware. SWAP gates are a major source of error and significantly increase circuit duration.

  • Circuit Depth/Duration: A measure of the longest path of dependent gates in a circuit, representing the total time of the computation. Longer circuits suffer more from decoherence, where qubits lose their quantum information due to environmental noise.

  • Fidelity: A metric indicating how closely the experimental output distribution from a real quantum computer matches the theoretically perfect output distribution. Higher fidelity means a more accurate computation.

  • Qubit Interaction Graph: A graph where nodes are the logical qubits in an algorithm and an edge connects two nodes if a two-qubit gate is applied between them.

  • Hardware Coupling Graph: A graph representing the physical connectivity of qubits on a quantum chip. A two-qubit gate can only be directly applied between physically connected qubits.

  • Bernstein-Vazirani (BV) Algorithm: A quantum algorithm that demonstrates a speedup over classical algorithms for a specific problem. It is a common benchmark for evaluating quantum hardware and compilers.

  • QAOA (Quantum Approximate Optimization Algorithm): A popular hybrid quantum-classical algorithm for finding approximate solutions to optimization problems. Its quantum circuits often contain layers of commuting gates, providing flexibility for compilation.

• Previous Works:

  • CutQC: A technique that partitions a large quantum circuit into smaller sub-circuits that can run on smaller devices. Its drawback is the need for classical post-processing that can be exponentially costly. CaQR operates within a single circuit without this overhead.
  • Ancilla Qubit Reuse: Prior methods for reusing ancilla (helper) qubits often require un-computation—running a portion of the circuit in reverse to disentangle the ancilla qubit before reuse. This adds significant gate overhead.
  • Square framework: Explores the trade-off between un-computation cost and qubit savings for ancilla reuse.

• Differentiation: CaQR is distinct from these prior works because:

  1. It leverages mid-circuit measurement and reset, a new hardware feature, and does not require costly un-computation.
  2. It can reuse any qubit (ancilla or data), not just designated ancilla qubits.
  3. It provides a general, automated framework for finding and exploiting reuse opportunities in arbitrary applications, balancing multiple performance objectives.

4. Methodology (Core Technology & Implementation)

The core of CaQR is its ability to identify valid qubit reuse pairs and transform the circuit while optimizing for specific goals.

• Principles: Qubit Reuse Conditions For a logical qubit qi to be reused for the operations of another logical qubit qj (denoted $qi -> qj$), two conditions must be met:

  1. Condition 1 (No Interaction): There must not be any two-qubit gate directly connecting qi and qj in the original circuit. If they interact, their operations cannot be fully separated in time.

  2. Condition 2 (No Cyclic Dependency): Reusing qi for qj means all operations on qi must finish before any operations on qj begin. This introduces a new dependency. This new dependency must not create a cycle in the circuit's overall dependency graph. For example, if an operation on qi depends on an operation on qj, then qi cannot be reused for qj.

     Image 18: An illustration of an invalid reuse pair due to Condition 2. Reusing $q1$ for $q4$ (b) would require $g(q3, q1)$ to run before $g(q4, q2)$. However, the original circuit (a) has a dependency path from $g(q4, q2)$ to $g(q3, q1)$, creating a cycle.

CaQR is offered in two versions, QS-CaQR and SR-CaQR.

QS-CaQR: Targeting Qubit Saving

This version aims to compile a circuit using a specific, reduced number of qubits.

• For Regular Applications (with fixed gate dependencies):

  1. DAG Construction: The circuit is first represented as a Directed Acyclic Graph (DAG), where nodes are gates and edges represent dependencies.

  2. Candidate Identification: The tool identifies all potential reuse pairs $(qi -> qj)$ that satisfy Conditions 1 and 2.

  3. Iterative Reduction: To reach a target qubit count, QS-CaQR iteratively saves one qubit at a time. In each step, it evaluates all valid single-qubit reuse opportunities. For each possibility, it calculates the resulting circuit depth by adding a "measurement-reset" dependency to the DAG.

  4. Optimal Choice: It selects the reuse pair that causes the minimum increase in the critical path length (circuit depth) and applies the transformation. This process is repeated until the user's qubit budget is met or no more reuse is possible.

     Image 3: The DAG for the BV circuit (a). To reuse $q1$ for $q3$ and then $q3$ for $q4$, new dependency nodes (D1, D2) are added to the DAG to enforce the execution order (b).

• For Applications with Commutable Gates (e.g., QAOA): The lack of a fixed gate order provides more flexibility.

  1. Finding Minimal Qubits: The theoretical minimum number of qubits can be found by constructing the qubit interaction graph and solving the graph coloring problem. Qubits assigned the same color can potentially be mapped to the same physical qubit because they do not interact directly.
  2. Handling Commutativity: To evaluate a reuse pair $(qi -> qj)$, QS-CaQR imposes a dependency: all gates involving qi must execute before all gates involving qj.
  3. Evaluating a Reuse Pair: A three-step scheduling algorithm estimates the resulting circuit depth:

     • Step 1: Update a dependency graph $G_D$ with the new ordering constraint from the reuse pair.

     • Step 2: From the set of gates ready to be scheduled (the "frontier"), assign higher weights to gates that will unblock future dependent gates.

     • Step 3: Use a maximum weight perfect matching algorithm on the qubit interaction graph G_int to select the largest possible set of non-conflicting gates to schedule in parallel. This step is repeated until all gates are scheduled. The number of iterations gives the circuit depth.

       Image 5: An illustration of the scheduling process for a QAOA circuit. After imposing a reuse dependency (a), the algorithm uses matching to schedule gates in parallel across multiple iterations (b) to minimize depth.

SR-CaQR: Targeting SWAP Reduction and Improved Fidelity

This version assumes sufficient qubits are available and uses reuse to minimize SWAP gates and avoid noisy hardware.

• Core Idea: Delay the execution of gates that are not on the critical path. This keeps logical qubits "unmapped" for longer, providing more flexibility. When a gate needs to be executed, its logical qubits can be mapped to a wider selection of available physical qubits—including both fresh qubits and ones that have been freed up by reuse. This increases the chance of finding an adjacent pair of physical qubits, avoiding a SWAP.

• For Regular Applications:

  1. The compiler processes the circuit's DAG layer by layer.

  2. It prioritizes scheduling gates on the critical path. Gates off the critical path are delayed.

  3. When mapping a logical qubit, it chooses an available physical qubit (from a list of fresh and reused qubits) that minimizes future communication costs (i.e., potential SWAPs) and has better fidelity characteristics.

  4. Once a logical qubit's operations are all completed, its physical qubit is measured, reset, and added back to the list of available physical qubits.

     Image 6: An example flow of SR-CaQR. Gates are strategically delayed and qubits are mapped to optimize connectivity. For instance, $q0$ is freed after $g2$ is executed and its physical location can be reused later.

• For Applications with Commutable Gates:

  1. First, QS-CaQR is used to find a "sweet spot" of reuse pairs to create a partial dependency structure.
  2. Gates involved in these initial dependencies are scheduled first.
  3. Other gates, especially those involving low-degree qubits in the QAOA graph, are delayed.
  4. The rest of the compilation proceeds similarly to the regular application case, mapping qubits dynamically to minimize SWAPs and considering hardware error rates.

• Overhead Analysis: The time complexity of both methods for general circuits is given as $O(kn^3)$, where $k$ is the number of qubits and $n$ is the number of gates. For QAOA benchmarks, which use a more complex matching algorithm (Edmonds' Blossom), the complexity is $O(k^3 n^4)$. The authors note that a faster, approximate greedy algorithm could be used in practice.

5. Experimental Setup

• Datasets/Benchmarks:
  • Regular Applications: A standard set of benchmarks including Rd-32, 4mod5, $Multiply_13$, $System_19$, $CC_10$, $XOR_5$, and $BV_10$.
  • Commutable-Gate Applications: QAOA for the max-cut problem on two types of graphs (random and power-law) with sizes ranging from 16 to 128 qubits.
• Evaluation Metrics:
  1. Qubit Usage: The number of physical qubits required.
  2. Two-qubit gate count: The total count of two-qubit gates, which is heavily influenced by the number of inserted SWAP gates.
  3. Circuit Depth/Duration: The number of time steps required for execution. Measured in dt (device-specific time unit), where 1 dt = 0.22 ns on the IBM Mumbai machine.
  4. Total Variation Distance (TVD): A measure of the statistical distance between two probability distributions. Here, it compares the ideal output distribution of a circuit with the one measured from noisy hardware. A lower TVD indicates higher fidelity.
     • Conceptual Definition: TVD measures the total difference between the probabilities of all possible outcomes. A value of 0 means the distributions are identical, while a value of 1 means they are completely disjoint.
     • Mathematical Formula: For a measured distribution $P_{meas}$ and an ideal distribution $P_{ideal}$: $$\mathrm{TVD}(P_{meas}, P_{ideal}) = \frac{1}{2} \sum_{i} |P_{meas}(i) - P_{ideal}(i)|$$
     • Symbol Explanation:
       • $i$: An index over all possible computational basis states (outcomes).
       • $P_{meas}(i)$: The measured probability of outcome $i$.
       • $P_{ideal}(i)$: The theoretically calculated probability of outcome $i$.
• Baselines:
  • The primary baseline is IBM Qiskit's transpiler at optimization level 3, which is a state-of-the-art, highly aggressive compilation pipeline.
• Hardware:
  • Simulations were performed on models of IBM's heavy-hex architecture.
  • Real-machine experiments were run on IBM Mumbai, a device that supports dynamic circuits.

6. Results & Analysis

• Core Results:

  • QS-CaQR Evaluation:

    • Regular Applications: Figure 13 shows that for logical circuits, depth always increases as qubits are reused. However, for the final compiled circuit (after SWAP insertion), moderate qubit saving often decreases the depth. This is because the reduced qubit count leads to a more compact qubit interaction graph, which requires fewer SWAPs and can be mapped more efficiently to the hardware. Extreme reuse, however, leads to high serialization and increases depth. This reveals a "sweet spot" for qubit saving.

      Image 7: QS-CaQR results for regular circuits. The depth of the final compiled circuit (left side of each plot) often decreases with moderate qubit reuse before increasing with aggressive reuse.

    • QAOA Applications: QAOA circuits show massive potential for reuse, with qubit savings of over 80% possible while only incurring a small increase in circuit depth (Figure 14). Power-law graphs are particularly amenable to this, as they have many low-degree nodes whose corresponding qubits are idle for long periods and can be easily reused.

      Image 8: QS-CaQR results for QAOA logical circuits, showing significant qubit savings are possible with a modest increase in depth, especially for power-law graphs.

    • Tradeoff Analysis: The following manually transcribed table (from Table 1 in the paper) shows a detailed comparison. The "Ours with Minimal Depth" version of QS-CaQR often achieves a better result than the baseline, reducing both qubit count and circuit duration simultaneously.

      Manual Transcription of Table 1: QS-CaQR Version Comparison The unit of circuit duration is dt (system cycles), where 1 dt is 0.22 nano-seconds.

      Benchmarks	Baseline (No Reuse)				Ours with Maximal Reuse				Ours with Minimal Depth
      	Qubit	Depth	2Q-Gates	Duration	Qubit	Depth	2Q-Gates	Duration	Qubit	Depth	2Q-Gates	Duration
      Rd-32	32	289	289	38780	18	273	290	39281	30	284	284	38180
      4mod5	5	47	32	3696	3	61	29	4972	4	39	24	3176
      Multiply_13	13	220	210	29124	8	260	209	34888	11	193	178	25700
      System_9	9	143	121	17892	6	171	121	22548	7	126	102	15992
      CC_10	10	82	90	12420	5	106	89	15688	9	76	82	11376
      XOR_5	5	18	14	1864	3	22	14	2428	4	15	11	1588
      BV_10	10	17	24	3468	2	48	24	7956	3	31	21	5500

  • SR-CaQR Evaluation: The following transcription of Table 2 shows that SR-CaQR consistently finds solutions with equal or fewer SWAP gates compared to the best version of QS-CaQR, confirming its strength in SWAP optimization. For larger circuits ($System_9$, QAOA-16-0.3), the reduction is more pronounced.

    Manual Transcription of Table 2: SWAP Gate Comparison

    	QS-CaQR (min SWAP version)			SR-CaQR
    Benchmarks	SWAP	Qubit	Duration	SWAP	Qubit	Duration
    4mod5	0	4	3176	0	4	3176
    System_9	39	9	21160	31	9	20468
    QAOA-10-0.3	2	8	3344	2	8	3344
    QAOA-16-0.3	17	14	7172	14	14	6744

  • Real Machine Experiments:

    • Fidelity Improvement: The BV experiment on IBM Mumbai is a powerful demonstration. The baseline 5-qubit circuit (requiring a SWAP and using a noisy qubit Q23) achieved a 55% success rate. By reusing a qubit, the 4-qubit version avoided the noisy qubit and the SWAP, improving the success rate to 58%. The 3-qubit version further improved this to 64% by using only the most reliable qubits and links. This shows that less is more: using fewer, better qubits can yield superior results.

      Image 17: Results for the BV algorithm on real hardware. The success probability (finding the correct answer '111...1') increases from 55% (5 qubits) to 58% (4 qubits) to 64% (3 qubits) by strategically reusing qubits to avoid noise and SWAPs.

    • TVD and QAOA: Table 3 (transcribed below) shows that SR-CaQR improves the TVD on all tested benchmarks. For QAOA, the optimized circuits converge to a better solution (higher expectation value), indicating that the computation is more accurate.

      Manual Transcription of Table 3: Real Machine Results on IBM Mumbai

      	Baseline			SR-CaQR
      Benchmarks	TVD	2Q-Gates	Duration	TVD	2Q-Gates	Duration
      BV_5	0.142	5	1348	0.125	4	1268
      BV_10	0.298	24	3468	0.281	21	3228
      Multiply_13	0.435	210	29124	0.399	178	25700
      CC_13	0.489	214	29824	0.453	193	27412
      QAOA-10-0.3	0.322	17	3572	0.298	14	3280
      QAOA-10-0.5	0.384	30	4960	0.347	27	4548

7. Conclusion & Reflections

• Conclusion Summary: The paper successfully demonstrates that compiler-assisted qubit reuse, enabled by dynamic circuits, is a highly effective and practical strategy for optimizing quantum computations on near-term hardware. The CaQR tool automates this process, navigating the complex trade-offs between qubit count, circuit depth, SWAP overhead, and fidelity. By intelligently reusing qubits, CaQR not only allows larger circuits to run on small devices but can also enhance the quality of results by avoiding hardware noise.

• Limitations & Future Work:

  • Hardware Instability: The authors note that mid-circuit measurement pulses on current hardware are still not perfectly stable, which may affect performance. They expect results to improve as the hardware matures.
  • Compiler Overhead: The optimal matching algorithm used in the QAOA scheduler has high polynomial complexity. The authors suggest exploring faster, heuristic-based greedy algorithms as a practical alternative for future work.

• Personal Insights & Critique:

  • Practical Impact: This work is exceptionally relevant for the current era of Noisy Intermediate-Scale Quantum (NISQ) computing. It addresses the most pressing limitations—qubit count and noise—with a concrete, automated software solution. It bridges the gap between a new hardware feature and its practical application.
  • Co-design Philosophy: CaQR is a prime example of hardware-software co-design. As quantum hardware evolves (e.g., by adding dynamic circuit capabilities), compiler technology must evolve in tandem to unlock its full potential. This paper shows that the compiler's role is not just to translate, but to actively optimize and strategize based on the underlying device's characteristics.
  • Revealing Hidden Trade-offs: A key insight is that minimizing one resource (qubits) can have non-obvious, positive effects on others (fewer SWAPs, higher fidelity). This highlights the need for holistic, multi-objective optimizers in the quantum compilation stack. CaQR's two-version approach (QS vs. SR) is a smart design choice that allows users to target the optimization that matters most for their specific context.
  • Future Trajectory: This research paves the way for even more sophisticated dynamic compilation techniques. As quantum computers gain more complex classical control capabilities, compilers will play an increasingly crucial role in managing resources, mitigating errors, and enabling fault-tolerant quantum computing. CaQR represents a significant and practical step in that direction.