Quantum computing · Theory and numerical analysis
Meet-in-the-Middle Compilation of the [CNOT] Class with Fibonacci Anyons
arXiv:2610.37552v1 ↗PDF ↗Submitted 27 October 2026
- Question
- Two qubits encoded in six Fibonacci anyons live in a five-dimensional fusion space, one dimension more than two qubits need. The only exchange that entangles the qubits, \(\sigma_3\), is also the only one that couples them to the fifth, noncomputational state, so every entangling braid leaks. How small can the leakage of a braid equivalent to CNOT up to single-qubit gates be at a given length, and is exhaustive search better than random sampling?
- Result
- A GPU meet-in-the-middle search over all \(5^{21}\) positive words finds at length 21 a braid with leakage \(\ell=3.95\times10^{-3}\) and distance \(7.8\times10^{-9}\) to the CNOT class, less leakage than the best previously sampled braid of length 39. Restricting to \(\{\sigma_1,\sigma_2,\sigma_3\}\), to words starting and ending with \(\sigma_3\), to palindromes and to Garside normal forms extends exhaustive search to length 72; at length 69 it finds \(\ell=8.8\times10^{-11}\) with distance \(4.3\times10^{-10}\). The paper proves that leakage lies in \(\mathbb Z[\varphi]\) and that any nonzero leakage satisfies \(\ell\ge1/(1+C^{2L})\) with \(C\approx2.89\), and that for long random words the leakage distribution tends to \(\ell^{d-1}\).
The paper in detail
Fibonacci anyons have one nontrivial particle \(\tau\) with \(\tau\times\tau=\mathbf 1+\tau\). Six of them with total charge \(\mathbf 1\) have a five-dimensional fusion space, ordered here as \(\{\ket{\rm NC},\ket{11},\ket{1\tau},\ket{\tau1},\ket{\tau\tau}\}\). The exchanges \(\sigma_1,\sigma_2\) act on the first qubit, \(\sigma_4,\sigma_5\) on the second, and \(\sigma_3\) mixes \(\ket{\rm NC}\) with \(\ket{\tau\tau}\) through the entry \(\varphi^{-1/2}e^{-3\pi i/5}\). For a braid matrix \(U\), leakage out of the computational block is \(\ell(U)=1-|U_{00}|^2\), and closeness to the CNOT class is measured with the Makhlin invariants \((G_1,G_2)\), which equal \((0,1)\) on the class, through \(d=|G_1|^2+|G_2-1|^2\).
Leakage needs only one matrix element. Splitting a word into halves, \((U_2U_1)_{00}=\sum_i(U_2)_{0i}(U_1)_{i0}\), so the leakage of all \(q^L\) words follows from a single matrix product of a table of \(q^{L/2}\) rows by a table of \(q^{L/2}\) columns, executed as batched GPU matrix multiplication. Only words below an adaptive threshold \(\ell<4b_{L-1}\) (four times the previous record) go on to the expensive invariant computation and an exact check. Appending a leakage-free generator keeps the record, so the threshold never discards the optimum.
The search space then shrinks in steps: \(5^L\to3^L\) by using only \(\{\sigma_1,\sigma_2,\sigma_3\}\) (the records at lengths 20 and 21 already have this form), \(3^{L-2}\) by fixing \(\sigma_3\) at both ends, \(3^{L/2}\) by palindromes \(AMA^R\) (all generators are symmetric matrices, so \(U(AMA^R)=U(A)^{\mathsf T}U(M)U(A)\)), and finally \(\rho^{L/2}\) with \(\rho\approx2.0868\) by enumerating each half once in Garside left normal form. Records include \(\ell=6.6\times10^{-5}\) at length 31, \(5.4\times10^{-7}\) at 42 with \(d=4.1\times10^{-12}\), and \(2.1\times10^{-10}\) at 64, fitted by \(\ell_{\rm fit}=\sqrt5\cdot10^{1-L/6}\).
Two theoretical results frame the numbers. Leakage is an algebraic integer in \(\mathbb Z[\varphi]\), and a Galois conjugate bounds it away from zero at fixed length. For long uniformly random words, the braid matrix becomes Haar-distributed on the invariant subspace containing \(\ket{\rm NC}\), of dimension \(d=3\) for three generators and \(d=5\) for five, so \(\Pr(\ell<\ell_0)\to\ell_0^{d-1}\). Reaching leakage \(\ell_L\) by sampling then needs at least about \(\ell_L^{1-d}\) samples, while the palindromic exhaustive search costs about \(\ell_L^{-3\log_{10}3}\approx\ell_L^{-1.43}\) under the fitted decay. Explaining the generator and palindrome reductions, and finding analytic structure in the optimal braids, is left open.
Transferable methods
Galois-conjugate lower bound on an algebraic quantity
If a quantity is an algebraic integer, it cannot be smaller in absolute value than one over its conjugates, because their product is a nonzero integer. Bounding the conjugate by the norms of conjugated generator matrices gives an explicit floor that grows only exponentially with braid length.
With \(\varphi^{-1}=\varphi-1\) and \(\varphi^{-1/2}=\sqrt\varphi(\varphi-1)\), every generator entry lies in \(\mathbb Z[\zeta_5,\sqrt\varphi]\). Grading basis states by \(\gamma=(1,0,1,1,0)\), entries with \(\gamma(k)+\gamma(l)\) even lie in \(\mathbb Z[\zeta_5]\) and those with odd sum in \(\sqrt\varphi\,\mathbb Z[\zeta_5]\); since \(\gamma(k)+2\gamma(m)+\gamma(l)\equiv\gamma(k)+\gamma(l)\), products keep the grading and \(U_{00}\in\mathbb Z[\zeta_5]\). Hence \(|U_{00}|^2\in\mathbb Z[\zeta_5]\cap\mathbb R=\mathbb Z[\varphi]\) and \(\ell=(a+b\sqrt5)/2\) with integers \(a\equiv b\pmod 2\).
The embedding \(g\) with \(g(\zeta_5)=\zeta_5^2\) and \(g(\sqrt\varphi)=i/\sqrt\varphi\) sends \(\sqrt5\mapsto-\sqrt5\). If \(\ell>0\), its norm \(\ell\,g(\ell)=(a^2-5b^2)/4\) is a nonzero integer, so \(\ell\ge1/|g(\ell)|\). Because \(g\) commutes with complex conjugation on \(\mathbb Q(\zeta_5)\) and preserves products, \(|g(U_{00})|\le\prod_s\lVert\sigma_{i_s}^g\rVert\le C^L\), and
\[\ell(U)\ge\frac{1}{1+C^{2L}},\qquad C=\max_j\lVert\sigma_j^g\rVert=2.8901\ldots\] Editorial check: rebuilding the five generators from the paper’s matrices (they satisfy the braid relations) and the conjugated ones (\(e^{i\pi k/5}\mapsto e^{7i\pi k/5}\), \(\varphi^{-1}\mapsto-\varphi\), \(\varphi^{-1/2}\mapsto-i\sqrt\varphi\)) reproduces \(C=2.89005\) and the published \(\ell\) and \(d\) of the records at lengths 21, 23, 31, 42 and 64. The length-21 record has \(\ell=(-10391+4647\sqrt5)/2\) with norm \(-41\), and all five records give integer norms (\(-41,-81,-121,-1780,-245\)) up to floating-point error. The bound is far from tight: \(4.4\times10^{-20}\) at length 21 against \(3.9\times10^{-3}\).
How to reuse it
Whenever gates come from a finite set of matrices with entries in a number field, as for Clifford+T, metaplectic or other anyon gate sets, quantities such as leakage, gate infidelity or a target matrix element are algebraic, and Galois conjugation gives a length-dependent floor for free. The grading trick, tracking which entries carry an odd power of a square root, is how to show the quantity lies in the smaller ring.
Haar limit of one matrix element and the cost of sampling
For long random words, the braid group acts as a Haar-random unitary on the invariant subspace containing the leaky state. The distribution of one diagonal element is then known exactly, which turns the question “how often does a random braid leak less than \(\ell\)?” into a power law.
A Haar-random unit vector in \(\mathbb C^d\) is \(u=g/\lVert g\rVert\) with independent complex Gaussians \(g_k\); the \(|g_k|^2\) are independent exponentials, so \(X=|u_0|^2\) is Beta\((1,d-1)\)-distributed with density \((d-1)(1-x)^{d-2}\). Then \(\Pr(1-X<\ell)=\int_{1-\ell}^1(d-1)(1-x)^{d-2}dx=\ell^{d-1}\). The relevant \(d\) is the dimension of the orbit of \(\ket{\rm NC}\): \(\sigma_3\) links it to \(\ket{\tau\tau}\), \(\sigma_2\) links \(\ket{\tau\tau}\) to \(\ket{1\tau}\), and \(\sigma_1\) is diagonal, so \(d=3\) for \(\{\sigma_1,\sigma_2,\sigma_3\}\), while \(\sigma_4\) brings in the remaining two states and \(d=5\) for all five generators. The paper proves convergence of long positive random words to this limit using density of the Jones representation and the Kawada–Itô theorem.
To hit \(\ell<\ell_L\) with probability \(\tfrac12\), sampling needs \(n\ge-1/\log_2(1-\ell_L^{d-1})\approx\ell_L^{1-d}/\ln 2\) draws. Exhaustive palindromic search costs \(\sqrt3^{\,L}\), and with the fitted record \(L\approx-6\log_{10}\ell_L+{\rm const}\) this is \(\ell_L^{-3\log_{10}3}=\ell_L^{-1.431}\), better than \(\ell_L^{-2}\) (\(d=3\)) and \(\ell_L^{-4}\) (\(d=5\)). Editorial note: the exhaustive estimate inherits the empirical decay \(\ell\sim10^{-L/6}\), and the sampling estimate counts only low-leakage hits, not closeness to the CNOT class, so it is a lower bound on sampling cost.
How to reuse it
For any compilation problem where one constraint is a single matrix element of a product (leakage, a target overlap, a return probability), the Beta\((1,d-1)\) law predicts how rare good random words are, and the meet-in-the-middle identity \((U_2U_1)_{00}=\mathrm{row}_0(U_2)\cdot\mathrm{col}_0(U_1)\) makes exhaustive screening a single dense matrix multiplication. Compare \(\ell^{1-d}\) with the growth of a structured search before investing in sampling.
Context & limitations
Why it matters. It gives braids with proven optimality inside explicitly defined families, rather than heuristic best finds. The record leakage falls roughly as \(10^{-L/6}\). The limit law explains why random sampling becomes hopeless at small leakage, since its cost grows as \(\ell^{1-d}\), faster than structured exhaustive search.
Limitations. Optimality holds only within the chosen families. The reduction to three generators is empirical, and the palindromic family is not shown to contain global optima. Whether braiding alone can give an exactly leakage-free entangling gate remains open. The proven lower bound is extremely loose (about \(10^{-20}\) at length 21 against an actual \(4\times10^{-3}\)). The comparison with sampling extrapolates an empirical fit. Only positive words are searched, and the searches took about 1000 V100 GPU hours.