标题： 关于最小CNOT电路的确切大小 显示英文标题

标题： On Exact Sizes of Minimal CNOT Circuits

摘要： 计算实现某一特定函数的最小尺寸电路是一项标准的优化任务。 我们研究了CNOT门组成的电路，这些门是可逆和量子计算中的基本二进制门。 从代数角度来看， $n$量子比特上的CNOT电路对应于$GL(n,2)$（两个元素域上的广义线性群），而电路最小化可以归结为计算由换位生成的$GL(n,2)$的Cayley图$G_n$中的距离。 然而，$GL(n,2)$的超指数级大小使得对其探索在计算上极具挑战性。 本文提出了一种新的方法来计算$G_n$中的距离，使我们能够合成之前无法触及的最小电路（例如，我们可以对所有$n=7$量子比特上的电路进行最优合成）。 为此，我们建立了两个可能具有独立兴趣的理论成果。 首先，我们通过以下两种方式给出了 $G_n$ 中所有等距变换的完整刻画：(i) 对量子位进行置换；(ii) 交换所有 CNOT 门的参数。 其次，对于任意固定的 $d$，我们构建了 $n$ 中次数为 $2d$ 的多项式，这些多项式刻画了 $G_n$ 中距离为 $d$ 的球体的大小，只要 $n\geq 2d$。 利用这些工具，我们重新审视了[Bataille, 2022] 中的一个开放问题，即使得 $n_0$ 的直径超过 $G_{n_0}$ 的最小数 $3(n_0-1)$。 此前已证明 $6\leq n_0 \leq 30$，我们显著缩小了这一差距至 $8\leq n_0 \leq 20$。 我们还证实了一个猜想，即长循环置换的距离为 $3(n-1)$，对于所有的 $n\leq 8$，扩展了之前 $n\leq 5$ 的界限。 显示英文摘要

摘要： 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_n$ 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_n$, 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_n$ 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_n$ at distance $d$, as long as $n\geq 2d$. With these tools, we revisit an open question of [Bataille, 2022] regarding the smallest number $n_0$ for which the diameter of $G_{n_0}$ exceeds $3(n_0-1)$. It was previously shown that $6\leq n_0 \leq 30$, a gap that we tighten considerably to $8\leq n_0 \leq 20$. We also confirm a conjecture that long cycle permutations lie at distance $3(n-1)$, for all $n\leq 8$, extending the previous bound of $n\leq 5$.