CNOT circuits need little help to implement arbitrary Hadamard-free Clifford transformations they generate

A Hadamard-free Clifford transformation is a circuit composed of quantum Phase (P), CZ, and CNOT gates. It is known that such a circuit can be written as a three-stage computation, -P-CZ-CNOT-, where each stage consists only of gates of the specified type. In this paper, we focus on the minimization of circuit depth by entangling gates, corresponding to the important time-to-solution metric and the reduction of noise due to decoherence. We consider two popular connectivity maps: Linear Nearest Neighbor (LNN) and all-to-all. First, we show that a Hadamard-free Clifford operation can be implemented over LNN in depth 5n, i.e., in the same depth as the -CNOT- stage alone. This allows us to implement arbitrary Clifford transformation over LNN in depth no more than 7n − 4, improving the best previous upper bound of 9n. Second, we report heuristic evidence that on average a random uniformly distributed Hadamard-free Clifford transformation over n > 6 qubits can be implemented with only a tiny additive overhead over all-to-all connected architecture compared to the best-known depth-optimized implementation of the -CNOT- stage alone. This suggests the reduction of the depth of Clifford circuits from 2n+O(log2(n)) to 1.5n+O(log2(n)) over unrestricted architectures.