Optimal Quantum Programs
summary
Three notions of optimality are compared: reliability (gate error rates ~single‑qubit 99.99%, two‑qubit ~99.9%), depth (mapping to hardware is NP‑complete and current compilers often insert 10x more swaps than optimal), and two‑qubit count (optimizers typically cut two‑qubit gates ~30%). Concrete results: the Toffoli (CCX) requires six CNOTs if only CNOTs are allowed, or five two‑qubit gates with arbitrary two‑qubit unitaries; the optimality proofs are formalized in Coq (≈16k lines, one lemma left).
AI-written summary · about
chapters (9)
- 0:00Optimal quantum programs
- 1:06Reliability in quantum computing
- 6:47Quantum circuit compilation challenges
- 11:45Toffoli gate optimality
- 16:45Proving optimality with linear algebra
- 23:24Formalizing proofs in Coq and Lean
- 25:29Running on real quantum computers
- 27:57Optimality versus physical layout
- 30:07Future of error correction
related talks
22mOptimal Two-Qubit Circuits for Universal Fault-Tolerant Quantum Computation
15mAssertion-Based Optimization of Quantum Programs
19mAn Industry Perspective on the Path Forward in Quantum Optimization
01h 09mRecent Progress in Quantum Advantage
29mEfficiently Verifying Quantum Programs with Few T Gates
24mSynthesizing Quantum-Circuit Optimizers
17mCompiling Conditional Quantum Gates without Using Helper Qubits
01h 01mInvited Talk: Welcome to Quantum 3.0!