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. Over all linear reversible circuits with \(n = 3, 4, 5\) qubits, our lower bound is optimal for exactly 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.
