Minimum Synthesis Cost of CNOT Circuits

Abstract

Optimizing the size and depth of CNOT circuits is an active area of research in quantum computing and is particularly relevant for circuits synthesized from the Clifford + T universal gate set. Although many techniques exist for finding short syntheses, it is difficult to assess how close to optimal these syntheses are without an exponential brute-force search. We use a novel method of categorizing CNOT gates in a synthesis to obtain a strict lower bound computable in $O(n^{\omega })$ time on the minimum number of gates needed to synthesize a given CNOT circuit, where $\omega$ denotes the matrix multiplication constant and $n$ is the number of qubits involved. Applying our framework, we prove that $3(n-1)$ gate syntheses of the $n$-cycle circuit are optimal and provide insight into their structure. We also generalize this result to permutation circuits. For linear reversible circuits with $n=3,4,5$ qubits, our lower bound is optimal for 100%, 67.7%, and 23.1% of circuits and is accurate to within one CNOT gate in 100%, 99.5%, and 83.0% of circuits respectively. We also introduce an algorithm that efficiently determines whether certain circuits can be synthesized with fewer than $n$ CNOT gates.

arXiv comment14 pages, 12 figures

References in corpus (13)

• Elementary gates for quantum computation
• Two-Bit Gates are Universal for Quantum Computation
• High-fidelity two-qubit quantum logic gates using trapped calcium-43 ions
• High-fidelity quantum logic gates using trapped-ion hyperfine qubits
• High-fidelity preparation, gates, memory and readout of a trapped-ion quantum bit
• Optimal Quantum Circuits for General Two-Qubit Gates
• Two-qubit silicon quantum processor with operation fidelity exceeding 99%
• Efficient decomposition of quantum gates
• Implementation of Grover's Quantum Search Algorithm in a Scalable System
• Quantum circuit optimizations for NISQ architectures
• On the CNOT-complexity of CNOT-PHASE circuits
• Depth optimization of CZ, CNOT, and Clifford circuits
• Minimizing CNOT-count in quantum circuit of the extended Shor's algorithm for ECDLP