{"id":"arxiv/2608.09578","url":"https://arxiv.org/abs/2608.09578","tags":["cs.PL","quant-ph"],"score":0,"title":"Quantum Uncomputation of Clean and Dirty Ancilla Qubits","domain":"cs.PL","source":"arxiv","authors":["Chenke Liu","Li Zhou","Boning Meng"],"reviews":0,"subject":"cs.PL","summary":"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),…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-08-10","reactions":{}}