arXiv:2609.26677
Strong matchgate designs in nearly optimal depth
Maxwell West, M. Cerezo, Martin Larocca
Abstract
Understanding the resources required to generate approximately random unitaries over various groups is a natural goal of quantum information theory. With respect to one notion of approximation, that of a design, it is known that the full unitary group can be approximated in logarithmic depth by one-dimensional circuits of nearest-neighbour 2-local gates. On the other hand, remarkably, circuits with this connectivity cannot form designs over the matchgate group in sublinear depth. Here we show that this dramatic slowdown can disappear when using a general qubit connectivity graph $\mathsf{G}$ of routing number ${\rm rt}(\mathsf{G})$. Indeed, in this setting one can obtain (strong) $\varepsilon$-approximate relative error matchgate $k$-designs in depth $\mathcal{O}(k^2{\rm rt}(\mathsf{G})\log n\log(n/\varepsilon))$. For all-to-all connectivity, ${\rm rt}(\mathsf{G})=2$. Our construction is conceptually simple, involving a random walk on the matchgate group, and no ancillae. As a technical byproduct, we improve upon the state of the art for fermionic routing, obtaining an $\mathcal{O}({\rm rt}(\mathsf{G})\log n)$ depth router. Additionally, for $k=3$, we obtain an exact strong matchgate design in $\mathcal{O}({\rm rt}(\mathsf{G})\log n)$ depth, again without ancillae. Under all-to-all connectivity, our fermionic router and 3-designs are optimal. Notably, our results imply that quantum algorithms for fermionic tomography which require drawing from a matchgate 3-design may be exponentially sped up on quantum computers with all-to-all connectivity, relative to their strictly one-dimensional counterparts.
AI Summary
The paper asks whether the linear-depth obstruction to matchgate designs on one-dimensional nearest-neighbour architectures disappears with more general connectivity. For an $n$-qubit connectivity graph $\mathsf G$ with routing number ${\rm rt}(\mathsf G)$, it constructs strong $\varepsilon$-approximate relative-error matchgate $k$-designs with depth $O(k^2{\rm rt}(\mathsf G)\log n\log(n/\varepsilon))$, without ancillas. All-to-all connectivity has routing number two, giving polylogarithmic depth for fixed $k$ and $\varepsilon$. The construction starts with $O(k^2n\log(n/\varepsilon))$ random two-Majorana rotations. Representation-theoretic bounds using the quadratic Casimir control convergence of their moments in relative error. A probabilistic dependency-chain argument bounds parallel depth; rejecting walks that are too deep and concatenating two independently accepted walks preserves the design guarantee. Each fermionic layer is compiled into physical two-qubit gates using an ancilla-free Clifford router for arbitrary signed Majorana permutations, with depth $O({\rm rt}(\mathsf G)\log n)$. Combining this router with a known exact design ensemble gives exact strong matchgate 3-designs at the same routing depth. Both routing and these designs attain optimal $\Theta(\log n)$ depth under all-to-all connectivity. This reduces the circuit-depth cost of design sampling for applications such as fermionic classical shadows. For general $k>3$, a logarithmic gap in $n$ remains against the lightcone lower bound. A separate rank argument gives an ancilla-free relative-error depth lower bound $\Omega(k/\log(nk))$ for $1\leq k\leq n$; near $k=n$, the connectivity advantage is at most logarithmic. Efficient compilation is established for all-to-all connectivity.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.