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

Abstract

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.

References in corpus (12)

• Mixed State Entanglement and Quantum Error Correction
• Improved Simulation of Stabilizer Circuits
• Universal Quantum Computation with ideal Clifford gates and noisy ancillas
• Randomized Benchmarking of Quantum Gates
• Robust randomized benchmarking of quantum processes
• Experimental Comparison of Two Quantum Computing Architectures
• Graph-theoretic Simplification of Quantum Circuits with the ZX-calculus
• Hadamard-free circuits expose the structure of the Clifford group
• Shorter stabilizer circuits via Bruhat decomposition and quantum circuit transformations
• Shorter gate sequences for quantum computing by mixing unitaries
• Reducing the Depth of Linear Reversible Quantum Circuits
• Depth optimization of CZ, CNOT, and Clifford circuits

Cited by in corpus (4)

• Approximate complex amplitude encoding algorithm and its application to data classification problems
• Resource-efficient shadow tomography using equatorial stabilizer measurements
• A graph-state based synthesis framework for Clifford isometries
• Limits of Clifford Disentangling in Tensor Network States