Reducing the CNOT count for Clifford+T circuits on NISQ architectures
summary
Presents a heuristic called slice and build that re-synthesizes Clifford+T circuits to cut CNOT count on connectivity-constrained NISQ graphs by combining Steiner-tree reduction with parity/phase-polynomial synthesis and linear reversible (CNOT/NOT) synthesis. Implements the method in Java, evaluates on five published device topologies, and shows consistently lower CNOT growth than naive SWAP insertion while running efficiently; uses phase-polynomial matrices to place T/S phases and Steiner trees to route multi-qubit row operations.
AI-written summary · about
chapters (18)
- 0:00Intro
- 0:18Background
- 0:51Clifford T Circuits
- 1:06Basic Gates
- 1:39Connectivity Graph
- 2:19Naive Solution
- 3:15Motivation
- 4:26Steiner Tree
- 5:19Slice-and-Build Techniques
- 8:36Linear Transformation Synthesis
- 9:36Step 1: Reducing A to Upper Triangular Form
- 11:40Step 2: Reducing A to identity
- 14:30Phase Polynomial Network Synthesis
- 15:14Columns Represent Parity Term
- 15:37Top Six Rows Encode Parity
- 16:06The Last Row Stores Coefficients
- 16:17Implementation
- 17:40Conclusion
related talks
33mOptimizing the Annoying Stuff: Reducing Costs Obscured by the Abstract Circuit Model
20mSynthetiq: Fast and Versatile Quantum Circuit Synthesis
29mEfficiently Verifying Quantum Programs with Few T Gates
22mOptimal Two-Qubit Circuits for Universal Fault-Tolerant Quantum Computation
32mOptimal Quantum Programs
22mHow to Synthesize Quantum-Circuit Optimizers
59mUtility, Computational Cost, and Effective Quantum Volume of NISQ Experiments
51mOn constant T-depth circuits