Meet-in-the-Middle Compilation of the $[\mathrm{CNOT}]$ Class with Fibonacci Anyons

Abstract

Compilation of two-qubit Fibonacci anyon gates is complicated by leakage ($\ell$) from the four-dimensional computational sector to the fifth state of the fusion space. We construct a GPU pipeline to find low-leakage representatives of the $[\text{CNOT}]$ class on different subsets of the braid group. We exhaustively explore the full positive five-generator alphabet up to $L=21$ with minimal leakage $\ell\sim10^{-3}$ and error $d_{[\text{CNOT}]}\sim 10^{-8}$ on it. To reach larger lengths, the search space is successively narrowed to three-generator, boundary-$σ_3$, and palindromic braids, and by considering only the Garside left normal form. These optimizations allow us to reach $L=72$. For $L=69$, a braid with $\ell\sim10^{-10}$ and $d_{[\text{CNOT}]}\sim 10^{-10}$ is found. In addition to directly enumerating optimal braids, we proved that $\ell\in\mathbb Z[\varphi]$, and any nonzero leakage obeys an exponential lower bound in the braid length, and obtained the limit laws $F_{3,\infty}(\ell)=\ell^2$ and $F_{5,\infty}(\ell)=\ell^4$ for our sets. Using asymptotics for the distribution function $F$, we showed that for sufficiently long braids, the asymptotics of exhaustive search are better than the asymptotics of random sampling for finding low-leakage braids.

The paper studies compilation of two-qubit gates locally equivalent to CNOT in the six-Fibonacci-anyon encoding, where a fifth fusion-space state causes leakage. It searches positive braid words, optimizing leakage $\ell=1-|U_{00}|^2$ together with a Makhlin-invariant deviation $d_{[\mathrm{CNOT}]}$. A GPU pipeline splits words into halves and evaluates the leakage-determining amplitude using batched row–column products; full computational blocks and invariants are reconstructed only for filtered candidates. This retains exponential enumeration time rather than providing a collision-based meet-in-the-middle speedup. Full five-generator enumeration reaches $L=21$, yielding $\ell=3.946\times10^{-3}$ and $d=7.779\times10^{-9}$ for the composite-score optimum. Successively restricting to three generators, fixed boundary generators, and palindromes, then removing duplicate halves using Garside normal forms, extends searches to $L=72$. At $L=69$, a candidate has $\ell=8.784\times10^{-11}$ and $d=4.26\times10^{-10}$; candidate leakage values are verified algebraically. The paper proves $\ell\in\mathbb Z[\varphi]$ and, for nonzero leakage at length $L$, $\ell\ge(1+C^{2L})^{-1}$ with $C\approx2.8901$. Projective braid-image density, compact-group random-walk convergence, and Haar matrix-element statistics establish fixed-threshold limiting leakage CDFs $F_{3,\infty}(\ell)=\ell^2$ and $F_{5,\infty}(\ell)=\ell^4$. Optimality claims apply only within the specified search families and objectives; alphabet and palindrome restrictions are empirically motivated, not proved lossless. The claimed asymptotic advantage over random sampling additionally uses an empirical record-leakage scaling and lacks mixing estimates for jointly increasing length and decreasing threshold. Exactly leakage-free entangling braids remain unresolved.