Fast algorithms for classical specifications of stabiliser states and Clifford gates

Abstract

The stabiliser formalism plays a central role in quantum computing, error correction, and fault tolerance. Conversions between and verifications of different specifications of stabiliser states and Clifford gates are important components of many classical algorithms in quantum information, e.g. for gate synthesis, circuit optimisation, and simulating quantum circuits. These core functions are also used in the numerical experiments critical to formulating and testing mathematical conjectures on the stabiliser formalism. We develop novel mathematical insights concerning stabiliser states and Clifford gates that significantly clarify their descriptions. We then utilise these to provide ten new fast algorithms which offer asymptotic advantages over any existing implementations. We show how to rapidly verify that a vector is a stabiliser state, and interconvert between its specification as amplitudes, a quadratic form, and a check matrix. These methods are leveraged to rapidly check if a given unitary matrix is a Clifford gate and to interconvert between the matrix of a Clifford gate and its compact specification as a stabiliser tableau. For example, we extract the stabiliser tableau of a $2^n\times 2^n$ matrix, promised to be a Clifford gate, in $O(n{2}^n)$ time. Remarkably, it is not necessary to read all the elements of a Clifford gate matrix to extract its stabiliser tableau. This is an asymptotic speedup over the best-known method that is exponential in the number of qubits. We provide implementations of our algorithms in $\text{Python}$ and $\text{C++}$ that exhibit vastly improved practical performance over existing algorithms in the cases where they exist.

C++ and Python implementations available at https://github.com/ndesilva/stabiliser-tools. Final journal version (Quantum)

References in corpus (28)

• Quantum cryptography: Public key distribution and coin tossing
• Concentrating Partial Entanglement by Local Operations
• Improved Simulation of Stabilizer Circuits
• Universal Quantum Computation with ideal Clifford gates and noisy ancillas
• Predicting Many Properties of a Quantum System from Very Few Measurements
• Randomized Benchmarking of Quantum Gates
• Stabilizer Codes and Quantum Error Correction
• Restrictions on Transversal Encoded Quantum Gate Sets
• Stim: a fast stabilizer circuit simulator
• Magic state distillation with low overhead
• Trading classical and quantum computational resources
• Simulation of quantum circuits by low-rank stabilizer decompositions
• Polynomial-time T-depth Optimization of Clifford+T circuits via Matroid Partitioning
• Automated optimization of large quantum circuits with continuous parameters
• The Clifford group, stabilizer states, and linear and quadratic operations over GF(2)
• Fast simulation of stabilizer circuits using a graph state representation
• Experimental Estimation of Quantum State Properties from Classical Shadows
• Entanglement on mixed stabiliser states--I: Normal Forms and Reduction Procedures
• Quantum computing via measurements only
• Optimal verification of stabilizer states
• A Non-Commuting Stabilizer Formalism
• Fast Stabiliser Simulation with Quadratic Form Expansions
• Quantum gate verification and its application in property testing
• Efficient quantum gate teleportation in higher dimensions
• Optimizing T gates in Clifford+T circuit as $\pi /4$ rotations around Paulis
• Symbolic Synthesis of Clifford Circuits and Beyond
• Stabilizer circuit verification
• Stabilizer operators and Barnes-Wall lattices

Cited by in corpus (2)

• Simulation of quantum computation with magic states via Jordan-Wigner transformations
• Limits of Clifford Disentangling in Tensor Network States