A heuristic to reduce π/4-phase-parity circuits

Niel De Beaudrap (University of Oxford), Quanlong Wang (University of Oxford)

To approximate arbitrary unitary transformations on one or more qubits, one must perform transformations which are outside of the Clifford group, which is only a discrete set of transformations. The gate most commonly considered for this purpose is the T = diag(1,exp(iπ/4)) gate. As T gates are computationally expensive to perform fault-tolerantly in the most promising error-correction technologies, minimising the “T count” (the number of T gates) required to realise a given unitary in a Clifford+T circuit is of great interest. Following Heyfron and Campbell [arXiv:1712.01557], one can transform the circuit into a form involving a CNOT+T circuit, followed by rounds of Pauli measurements and classically controlled Clifford gates. One may further transform the CNOT+T portion into a CNOT circuit, followed by a product of “π/4-parity-phase” operations: diagonal unitary transformations which induce a relative phase of exp(iπ/4) depending on the outcome of a parity computation on the standard basis (which the “phase gadgets” of Kissinger and van de Wetering [arXiv:1903.10477] can easily represent). We present a heuristic technique to simplify circuits of π/4-parity-phase operations, based on simple identities for such operations. This results in a corresponding reduction of the T-count to realise a unitary circuit. These techniques can be extended to reduce non-Clifford phase gates at various levels of the Clifford hierarchy, by simplifying “π/2^k-parity-phase” operations for non-negative integers k.