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 (4)

• Predicting Many Properties of a Quantum System from Very Few Measurements
• Randomized Benchmarking of Quantum Gates
• Robust randomized benchmarking of quantum processes
• Entanglement renormalization and topological order

Cited by in corpus (69)

• 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
• A Practical Introduction to Benchmarking and Characterization of Quantum Computers
• 6-qubit Optimal Clifford Circuits
• 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
• No-Go Theorems for Universal Entanglement Purification
• Efficient learning of $t$-doped stabilizer states with single-copy measurements
• Neural-Shadow Quantum State Tomography
• Fully scalable randomized benchmarking without motion reversal
• Improved simulation of quantum circuits dominated by free fermionic operations
• Clifford Group and Unitary Designs under Symmetry
• CNOT circuits need little help to implement arbitrary Hadamard-free Clifford transformations they generate
• 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
• Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates
• Qudit Shadow Estimation Based on the Clifford Group and the Power of a Single Magic Gate
• 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
• Solvable Quantum Circuits in Tree+1 Dimensions
• Randomized measurements for multi-parameter quantum metrology
• A quantum computing approach to fixed-node Monte Carlo using classical shadows
• Single-copy stabilizer testing
• Quantum noise modeling through Reinforcement Learning
• Architectures and random properties of symplectic quantum circuits
• Entanglement spectrum of matchgate circuits with universal and non-universal resources
• A Rubik's Cube inspired approach to Clifford synthesis
• Time-optimal multi-qubit gates: Complexity, efficient heuristic and gate-time bounds
• A Theory of Direct Randomized Benchmarking
• Q-fid: Quantum Circuit Fidelity Improvement with LSTM Networks
• Multipartite Greenberger-Horne-Zeilinger Entanglement in Monitored Random Clifford Circuits
• A graph-state based synthesis framework for Clifford isometries
• Resource-efficient shadow tomography using equatorial stabilizer measurements
• 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
• Limits of Clifford Disentangling in Tensor Network States
• Approximate Quantum Error Correction with 1D Log-Depth Circuits
• Optimized Clifford Noise Reduction: Theory, Simulations and Experiments
• Optimal randomized measurements for a family of non-linear quantum properties
• Computable and noncomputable in the quantum domain: statements and conjectures
• Nonunitary gates using measurements only
• High-expressibility Quantum Neural Networks using only classical resources