Hadamard-free circuits expose the structure of the Clifford group

Abstract

The Clifford group plays a central role in quantum randomized benchmarking, quantum tomography, and error correction protocols. Here we study the structural properties of this group. We show that any Clifford operator can be uniquely written in the canonical form $F_{1}HS{F}_2$, where $H$ is a layer of Hadamard gates, $S$ is a permutation of qubits, and $F_i$ are parameterized Hadamard-free circuits chosen from suitable subgroups of the Clifford group. Our canonical form provides a one-to-one correspondence between Clifford operators and layered quantum circuits. We report a polynomial-time algorithm for computing the canonical form. We employ this canonical form to generate a random uniformly distributed $n$-qubit Clifford operator in runtime $O(n^2)$. The number of random bits consumed by the algorithm matches the information-theoretic lower bound. A surprising connection is highlighted between random uniform Clifford operators and the Mallows distribution on the symmetric group. The variants of the canonical form, one with a short Hadamard-free part and one allowing a circuit depth $9n$ implementation of arbitrary Clifford unitaries in the Linear Nearest Neighbor architecture are also discussed. Finally, we study computational quantum advantage where a classical reversible linear circuit can be implemented more efficiently using Clifford gates, and show an explicit example where such an advantage takes place.

References in corpus (14)

• Mixed State Entanglement and Quantum Error Correction
• Universal Quantum Computation with ideal Clifford gates and noisy ancillas
• Improved Simulation of Stabilizer Circuits
• Predicting Many Properties of a Quantum System from Very Few Measurements
• Randomized Benchmarking of Quantum Gates
• Robust randomized benchmarking of quantum processes
• Scalable Noise Estimation with Random Unitary Operators
• Quantum Data Hiding
• Graph-theoretic Simplification of Quantum Circuits with the ZX-calculus
• Multiqubit Clifford groups are unitary 3-designs
• Entanglement renormalization and topological order
• How to efficiently select an arbitrary Clifford group element
• Bifurcation in entanglement renormalization group flow of a gapped spin model
• Shorter stabilizer circuits via Bruhat decomposition and quantum circuit transformations

Cited by in corpus (70)

• Universal behavior beyond multifractality of wave-functions at measurement--induced phase transitions
• Random quantum circuits are approximate unitary $t$-designs in depth $O\left(n{t}^{5+o(1)}\right)$
• Matchgate Shadows for Fermionic Quantum Simulation
• Scalable randomized benchmarking of quantum computers using mirror circuits
• Measuring nonstabilizerness via multifractal flatness
• Covariant quantum kernels for data with group structure
• Dynamical Magic Transitions in Monitored Clifford+T Circuits
• Classical Shadows for Quantum Process Tomography on Near-term Quantum Computers
• Learning t-doped stabilizer states
• Predicting Gibbs-State Expectation Values with Pure Thermal Shadows
• Learning efficient decoders for quasi-chaotic quantum scramblers
• Clifford Circuit Optimization with Templates and Symbolic Pauli Gates
• On the complexity of quantum partition functions
• Depth optimization of CZ, CNOT, and Clifford circuits
• A single $T$-gate makes distribution learning hard
• Synthesis of and compilation with time-optimal multi-qubit gates
• Enumerating all bilocal Clifford distillation protocols through symmetry reduction
• Constant-cost implementations of Clifford operations and multiply controlled gates using global interactions
• 6-qubit Optimal Clifford Circuits
• A Practical Introduction to Benchmarking and Characterization of Quantum Computers
• Benchmarking the performance of quantum computing software
• Stabilizer Tensor Networks with Magic State Injection
• Architecture aware compilation of quantum circuits via lazy synthesis
• Near-term $n$ to $k$ distillation protocols using graph codes
• Spectral Properties Versus Magic Generation in $T$-doped Random Clifford Circuits
• The Classification of Clifford Gates over Qubits
• Efficient learning of $t$-doped stabilizer states with single-copy measurements
• No-Go Theorems for Universal Entanglement Purification
• Neural-Shadow Quantum State Tomography
• Improved simulation of quantum circuits dominated by free fermionic operations
• Fully scalable randomized benchmarking without motion reversal
• CNOT circuits need little help to implement arbitrary Hadamard-free Clifford transformations they generate
• Clifford Group and Unitary Designs under Symmetry
• Absence of localization in two-dimensional Clifford circuits
• Synthesis of CNOT-Dihedral circuits with optimal number of two qubit gates
• Accelerating Quantum Algorithms with Precomputation
• Qudit Shadow Estimation Based on the Clifford Group and the Power of a Single Magic Gate
• Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates
• The qudit Pauli group: non-commuting pairs, non-commuting sets, and structure theorems
• Designs from magic-augmented Clifford circuits
• Learning to rank quantum circuits for hardware-optimized performance enhancement
• Generators and Relations for Real Stabilizer Operators
• Symbolic Synthesis of Clifford Circuits and Beyond
• Local spreading of stabilizer Rényi entropy in a brickwork random Clifford circuit
• Hamiltonian Learning via Shadow Tomography of Pseudo-Choi States
• Extending Classically Simulatable Bounds of Clifford Circuits with Nonstabilizer States via Framed Wigner Functions
• Randomized measurements for multi-parameter quantum metrology
• Solvable Quantum Circuits in Tree+1 Dimensions
• A Rubik's Cube inspired approach to Clifford synthesis
• Time-optimal multi-qubit gates: Complexity, efficient heuristic and gate-time bounds
• Architectures and random properties of symplectic quantum circuits
• A Theory of Direct Randomized Benchmarking
• Quantum noise modeling through Reinforcement Learning
• A quantum computing approach to fixed-node Monte Carlo using classical shadows
• Entanglement spectrum of matchgate circuits with universal and non-universal resources
• Single-copy stabilizer testing
• Multipartite Greenberger-Horne-Zeilinger Entanglement in Monitored Random Clifford Circuits
• Q-fid: Quantum Circuit Fidelity Improvement with LSTM Networks
• Resource-efficient shadow tomography using equatorial stabilizer measurements
• A graph-state based synthesis framework for Clifford isometries
• Model validation and error attribution for a drifting qubit
• Anticoncentration in Clifford Circuits and Beyond: From Random Tensor Networks to Pseudo-Magic States
• Optimal quantum reservoir learning in proximity to universality
• Optimal randomized measurements for a family of non-linear quantum properties
• High-expressibility Quantum Neural Networks using only classical resources
• Approximate Quantum Error Correction with 1D Log-Depth Circuits
• Limits of Clifford Disentangling in Tensor Network States
• Computable and noncomputable in the quantum domain: statements and conjectures
• Nonunitary gates using measurements only
• Optimized Clifford Noise Reduction: Theory, Simulations and Experiments