Hadamard-free circuits expose the structure of the Clifford group
Authors:
Preprint
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_1HSF_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.
Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- Predicting many properties of a quantum system from very few measurementsNature Physics, 2020
- Multiqubit Clifford groups are unitary 3-designsPhysical Review A, 2017
- How to efficiently select an arbitrary Clifford group elementJournal of Mathematical Physics, 2014
- Bifurcation in entanglement renormalization group flow of a gapped spin modelPhysical Review B, 2014
- Entanglement Renormalization and Topological OrderPhysical Review Letters, 2008
- Randomized benchmarking of quantum gatesPhysical Review A, 2008
- Scalable noise estimation with random unitary operatorsJournal of Optics B: Quantum and Semiclassical Optics, 2005
- Universal quantum computation with ideal Clifford gates and noisy ancillasPhysical Review A, 2005
- Improved simulation of stabilizer circuitsPhysical Review A, 2004
- Efficient generation of random nonsingular matricesRandom Structures & Algorithms, 1993