Strong matchgate designs in nearly optimal depth
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 G of routing number rt(G). Indeed, in this setting one can obtain (strong) ε-approximate relative error matchgate k-designs in depth 𝒪(k2rt(G)log nlog(n/ε)). For all-to-all connectivity, rt(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 𝒪(rt(G)log n) depth router. Additionally, for k=3, we obtain an exact strong matchgate design in 𝒪(rt(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.
Related
- Unitary Designs from Doped Matchgate Circuits
- Complexity separations for optimal matchgate-Clifford synthesis
- Ultra-Precise Quantum Projective Designs in Constant Depth
- Strong-deflection scaling in nearly symmetric thin-shell wormholes
- Nearly Optimal Quantum Sample Complexity of Learning Fourier-Sparse Boolean Functions
BibTeX
@misc{west2026strong,
title = {{Strong matchgate designs in nearly optimal depth}},
author = {Maxwell West and M. Cerezo and Martin Larocca},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.26677},
eprint = {2609.26677},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.26677},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Strong matchgate designs in nearly optimal depth
AU - Maxwell West
AU - M. Cerezo
AU - Martin Larocca
PY - 2026
DA - 2026/09/22
PB - arXiv
DO - 10.48550/arxiv.2609.26677
UR - https://arxiv.org/abs/2609.26677
AB - 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 G of routing number rt(G). Indeed, in this setting one can obtain (strong) ε-approximate relative error matchgate k-designs in depth 𝒪(k^2rt(G)log nlog(n/ε)). For all-to-all connectivity, rt(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 𝒪(rt(G)log n) depth router. Additionally, for k=3, we obtain an exact strong matchgate design in 𝒪(rt(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.
ER -