Optimizing Ancilla-Based Quantum Circuits with SPARE
Ritvik Sharma, Sara Achour
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.
Ask Lune
Know where this paper stands in minutes, not an afternoon.
Lune can read the top-tier papers that cite it and the ones closest to it, and tells you what it claims, what came after and where it falls short, each point cited to the paper it comes from. No skimming, no AI slop.
3 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
its abstract · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
Cited by top-tier papers3
Related papers
- Quartz: superoptimization of Quantum circuitsMingkuan Xu, Zikun Li, Oded Padon, Sina Lin et al.PLDI 2022 · 57 citations
- Unqomp: synthesizing uncomputation in Quantum circuitsAnouk Paradis, Benjamin Bichsel, Samuel Steffen, Martin T. VechevPLDI 2021 · 34 citations
- SQUARE: Strategic Quantum Ancilla Reuse for Modular Quantum Programs via Cost-Effective UncomputationYongshan Ding, Xin-Chuan Wu, Adam Holmes, Ash Wiseth et al.ISCA 2020 · 33 citations
- Compilation of Qubit Circuits to Optimized Qutrit CircuitsRitvik Sharma, Sara AchourPLDI 2024 · 2 citations
- A verified optimizer for Quantum circuitsKesha Hietala, Robert Rand, Shih-Han Hung, Xiaodi Wu et al.POPL 2021 · 111 citations
