A Complete Equational Theory for Quantum Circuits
arXiv:2206.10577 · doi:10.1109/LICS56636.2023.10175801
Abstract
We introduce the first complete equational theory for quantum circuits. More precisely, we introduce a set of circuit equations that we prove to be sound and complete: two circuits represent the same unitary map if and only if they can be transformed one into the other using the equations. The proof is based on the properties of multi-controlled gates -- that are defined using elementary gates -- together with an encoding of quantum circuits into linear optical circuits, which have been proved to have a complete axiomatisation.
arXiv comment92 pages
References in corpus (18)
- Elementary gates for quantum computation
- Interacting Quantum Observables: Categorical Algebra and Diagrammatics
- Polynomial-time T-depth Optimization of Clifford+T circuits via Matroid Partitioning
- Quantum Circuit Simplification and Level Compaction
- Automated optimization of large quantum circuits with continuous parameters
- Graph-theoretic Simplification of Quantum Circuits with the ZX-calculus
- Reducing T-count with the ZX-calculus
- Quantum circuit optimizations for NISQ architectures
- Phase Gadget Synthesis for Shallow Circuits
- ZH: A Complete Graphical Calculus for Quantum Computations Involving Classical Non-linearity
- A Finite Presentation of CNOT-Dihedral Operators
- A Complete Equational Theory for Quantum Circuits
- The Category TOF
- LOv-Calculus: A Graphical Language for Linear Optical Quantum Circuits
- The Category CNOT
- Generators and Relations for 2-Qubit Clifford+T Operators
- Generators and Relations for Real Stabilizer Operators
- Complete set of circuit equations for Stabilizer Quantum Mechanics
Cited by in corpus (6)
- A Complete Equational Theory for Quantum Circuits
- A Complete and Natural Rule Set for Multi-Qutrit Clifford Circuits
- A Sound and Complete Equational Theory for 3-Qubit Toffoli-Hadamard Circuits
- Quantum Circuits Are Just a Phase
- Minimal Equational Theories for Quantum Circuits
- A Complete Equational Theory for Quantum Circuits with Generalized Control