Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper addresses the challenge of managing dirty ancilla qubits in quantum circuits, a critical factor for reducing circuit width. By formalizing the dirty-qubit borrowing problem and proving its NP-hardness, the authors introduce Bona, a scheduler that employs a depth-aware heuristic algorithm to optimize the use of dirty ancillas. Evaluations show that Bona reduces nearly 99% of dirty ancillas on average while achieving circuit depth comparable to clean-qubit schemes, highlighting its effectiveness in circuits with parallelism.
Dirty ancillas can drastically cut down circuit width while maintaining lower depth than traditional clean-qubit methods, revolutionizing quantum circuit design.
The management of ancilla qubits has become a critical technique for reducing quantum circuit width. Dirty ancillas, which may be borrowed from any temporarily idle qubit regardless of their initial states, offer substantial flexibility for width optimization, but their use has so far required manual and error-prone handling. We formalize the dirty-qubit borrowing problem and establish a fundamental computational limit by proving its NP-hardness. To support practical optimization, we present \bona, the first scheduler for dirty-qubit borrowing, built on a novel depth-aware heuristic algorithm. We evaluate \bona~ across a variety of benchmarks, including practical quantum circuits and randomly arranged compositions of real circuit modules, and find that it reduces nearly 99\% of dirty ancillas on average with controlled depth overhead. In particular, for parallel quantum walk---an essential component of parallel Hamiltonian simulation---\bona~ matches the circuit width achieved by the clean-qubit schemes of \citeauthor{jiang2024recycling}~(\citeyear{jiang2024recycling}) and \citeauthor{quantinuum}~(\citeyear{quantinuum}), but attains significantly smaller circuit depth, providing concrete evidence that dirty ancillas offer unique optimization advantages in circuits with certain parallelism.