Hadamard-free circuits expose the structure of the Clifford group

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.