Modular Synthesis of Efficient Quantum Uncomputation
Hristo Venev, Timon Gehr, Dimitar Dimitrov, Martin T. Vechev
Abstract
A key challenge of quantum programming is uncomputation: the reversible deallocation of qubits. And while there has been much recent progress on automating uncomputation, state-of-the-art methods are insufficient for handling today's expressive quantum programming languages. A core reason is that they operate on primitive quantum circuits, while quantum programs express computations beyond circuits, for instance, they can capture families of circuits defined recursively in terms of uncomputation and adjoints.
In this paper, we introduce the first modular automatic approach to synthesize correct and efficient uncomputation for expressive quantum programs. Our method is based on two core technical contributions: (i) an intermediate representation (IR) that can capture expressive quantum programs and comes with support for uncomputation, and (ii) modular algorithms over that IR for synthesizing uncomputation and adjoints.
We have built a complete end-to-end implementation of our method, including an implementation of the IR and the synthesis algorithms, as well as a translation from an expressive fragment of the Silq programming language to our IR and circuit generation from the IR. Our experimental evaluation demonstrates that we can handle programs beyond the capabilities of existing uncomputation approaches, while being competitive on the benchmarks they can handle. More broadly, we show that it is possible to benefit from the greater expressivity and safety offered by high-level quantum languages without sacrificing efficiency.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
6 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- Borrowing Dirty Qubits in Quantum Programs cites Unqomp: synthesizing uncomputation in Quantum circuits
- Borrowing Dirty Qubits in Quantum Programs cites Silq: a high-level quantum language with safe uncomputation and intuitive semantics
- Borrowing Dirty Qubits in Quantum Programs cites Qunity: A Unified Language for Quantum and Classical Computing
- Unqomp: synthesizing uncomputation in Quantum circuits cites Silq: a high-level quantum language with safe uncomputation and intuitive semantics
- Quantum Register Machine: Efficient Implementation of Quantum Recursive Programs cites Unqomp: synthesizing uncomputation in Quantum circuits
- Quantum Register Machine: Efficient Implementation of Quantum Recursive Programs cites Tower: data structures in Quantum superposition
- Quantum Register Machine: Efficient Implementation of Quantum Recursive Programs cites Silq: a high-level quantum language with safe uncomputation and intuitive semantics
- Quantum Register Machine: Efficient Implementation of Quantum Recursive Programs cites Qunity: A Unified Language for Quantum and Classical Computing
- Quantum information effects cites Silq: a high-level quantum language with safe uncomputation and intuitive semantics
- Tower: data structures in Quantum superposition cites Unqomp: synthesizing uncomputation in Quantum circuits
- Tower: data structures in Quantum superposition cites Silq: a high-level quantum language with safe uncomputation and intuitive semantics
- Qunity: A Unified Language for Quantum and Classical Computing cites Silq: a high-level quantum language with safe uncomputation and intuitive semantics
- Quantum Uncomputation of Clean and Dirty Ancilla Qubits cites Borrowing Dirty Qubits in Quantum Programs
- Quantum Uncomputation of Clean and Dirty Ancilla Qubits cites Unqomp: synthesizing uncomputation in Quantum circuits
- Quantum Uncomputation of Clean and Dirty Ancilla Qubits cites Silq: a high-level quantum language with safe uncomputation and intuitive semantics
- Quantum Uncomputation of Clean and Dirty Ancilla Qubits cites Qurts: Automatic Quantum Uncomputation by Affine Types with Lifetime
- Qurts: Automatic Quantum Uncomputation by Affine Types with Lifetime cites Unqomp: synthesizing uncomputation in Quantum circuits
- Qurts: Automatic Quantum Uncomputation by Affine Types with Lifetime cites Silq: a high-level quantum language with safe uncomputation and intuitive semantics
Cited by top-tier papers6
- Qurts: Automatic Quantum Uncomputation by Affine Types with LifetimeKengo Hirata, Chris HeunenPOPL 2025 · 4 citations
- Quantum Register Machine: Efficient Implementation of Quantum Recursive ProgramsZhicheng Zhang, Mingsheng YingPLDI 2025 · 3 citations
- AccelerQ: Accelerating Quantum Eigensolvers with Machine Learning on Quantum SimulatorsAvner Bensoussan, Elena Chachkarova, Karine Even-Mendoza, Sophie Fortz et al.OOPSLA 2025 · 1 citation
- Borrowing Dirty Qubits in Quantum ProgramsBonan Su, Li Zhou, Yuan Feng, Mingsheng YingASPLOS 2026 · 1 citation
- Quantum Uncomputation of Clean and Dirty Ancilla QubitsChenke Liu, Li Zhou, Boning MengOOPSLA 2026
Builds on5
- Silq: a high-level quantum language with safe uncomputation and intuitive semanticsBenjamin Bichsel, Maximilian Baader, Timon Gehr, Martin T. VechevPLDI 2020 · 145 citations
- Qunity: A Unified Language for Quantum and Classical ComputingFinn Voichick, Liyi Li, Robert Rand, Michael HicksPOPL 2023 · 35 citations
- Unqomp: synthesizing uncomputation in Quantum circuitsAnouk Paradis, Benjamin Bichsel, Samuel Steffen, Martin T. VechevPLDI 2021 · 34 citations
- Tower: data structures in Quantum superpositionCharles Yuan, Michael CarbinOOPSLA 2022 · 26 citations
- Quantum information effectsChris Heunen, Robin KaarsgaardPOPL 2022 · 1 citation
Related papers
- Compositional Quantum Control Flow with Efficient Compilation in QunityMikhail Mints, Finn Voichick, Leonidas Lampropoulos, Robert RandOOPSLA 2025
- Quantum Circuits Are Just a PhaseChris Heunen, Louis Lemonnier, Christopher McNally, Alex RicePOPL 2026
- A Case for Synthesis of Recursive Quantum Unitary ProgramsHaowei Deng, Runzhou Tao, Yuxiang Peng, Xiaodi WuPOPL 2024 · 10 citations
- Optimizing Ancilla-Based Quantum Circuits with SPARERitvik Sharma, Sara AchourPLDI 2025
- A verified optimizer for Quantum circuitsKesha Hietala, Robert Rand, Shih-Han Hung, Xiaodi Wu et al.POPL 2021 · 111 citations
