Qubit Recycling Revisited - Optimizing Quantum Circuit Width

Explore a 19-minute video presentation from the PLDI 2024 conference that delves into the optimization strategy of qubit recycling in quantum circuits. Learn about the introduction of qubit dependency graphs (QDGs) as a key abstraction for reducing circuit width by reusing discarded qubits. Discover how the presenter, Hanru Jiang from the Beijing Institute of Mathematical Sciences and Applications, frames qubit recycling as a matrix triangularization problem and establishes its NP-hardness. Gain insights into a proposed QDG-guided solver featuring multiple heuristic options for effective qubit recycling, and understand its performance compared to existing alternatives. Examine the development of a certified qubit recycler that integrates verification and validation techniques, with its correctness proof mechanized in Coq. Access supplementary materials, including available and reusable artifacts, to further explore the concepts presented in this talk on quantum circuit optimization and certified compilation.