Search papers, labs, and topics across Lattice.
This paper presents a comprehensive framework for the automatic uncomputation of both clean and dirty ancilla qubits in quantum computing, addressing a significant gap in existing research. The authors prove that determining the existence of uncomputation is coNP-hard and introduce two novel methods鈥擱wUn and TpUn鈥攖hat enhance synthesis-oriented existence checking. Their implementation in Qiskit shows that RwUn significantly outperforms state-of-the-art methods, achieving 100% coverage on complex-dependency benchmarks and demonstrating broader applicability in quantum circuit contexts.
Checking the existence of uncomputation is coNP-hard, but new methods achieve unprecedented coverage in practical quantum circuit applications.
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.
