2025/03/03 by Jens Christensen, Christensen, Jens Emil, Jørgensen, Søren Fuglede +4 · 3 citations
Computer Science · Engineering · #Advanced Memory and Neural Computing #Advancements in Semiconductor Devices and Circuit Design #FOS: Physical sciences #Quantum Physics (quant-ph) #Quantum-Dot Cellular Automata
paper · pdf · doi:10.48550/arxiv.2503.01467
openalex publication_date 2025/03/03 · openalex created_date 2025/10/12 · openalex updated_date 2026/07/28
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 Gn 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 Gn, 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 Gn 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 Gn at distance d, as long as n≥ 2d. With these tools, we revisit an open question of [Bataille, 2022] regarding the smallest number n0 for which the diameter of Gn0 exceeds 3(n0-1). It was previously shown that 6≤ n0 ≤ 30, a gap that we tighten considerably to 8≤ n0 ≤ 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.