  The Clifford group is a finite subgroup of the unitary group generated by the
Hadamard, the CNOT, and the Phase gates. This group plays a prominent role in
quantum error correction, randomized benchmarking protocols, and the study of
entanglement. Here we consider the problem of finding a short quantum circuit
implementing a given Clifford group element. Our methods aim to minimize the
entangling gate count assuming all-to-all qubit connectivity. First, we
consider circuit optimization based on template matching and design
Clifford-specific templates that leverage the ability to factor out Pauli and
SWAP gates. Second, we introduce a symbolic peephole optimization method. It
works by projecting the full circuit onto a small subset of qubits and
optimally recompiling the projected subcircuit via dynamic programming. CNOT
gates coupling the chosen subset of qubits with the remaining qubits are
expressed using symbolic Pauli gates. Software implementation of these methods
finds circuits that are only 0.2% away from optimal for 6 qubits and reduces
the two-qubit gate count in circuits with up to 64 qubits by 64.7% on average,
compared with the Aaronson-Gottesman canonical form.
