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

• Published in: arXiv.org 2023-01
• Main Authors: Maslov, Dmitri, Willers Yang
• Format: Article
• Language: English
• Subjects: Gates (circuits); Qubits (quantum computing); Transformations; Upper bounds
• ISSN: 2331-8422
• DOI: 10.48550/arxiv.2210.16195

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(\log^2(n))\) to \(1.5n\,{+}\,O(\log^2(n))\) over unrestricted architectures.