On Exact Sizes of Minimal CNOT Circuits

Computing a minimum-size circuit that implements a certain function is a standard optimization task. We consider circuits of CNOT gates, which are fundamental binary gates in reversible and quantum computing. Algebraically, CNOT circuits on n qubits correspond to GL (n, 2), the general linear group over the field of two elements, and circuit minimization reduces to computing distances in the Cayley graph Gₙ of GL (n, 2) generated by transvections. However, the super-exponential size of GL (n, 2) has made its exploration computationally challenging. In this paper, we develop a new approach for computing distances in Gₙ, allowing us to synthesize minimum circuits that were previously beyond reach (e. g. , we can synthesize optimally all circuits over n=7 qubits). Towards this, we establish two theoretical results that may be of independent interest. First, we give a complete characterization of all isometries in Gₙ in terms of (i) permuting qubits and (ii) swapping the arguments of all CNOT gates. Second, for any fixed d, we establish polynomials in n of degree 2d that characterize the size of spheres in Gₙ at distance d, as long as n 2d. With these tools, we revisit an open question of Bataille, 2022 regarding the smallest number n₀ for which the diameter of G₍䃐 exceeds 3 (n₀-1). It was previously shown that 6 n₀ 30, a gap that we tighten considerably to 8 n₀ 20. We also confirm a conjecture that long cycle permutations lie at distance 3 (n-1), for all n 8, extending the previous bound of n 5.