Kaoutar El Maghraoui, Gokul Kandiraju, et al.
WOSP/SIPEW 2010
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.
Kaoutar El Maghraoui, Gokul Kandiraju, et al.
WOSP/SIPEW 2010
Maurice Hanan, Peter K. Wolff, et al.
DAC 1976
Yvonne Anne Pignolet, Stefan Schmid, et al.
Discrete Mathematics and Theoretical Computer Science
Rajiv Ramaswami, Kumar N. Sivarajan
IEEE/ACM Transactions on Networking