Ancillary qubits are an essential resource in quantum programs, yet their management often introduces artificial long-range dependencies that obscure opportunities for parallel execution. In many programming models, uncomputation is treated as a global cleanup phase appended after the forward computation, causing temporary data to remain live far beyond its semantic relevance and inflating both circuit width and scheduling constraints. Building on the lifetime-guided uncomputation discipline introduced in the quantum programming language Qutes, this paper identifies and formalizes a new form of parallelism emerging from the semantic structure of quantum programs. By precisely tracking the semantic lifetime of temporary variables, subcomputations associated with ancillas can be restored locally once their influence terminates. This mechanism exposes a form of structural parallelism that arises not from qubit disjointness or quantum superposition, but from the reduction of semantic dependencies in the program. We formalize this phenomenon through the notion of temporary regions in the circuit dependence graph and show that lifetime-guided reclamation induces a contraction of these regions, collapsing temporary subcomputations into locally closed structures. As a consequence, circuits compiled under this discipline reduce peak width through systematic ancilla reuse and improve space–time volume without increasing asymptotic depth, illustrating how high-level language semantics can reshape the structural properties of quantum circuits.
Ancillary qubits are an essential resource in quantum programs, yet their management often introduces artificial long-range dependencies that obscure opportunities for parallel execution. In many programming models, uncomputation is treated as a global cleanup phase appended after the forward computation, causing temporary data to remain live far beyond its semantic relevance and inflating both circuit width and scheduling constraints. Building on the lifetime-guided uncomputation discipline introduced in the quantum programming language Qutes, this paper identifies and formalizes a new form of parallelism emerging from the semantic structure of quantum programs. By precisely tracking the semantic lifetime of temporary variables, subcomputations associated with ancillas can be restored locally once their influence terminates. This mechanism exposes a form of structural parallelism that arises not from qubit disjointness or quantum superposition, but from the reduction of semantic dependencies in the program. We formalize this phenomenon through the notion of temporary regions in the circuit dependence graph and show that lifetime-guided reclamation induces a contraction of these regions, collapsing temporary subcomputations into locally closed structures. As a consequence, circuits compiled under this discipline reduce peak width through systematic ancilla reuse and improve space–time volume without increasing asymptotic depth, illustrating how high-level language semantics can reshape the structural properties of quantum circuits.
Reversible computation requires that intermediate data be explicitly undone rather than discarded. In quantum programming, this principle appears as uncomputation, usually treated as a technical cleanup mechanism. We instead present uncomputation as a semantic foundation. In the Qutes language, we introduce a formal model of \emph{Scope-Bounded Liveness-Guided Uncomputation}, where lexical scope bounds variable lifetime and static liveness and entanglement analysis determine the earliest safe reclamation point. We define semantic lifetime and a Restoration Invariant ensuring that temporary quantum information disappears once it becomes semantically irrelevant. We prove compositional correctness under nested scopes and show that early reclamation can reduce circuit depth by avoiding critical-path overhead and can bound peak live qubits through disciplined ancilla reuse. Finally, we show that parameter passing semantics emerges from the same lifetime discipline, with pass-by-value and pass-by-reference corresponding to different lifetime boundaries, and we characterize the constraints (irreversibility, persistent entanglement, and aliasing) under which automatic uncomputation must be restricted.
Many quantum algorithms instantiate and use ancillas, spare qubits that serve as temporary storage in a quantum circuit. In particular, many recently developed high-level and modular quantum programming languages (QPLs) use ancilla qubits to implement various programming constructs. These are lowered to circuits with nested/cascading compute-uncompute gate sequences that use ancilla qubits to track internal state. We present SPARE, a rewrite-based quantum circuit optimizer that restructures these compute-uncompute gate sequences, leveraging the ancilla qubit state information to optimize the circuit. In this work, we prove the correctness of SPARE’s rewrites and link SPARE’s gate-level transforms to language-level program rewrites, which may be performed on the input language. We evaluate SPARE on QPL-generated quantum circuits against Unqomp and Spire, two optimizing compilers for QPLs. SPARE achieves a reduction of up to 27.3 % in qubit count, 56.7 % in 2 -qubit gates, 68.2 % in 1-qubit gates and 73.9 % in depth against Unqomp, and up to 17.8 % in qubits, 67.3 % in 2-qubit gates, 61.4 % in 1-qubit gates and 59.9 % in depth against Spire. We also evaluate SPARE against the Quartz, Feynman, and PyZX circuit optimizers: SPARE achieves up to a 70.0 % reduction in two-qubit gates, up to a 53.6 % reduction in 1-qubit gates, and up to a 56.7 % reduction in depth compared to the best result from all the gate-level optimizers.
We present a language extension for parallel quantum programming to (1) remove ambiguities concerning parallelism in current quantum programming languages and (2) facilitate space-time tradeoff investigations in quantum computing. While the focus of similar libraries in the domain of classical computing (OpenMP, OpenACC, etc.) is to divide a computation into multiple threads, the main goal of QParallel is to keep the compiler and the runtime system from introducing parallelism-inhibiting dependencies, e.g., through reuse of qubits in automatic qubit management. We describe the syntax and semantics of the proposed language extension, implement a prototype based on Q#, and present several examples and use cases to illustrate its performance benefits. Moreover, we introduce a tool that guides programmers in the placement of parallel regions by identifying the subroutines that profit most from parallelization, which is especially useful if the programmer's knowledge of the source code is limited. Support for QParallel can be added to any multithreading library and language extension, including OpenMP and OpenACC.
Automatic uncomputation aims to provide programming-language-level support to facilitate the correct and safe use of ancilla qubits in quantum computing, but efforts have only been made for clean ancillas, leaving dirty ancillas unexplored. We present a unified formalization of the uncomputation of both clean and dirty ancillas. For the first time, we prove that checking the existence of uncomputation is coNP-hard. We introduce two complementary synthesis-oriented existence checking methods: a syntax-directed static reasoning system and a rewrite-based normalization procedure (\RwUnx), together forming a top-down pipeline. We implement \RwUnx in Qiskit. Compared with the state-of-the-art \Reqompx, \RwUnx handles practical benchmarks with complex dependencies where \Reqompx does not, and achieves higher success rates in random-circuit experiments.
The management of ancilla qubits has become a critical technique for reducing quantum circuit width. Dirty ancillas, which may be borrowed from any temporarily idle qubit regardless of their initial states, offer substantial flexibility for width optimization, but their use has so far required manual and error-prone handling. We formalize the dirty-qubit borrowing problem and establish a fundamental computational limit by proving its NP-hardness. To support practical optimization, we present \bona, the first scheduler for dirty-qubit borrowing, built on a novel depth-aware heuristic algorithm. We evaluate \bona~ across a variety of benchmarks, including practical quantum circuits and randomly arranged compositions of real circuit modules, and find that it reduces nearly 99\% of dirty ancillas on average with controlled depth overhead. In particular, for parallel quantum walk---an essential component of parallel Hamiltonian simulation---\bona~ matches the circuit width achieved by the clean-qubit schemes of \citeauthor{jiang2024recycling}~(\citeyear{jiang2024recycling}) and \citeauthor{quantinuum}~(\citeyear{quantinuum}), but attains significantly smaller circuit depth, providing concrete evidence that dirty ancillas offer unique optimization advantages in circuits with certain parallelism.
Compiling high-level quantum programs to machines that are size constrained (i.e. limited number of quantum bits) and time constrained (i.e. limited number of quantum operations) is challenging. In this paper, we present SQUARE (Strategic QUantum Ancilla REuse), a compilation infrastructure that tackles allocation and reclamation of scratch qubits (called ancilla) in modular quantum programs. At its core, SQUARE strategically performs uncomputation to create opportunities for qubit reuse.Current Noisy Intermediate-Scale Quantum (NISQ) computers and forward-looking Fault-Tolerant (FT) quantum computers have fundamentally different constraints such as data locality, instruction parallelism, and communication overhead. Our heuristic-based ancilla-reuse algorithm balances these considerations and fits computations into resource-constrained NISQ or FT quantum machines, throttling parallelism when necessary. To precisely capture the workload of a program, we propose an improved metric, the “active quantum volume,” and use this metric to evaluate the effectiveness of our algorithm. Our results show that SQUARE improves the average success rate of NISQ applications by 1. 47X. Surprisingly, the additional gates for uncomputation create ancilla with better locality, and result in substantially fewer swap gates and less gate noise overall. SQUARE also achieves an average reduction of 1. 5X (and up to 9. 6X) in active quantum volume for FT machines.