Qubit Recycling Revisited
summary
Reframes qubit recycling as a graph-plus-matrix problem: introduce Qubit Dependency Graphs and show recycling reduces to an independent row/column permutation that yields a matrix triangularization in the adjacency matrix. Proves NP‑hardness (reduction from Wilf’s question), ships a heuristic solver that hits optimal on 76 of 84 RevLib benchmarks and outperforms CQR in speed, and delivers a certified qubit recycler with Coq‑mechanized soundness proofs using symmetric monoidal category semantics; works with measurement‑and‑reset hardware.
AI-written summary · about
chapters (11)
- 0:00Introduction
- 1:45Qubit recycling limits
- 3:57Certified compilation challenges
- 5:05Qubit recycling as triangulation
- 7:15Dependency graph constraints
- 9:03Matrix triangulation reduction
- 11:13Complexity and heuristics
- 13:39Algorithm performance
- 14:00Certified compiler workflow
- 15:43Categorical semantics
- 17:08Summary
related talks
41mGreen Qubits: Quantum Innovation for Sustainability
18mAutomated distribution of quantum circuits via hypergraph partitioning
15mAssertion-Based Optimization of Quantum Programs
48mHardware-efficient quantum computing using qudits
18mSAQR-QC: A Logic for Scalable but Approximate Quantitative Reasoning about Quantum(…)
22mOptimal Two-Qubit Circuits for Universal Fault-Tolerant Quantum Computation
21mQuantum Backtracking in Qrisp Applied to Sudoku Problems
14mDependency-Aware Compilation for Surface Code Quantum Architectures