How to Synthesize Quantum-Circuit Optimizers
summary
Synthesizes provably correct rewrite rules for device-specific gate sets by hashing polynomial circuit semantics so enumeration becomes linear not quadratic, then uses a polynomial identity filter with random instantiation (short simple lemma) to test equivalence. Produces 700 rules in 1.2 minutes with a failure bound around 10^-7, targets two-qubit and T-gate reduction, matches or outperforms academic and industrial optimizers on benchmarks, and pairs ahead-of-time rules with runtime circuit re-synthesis to get larger, approximate rewrites; implementation is available as open source.
AI-written summary · about
chapters (10)
- 0:00Quantum circuit optimization intro
- 1:24Why circuits need optimization
- 3:12Hardware-specific optimizations
- 4:38Handcrafted vs synthesized optimizers
- 6:43Synthesizing rewrite rules
- 10:37Equivalence checking filter
- 15:59Evaluating optimizers on benchmarks
- 18:06Runtime re-synthesis
- 20:16Rewrite rules and re-synthesis
- 20:58Future directions
related talks
24mSynthesizing Quantum-Circuit Optimizers
20mSynthetiq: Fast and Versatile Quantum Circuit Synthesis
19mEquality Saturation for Quantum Circuit Optimization
01h 10mThe Rise & Collapse of a Quantum State
15mAssertion-Based Optimization of Quantum Programs
17mOptimization and Synthesis of Quantum Circuits with Global Gates
32mOptimal Quantum Programs
15mModular Component-Based Quantum Circuit Synthesis