A Complete Equational Theory for Quantum Circuits

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.

92 pages

References in corpus (5)

• Quantum Circuit Simplification and Level Compaction
• A Complete Equational Theory for Quantum Circuits
• LOv-Calculus: A Graphical Language for Linear Optical Quantum Circuits
• Generators and Relations for Real Stabilizer Operators
• Generators and Relations for 2-Qubit Clifford+T Operators

Cited by in corpus (5)

• 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