Quantum Uncomputation of Clean and Dirty Ancilla Qubits
2026-08-10 • Programming Languages
Programming Languages
AI summaryⓘ
The authors study a part of quantum computing called uncomputation, which helps restore extra helper qubits (ancillas) to their original state safely. They expanded the understanding from only clean ancilla qubits to also include dirty ancilla qubits, which was unexplored before. They show that figuring out if uncomputation is possible is a very hard problem (coNP-hard). To tackle this, the authors developed two new methods to check and create uncomputation, and tested them in software. Their methods cover more types of quantum circuits than previous tools, showing wider usefulness.
quantum computingancilla qubitsuncomputationclean ancillasdirty ancillascoNP-hardsynthesisrewriting algorithmsQiskitquantum circuits
Authors
Chenke Liu, Li Zhou, Boning Meng
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 rewrite-based normalization algorithm (RwUn) and a template-based reasoning system (TpUn) that guarantees uncomputation through structured Store-Use patterns. We implement prototypes of both methods in Qiskit and Python. Compared to the state-of-the-art Reqomp~\cite{reqomp}, RwUn achieves 100% coverage on practical complex-dependency benchmarks, twice the coverage on random classical circuits, and about 50% coverage on random quantum circuits beyond the scope of existing methods, demonstrating broader applicability.