Quantum Uncomputation of Clean and Dirty Ancilla Qubits
Abstract
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.
Related
- Efficient thermalization of one-dimensional noncommuting Hamiltonians via system-bath interactions with Θ(n) ancilla qubits
- Upper critical dimension for dirty Weyl semimetal-to-metal quantum phase transitions
- MBUndo: Sound, Automatic, and Efficient Measurement-Based Uncomputation for Quantum Circuits
- Evaluation of the quantum Fisher information for large systems via an ancilla
- Generation of arbitrary quantum states in cavity-atom systems with a three-level ancilla
BibTeX
@misc{liu2026quantum,
title = {{Quantum Uncomputation of Clean and Dirty Ancilla Qubits}},
author = {Chenke Liu and Li Zhou and Boning Meng},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2608.09578},
eprint = {2608.09578},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.09578},
}
RIS
TY - UNPB
TI - Quantum Uncomputation of Clean and Dirty Ancilla Qubits
AU - Chenke Liu
AU - Li Zhou
AU - Boning Meng
PY - 2026
DA - 2026/10/11
PB - arXiv
DO - 10.48550/arxiv.2608.09578
UR - https://arxiv.org/abs/2608.09578
AB - 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.
ER -