Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Proceedings of the ACM on Programming Languages

Optimizing Ancilla-Based Quantum Circuits with SPARE

Ritvik Sharma, Sara Achour

Published Jun 10, 2025• 0 citations
Publisher

Abstract

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.

DOI
10.1145/3729253

Related papers

Compilation of Qubit Circuits to Optimized Qutrit Circuits

Ritvik Sharma, Sara Achour

Quantum computers are a revolutionary class of computational platforms that are capable of solving computationally hard problems. However, today’s quantum hardware is subject to noise and decoherence issues that together limit the scale and complexity of the quantum circuits that can be implemented. Recently, practitioners have developed qutrit-based quantum hardware platforms that compute over ∣ 0 ⟩ , ∣ 1 ⟩ , and ∣ 2 ⟩ states, and have presented circuit depth reduction techniques using qutrits’ higher energy ∣ 2 ⟩ states to temporarily store information. However, thus far, such quantum circuits that use higher order states for temporary storage need to be manually crafted by hardware designers. We present D are , an optimizing compiler for qutrit circuits that implement qubit computations. D are deploys a qutrit circuit decomposition algorithm and a rewrite engine to construct and optimize qutrit circuits. We evaluate D are against hand-optimized qutrit circuits and qubit circuits, and find D are delivers up to 65 % depth improvement over manual qutrit implementations, and 43-75% depth improvement over qubit circuits. We also perform a fidelity analysis and find DARE-optimized qutrit circuits deliver up to 8.9 × higher fidelity circuits than their manually implemented counterparts.

Proceedings of the ACM on Programming Languages•Jun 20, 2024•2 citations

Uncomputing Ancilla Qubits in Quantum Circuits

Ashutosh Tiwari, Ranjani G. Sundaram, Himanshu Gupta +2 more

Uncomputation of ancilla qubits is essential in quantum computing to reset auxiliary qubits to a zero state, ensuring their safe discarding and reducing resource overhead. Current methods for uncomputation either rely on manual procedures or use additional ancilla qubits to store intermediate computation results, which increases qubit storage requirements. Additionally, most in-place uncomputation techniques employ an all-or-nothing strategy, wherein they perform uncomputation only when all ancilla qubits in the given circuit can be uncomputed.In this work, we tackle the problem of uncomputing a maximum number of ancilla qubits in a quantum circuit with minimal qubit storage overhead. We propose a novel approach where partial uncomputation—reverting the last ’m’ gates—enables the uncomputation of more qubits. We present three algorithms designed to uncompute the largest possible set of ancilla qubits and demonstrate their effectiveness through experiments on various randomly generated quantum circuits.

International Conference on Quantum Communications, Networking, and Computing (QCNC)•Mar 31, 2025•2 citations

Design and Optimization of Complex Quantum Circuits Targeting Near-Term Quantum Processors Using Custom Algorithms and Qiskit Transpiler

Kazi Redwan, Mustakim Ahmed, Md. Faruk Abdullah Al Sohan +5 more

Quantum computing faces challenges such as noise, short coherence time, and limited qubit connections. These challenges worsen as quantum circuits become more complex. One major issue is the increasing depth of quantum circuits. This research proposes an optimization framework targeting depth and gate count reduction in quantum circuits, specifically for Noisy Intermediate-Scale Quantum (NISQ) devices. The proposed approach combines unitary merging of single-qubit gates, CNOT cancellation, gate commuting, and rotation gate rewriting strategies. Consecutive gates acting on the same qubit, such as$R_{x}\left(\theta_{1}\right) \cdot R_{x}\left(\theta_{2}\right)$, are algebraically merged into a single rotation, while pairs of redundant CNOT gates are eliminated based on gate identity relations. The technique is implemented using Qiskit and validated across five diverse circuits including complex, random, and multi-qubit configurations. Experimental results show an average depth reduction of 33.33% and gate count reduction of 32.14%, with runtime improvement of up to 25%. For instance, an input circuit with a depth of 7 and gate count of 11 was reduced to a depth of 2 and 4 gates. All optimized circuits preserve functional correctness with a fidelity$F \geq 0.99$. High-resolution circuit diagrams are presented to visually demonstrate improvements before and after optimization. Additionally, global phase shifts such as$e^{i \pi / 4}$are preserved or analytically characterized where relevant. This work enhances the viability of quantum computations on near-term hardware and opens pathways for future AI-driven quantum optimizations.

IEEE Region 10 Conference (TENCON)•Oct 27, 2025•0 citations

Quantum Uncomputation of Clean and Dirty Ancilla Qubits

Chenke Liu, Li Zhou, Boning Meng

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.

cs.PLCross-listedarXiv:2608.09578•Proceedings of the ACM on Programming Languages•Aug 11, 2026•0 citations

Unqomp: synthesizing uncomputation in Quantum circuits

Anouk Paradis, Benjamin Bichsel, Samuel Steffen +1 more

A key challenge when writing quantum programs is the need for uncomputation: temporary values produced during the computation must be reset to zero before they can be safely discarded. Unfortunately, most existing quantum languages require tedious manual uncomputation, often leading to inefficient and error-prone programs. We present Unqomp, the first procedure to automatically synthesize uncomputation in a given quantum circuit. Unqomp can be readily integrated into popular quantum languages, allowing the programmer to allocate and use temporary values analogously to classical computation, knowing they will be uncomputed by Unqomp. Our evaluation shows that programs leveraging Unqomp are not only shorter (-19% on average), but also generate more efficient circuits (-71% gates and -19% qubits on average).

ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI)•Jun 18, 2021•34 citations

SQUARE: Strategic Quantum Ancilla Reuse for Modular Quantum Programs via Cost-Effective Uncomputation

Yongshan Ding, Xin-Chuan Wu, Adam Holmes +4 more

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.

arXiv:2004.08539•Proceedings - International Symposium on Computer Architecture/Proceedings•May 1, 2020•40 citations
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.
Quantum computers are a revolutionary class of computational platforms that are capable of solving computationally hard problems. However, today’s quantum hardware is subject to noise and decoherence issues that together limit the scale and complexity of the quantum circuits that can be implemented. Recently, practitioners have developed qutrit-based quantum hardware platforms that compute over ∣ 0 ⟩ , ∣ 1 ⟩ , and ∣ 2 ⟩ states, and have presented circuit depth reduction techniques using qutrits’ higher energy ∣ 2 ⟩ states to temporarily store information. However, thus far, such quantum circuits that use higher order states for temporary storage need to be manually crafted by hardware designers. We present D are , an optimizing compiler for qutrit circuits that implement qubit computations. D are deploys a qutrit circuit decomposition algorithm and a rewrite engine to construct and optimize qutrit circuits. We evaluate D are against hand-optimized qutrit circuits and qubit circuits, and find D are delivers up to 65 % depth improvement over manual qutrit implementations, and 43-75% depth improvement over qubit circuits. We also perform a fidelity analysis and find DARE-optimized qutrit circuits deliver up to 8.9 × higher fidelity circuits than their manually implemented counterparts.
Uncomputation of ancilla qubits is essential in quantum computing to reset auxiliary qubits to a zero state, ensuring their safe discarding and reducing resource overhead. Current methods for uncomputation either rely on manual procedures or use additional ancilla qubits to store intermediate computation results, which increases qubit storage requirements. Additionally, most in-place uncomputation techniques employ an all-or-nothing strategy, wherein they perform uncomputation only when all ancilla qubits in the given circuit can be uncomputed.In this work, we tackle the problem of uncomputing a maximum number of ancilla qubits in a quantum circuit with minimal qubit storage overhead. We propose a novel approach where partial uncomputation—reverting the last ’m’ gates—enables the uncomputation of more qubits. We present three algorithms designed to uncompute the largest possible set of ancilla qubits and demonstrate their effectiveness through experiments on various randomly generated quantum circuits.
Quantum computing faces challenges such as noise, short coherence time, and limited qubit connections. These challenges worsen as quantum circuits become more complex. One major issue is the increasing depth of quantum circuits. This research proposes an optimization framework targeting depth and gate count reduction in quantum circuits, specifically for Noisy Intermediate-Scale Quantum (NISQ) devices. The proposed approach combines unitary merging of single-qubit gates, CNOT cancellation, gate commuting, and rotation gate rewriting strategies. Consecutive gates acting on the same qubit, such asRx(θ1)⋅Rx(θ2)R_{x}\left(\theta_{1}\right) \cdot R_{x}\left(\theta_{2}\right)Rx​(θ1​)⋅Rx​(θ2​), are algebraically merged into a single rotation, while pairs of redundant CNOT gates are eliminated based on gate identity relations. The technique is implemented using Qiskit and validated across five diverse circuits including complex, random, and multi-qubit configurations. Experimental results show an average depth reduction of 33.33% and gate count reduction of 32.14%, with runtime improvement of up to 25%. For instance, an input circuit with a depth of 7 and gate count of 11 was reduced to a depth of 2 and 4 gates. All optimized circuits preserve functional correctness with a fidelityF≥0.99F \geq 0.99F≥0.99. High-resolution circuit diagrams are presented to visually demonstrate improvements before and after optimization. Additionally, global phase shifts such aseiπ/4e^{i \pi / 4}eiπ/4are preserved or analytically characterized where relevant. This work enhances the viability of quantum computations on near-term hardware and opens pathways for future AI-driven quantum optimizations.
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.
A key challenge when writing quantum programs is the need for uncomputation: temporary values produced during the computation must be reset to zero before they can be safely discarded. Unfortunately, most existing quantum languages require tedious manual uncomputation, often leading to inefficient and error-prone programs. We present Unqomp, the first procedure to automatically synthesize uncomputation in a given quantum circuit. Unqomp can be readily integrated into popular quantum languages, allowing the programmer to allocate and use temporary values analogously to classical computation, knowing they will be uncomputed by Unqomp. Our evaluation shows that programs leveraging Unqomp are not only shorter (-19% on average), but also generate more efficient circuits (-71% gates and -19% qubits on average).
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.