The Classification of Clifford Gates over Qubits
arXiv:1603.03999 · doi:10.22331/q-2022-06-13-734
Abstract
We examine the following problem: given a collection of Clifford gates, describe the set of unitaries generated by circuits composed of those gates. Specifically, we allow the standard circuit operations of composition and tensor product, as well as ancillary workspace qubits as long as they start and end in states uncorrelated with the input, which rule out common "magic state injection" techniques that make Clifford circuits universal. We show that there are exactly 57 classes of Clifford unitaries and present a full classification characterizing the gate sets which generate them. This is the first attempt at a quantum extension of the classification of reversible classical gates introduced by Aaronson et al., another part of an ambitious program to classify all quantum gate sets. The classification uses, at its center, a reinterpretation of the tableau representation of Clifford gates to give circuit decompositions, from which elementary generators can easily be extracted. The 57 different classes are generated in this way, 30 of which arise from the single-qubit subgroups of the Clifford group. At a high level, the remaining classes are arranged according to the bases they preserve. For instance, the CNOT gate preserves the X and Z bases because it maps X-basis elements to X-basis elements and Z-basis elements to Z-basis elements. The remaining classes are characterized by more subtle tableau invariants; for instance, the T_4 and phase gate generate a proper subclass of Z-preserving gates.
arXiv comment45 pages; v4 - journal version v3 - "Stabilizer Operations" is replaced by "Clifford Gates" in title. Improved writing and main decomposition theorem; v2 - Retracts claimed stabilizer ancilla for the Gamma gate
References in corpus (16)
- Elementary gates for quantum computation
- Measurement-based quantum computation with cluster states
- Improved Simulation of Stabilizer Circuits
- Universal Quantum Computation with ideal Clifford gates and noisy ancillas
- Multiple Particle Interference and Quantum Error Correction
- A Theory of Fault-Tolerant Quantum Computation
- Entanglement-assisted local manipulation of pure quantum states
- Layered architecture for quantum computing
- The Clifford group, stabilizer states, and linear and quadratic operations over GF(2)
- Exact synthesis of multiqubit Clifford+T circuits
- Lower bounds on the non-Clifford resources for quantum computations
- Hadamard-free circuits expose the structure of the Clifford group
- Shorter stabilizer circuits via Bruhat decomposition and quantum circuit transformations
- Generators and relations for n-qubit Clifford operators
- Generation of Universal Linear Optics by Any Beamsplitter
- Number-Theoretic Characterizations of Some Restricted Clifford+T Circuits
Cited by in corpus (7)
- Efficient self-consistent learning of gate set Pauli noise
- Single-qubit gate teleportation provides a quantum advantage
- A Rubik's Cube inspired approach to Clifford synthesis
- Decoding across transversal Clifford gates in the surface code
- Celestial Quantum Error Correction I: Qubits from Noncommutative Klein Space
- On character table of Clifford groups
- PHOENIX: Pauli-Based High-Level Optimization Engine for Instruction Execution on NISQ Devices