Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2609.26677

Strong matchgate designs in nearly optimal depth

Maxwell West, M. Cerezo, Martin Larocca

quant-phSubmitted Sep 22, 2026• Announced Sep 23, 2026• 3 citations
arXivHTMLPDF

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.

No sign of AI-generated text

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Related papers

Ambient unitaries don't enable shallow group designs

Maxwell West, M. Cerezo, Martin Larocca

Characterising the efficiency with which designs over various subsets of the unitary group may be constructed is an important goal of quantum information theory. While it is now known that approximate unitary designs can be realised in depth logarithmic in the system size, it has recently been shown that ensembles of local nearest-neighbour sublinear-depth one-dimensional circuits over the matchgate, orthogonal, and symplectic groups cannot form approximate 2-designs over their parent groups; similarly, sublinear-depth ensembles of Cliffords cannot form a Clifford 4-design. In this note we show that this remarkable exponential separation is not merely an artefact of restricting to ensembles consisting of unitaries from the subgroups themselves, but rather that no ensemble of local nearest-neighbour sublinear-depth unitaries can realise approximate designs in the aforementioned cases, even when employing "ambient" unitaries from beyond the subgroup itself (possibly acting on ancilla qubits). This implies that various natural tomography and benchmarking schemes which involves sampling from these groups suffer from a dramatic circuit depth overhead compared to similar protocols which involve sampling from the full unitary group. We additionally conclude that, in all of the above cases, the known linear-depth design constructions are up to constant factors optimal.

quant-pharXiv:2608.13528•Aug 14, 2026•3 citations

Strong matchgate designs in nearly optimal depth — E8 Intelligence Research

Andrew Stewart Caldin

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 technica Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com

•Nov 10, 2026•0 citations

Arts & crafts: Strong random unitaries and geometric locality

Marten Folkertsma, Lorenzo Grevink, Jonas Helsen +1 more

We study the problem of constructing strong approximate unitary $k$-designs on $D$-dimensional grids (and more generally on Cartesian products of graphs), building on the work of Schuster et al. arXiv:2509.26310 which establishes strong unitary designs in 1D and in all-to-all connectivity. We provide two constructions. The first construction leverages the existing all-to-all connectivity result with general routing theory to provide flexible (but slightly suboptimal) strong $k$-designs in arbitrary connectivities. The second construction is more direct, requires no auxiliaries and has provably optimal depth (in the number of qubits $n$) for $D$-dimensional grids with constant dimension. Combining these techniques also allows us to construct strong pseudorandom unitaries on $D$-dimensional grids with provably optimal depth.

quant-pharXiv:2605.03023•May 6, 2026•5 citations

Low-Depth Random Unitaries without Ancillae

Zhenyu Du, Siyuan Cheng, Xiongfeng Ma

Random unitaries are fundamental to quantum information and many-body physics, with widespread applications ranging from quantum learning and metrology to device benchmarking. A central pursuit is to minimize the space and circuit depth required to generate them. However, existing methods for generating low-depth random unitaries rely heavily on an extensive number of ancillary qubits, imposing severe spatial overhead. In this work, we prove that random unitaries can be generated in optimal depth without ancillae. For multiplicative-error approximate $k$-designs on $n$ qubits, our circuits achieve a depth of $\widetilde{O} (k) (\log n)^{1/δ}$ on $δ$-dimensional architectures and $\widetilde{O}(k) \log \log n$ with all-to-all connectivity. Furthermore, by introducing a general exactification lemma, we lift our construction to optimal-depth exact $k$-designs, yielding an exponential resource reduction over state-of-the-art exact constructions. Our results minimize the space-time costs for a wide range of quantum protocols.

quant-pharXiv:2609.06528•Sep 8, 2026•2 citations

Matchgate synthesis via Clifford matchgates and TTT gates

Berta Casas, Paolo Braccia, Élie Gouzien +2 more

Matchgate unitaries are ubiquitous in quantum computation due to their relation to non-interacting fermions and because they can be used to benchmark quantum computers. Implementing such unitaries on fault-tolerant devices requires first compiling them into a discrete universal gate set, typically Clifford$+T$. Here, we propose a different approach for their synthesis: compile matchgate unitaries using only matchgate gates. To this end, we first show that the matchgate-Clifford group (the intersection of the matchgate and Clifford groups) plus the $\overline{T}$ gate (a $T$ unitary up to a phase) is universal for the matchgate group. Our approach leverages the connection between $n$-qubit matchgate circuits and the standard representation of $\mathbb{SO}(2n)$, which reduces the compilation from $2^n\times 2^n$ unitaries to $2n\times2n$ ones, thus reducing exponentially the size of the target matrix. Moreover, we rigorously show that this scheme is efficient, as an approximation error $\varepsilon_{\mathbb{SO}(2n)}$ incurred in this smaller-dimensional representation translates at most into an $O(n \,\varepsilon_{\mathbb{SO}(2n)})$ error in the exponentially large unitary. In addition, we study the exact version of the matchgate synthesis problem, and we prove that all matchgate unitaries $U$ such that $U\otimes U^*$ has entries in the ring $\mathbb{Z}\big[1/\sqrt 2,i\big]$ can be exactly synthesized by a finite sequence of gates from the matchgate-Clifford$+\overline{T}$ set, without ancillas. We then use this insight to map optimal exact matchgate synthesis to Boolean satisfiability, and compile the circuits that diagonalize the free-fermionic $XX$ Hamiltonian on $n=4,\,8$ qubits.

quant-pharXiv:2602.05425•Feb 6, 2026•7 citations

No-go theorems for sublinear-depth group designs

Maxwell West, Diego García-Martín, N. L. Diaz +2 more

Constructing ensembles of circuits which efficiently approximate the Haar measure over various groups is a fundamental problem in quantum information theory, with breakthrough recent results showing that for the unitary group this can be achieved with depths scaling logarithmically in the system size. Here we prove that, for groups G possessing an invariant state $${G}^{\otimes k}\left\vert \Psi \right\rangle=\left\vert \Psi \right\rangle$$ satisfying certain conditions on its entanglement structure, no subset of G consisting of sublinear-depth one-dimensional circuits with constant-locality gates can form an approximate k-design over G. More generally, on a D-dimensional lattice of side-length n, our results imply that such group designs require depths scaling at least as n1/D. Among other examples, we show that there is a constant separation between the maximum depth and gate counts for which no circuit can approximate even the second moment of random matchgate circuits, and those required to implement the matchgate Haar distribution exactly. Finally, we relax the assumption of working with local gates, and prove the impossibility of obtaining approximate designs over G using any circuit comprised of a sublinear number of gates generated by Pauli strings. Significant effort has been spent to find low-depth constructions of random unitaries that appear Haar-random to a restricted observer, and earlier works showed logarithmic-depth approximate designs over the full unitary group using local random circuits. In this paper, the authors provide a general criterion ruling out shallow designs on a wide variety of groups.

arXiv:2506.16005•Nature Communications•Nov 2, 2026•19 citations
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\mathsf{G}G of routing number rt(G){\rm rt}(\mathsf{G})rt(G). Indeed, in this setting one can obtain (strong) ε\varepsilonε-approximate relative error matchgate kkk-designs in depth O(k2rt(G)log⁡nlog⁡(n/ε))\mathcal{O}(k^2{\rm rt}(\mathsf{G})\log n\log(n/\varepsilon))O(k2rt(G)lognlog(n/ε)). For all-to-all connectivity, rt(G)=2{\rm rt}(\mathsf{G})=2rt(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 O(rt(G)log⁡n)\mathcal{O}({\rm rt}(\mathsf{G})\log n)O(rt(G)logn) depth router. Additionally, for k=3k=3k=3, we obtain an exact strong matchgate design in O(rt(G)log⁡n)\mathcal{O}({\rm rt}(\mathsf{G})\log n)O(rt(G)logn) 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.
The paper asks whether the linear-depth obstruction to matchgate designs on one-dimensional nearest-neighbour architectures disappears with more general connectivity. For an nnn-qubit connectivity graph G\mathsf GG with routing number rt(G){\rm rt}(\mathsf G)rt(G), it constructs strong ε\varepsilonε-approximate relative-error matchgate kkk-designs with depth O(k2rt(G)log⁡nlog⁡(n/ε))O(k^2{\rm rt}(\mathsf G)\log n\log(n/\varepsilon))O(k2rt(G)lognlog(n/ε)), without ancillas. All-to-all connectivity has routing number two, giving polylogarithmic depth for fixed kkk and ε\varepsilonε.
The construction starts with O(k2nlog⁡(n/ε))O(k^2n\log(n/\varepsilon))O(k2nlog(n/ε)) 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(rt(G)log⁡n)O({\rm rt}(\mathsf G)\log n)O(rt(G)logn).
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 Θ(log⁡n)\Theta(\log n)Θ(logn) 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>3k>3k>3, a logarithmic gap in nnn remains against the lightcone lower bound. A separate rank argument gives an ancilla-free relative-error depth lower bound Ω(k/log⁡(nk))\Omega(k/\log(nk))Ω(k/log(nk)) for 1≤k≤n1\leq k\leq n1≤k≤n; near k=nk=nk=n, the connectivity advantage is at most logarithmic. Efficient compilation is established for all-to-all connectivity.
Characterising the efficiency with which designs over various subsets of the unitary group may be constructed is an important goal of quantum information theory. While it is now known that approximate unitary designs can be realised in depth logarithmic in the system size, it has recently been shown that ensembles of local nearest-neighbour sublinear-depth one-dimensional circuits over the matchgate, orthogonal, and symplectic groups cannot form approximate 2-designs over their parent groups; similarly, sublinear-depth ensembles of Cliffords cannot form a Clifford 4-design. In this note we show that this remarkable exponential separation is not merely an artefact of restricting to ensembles consisting of unitaries from the subgroups themselves, but rather that no ensemble of local nearest-neighbour sublinear-depth unitaries can realise approximate designs in the aforementioned cases, even when employing "ambient" unitaries from beyond the subgroup itself (possibly acting on ancilla qubits). This implies that various natural tomography and benchmarking schemes which involves sampling from these groups suffer from a dramatic circuit depth overhead compared to similar protocols which involve sampling from the full unitary group. We additionally conclude that, in all of the above cases, the known linear-depth design constructions are up to constant factors optimal.
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\mathsf{G}G of routing number rt(G){\rm rt}(\mathsf{G})rt(G). Indeed, in this setting one can obtain (strong) ε\varepsilonε-approximate relative error matchgate kkk-designs in depth O(k2rt(G)log⁡nlog⁡(n/ε))\mathcal{O}(k^2{\rm rt}(\mathsf{G})\log n\log(n/\varepsilon))O(k2rt(G)lognlog(n/ε)). For all-to-all connectivity, rt(G)=2{\rm rt}(\mathsf{G})=2rt(G)=2. Our construction is conceptually simple, involving a random walk on the matchgate group, and no ancillae. As a technica Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com
We study the problem of constructing strong approximate unitary kkk-designs on DDD-dimensional grids (and more generally on Cartesian products of graphs), building on the work of Schuster et al. arXiv:2509.26310 which establishes strong unitary designs in 1D and in all-to-all connectivity. We provide two constructions. The first construction leverages the existing all-to-all connectivity result with general routing theory to provide flexible (but slightly suboptimal) strong kkk-designs in arbitrary connectivities. The second construction is more direct, requires no auxiliaries and has provably optimal depth (in the number of qubits nnn) for DDD-dimensional grids with constant dimension. Combining these techniques also allows us to construct strong pseudorandom unitaries on DDD-dimensional grids with provably optimal depth.
Random unitaries are fundamental to quantum information and many-body physics, with widespread applications ranging from quantum learning and metrology to device benchmarking. A central pursuit is to minimize the space and circuit depth required to generate them. However, existing methods for generating low-depth random unitaries rely heavily on an extensive number of ancillary qubits, imposing severe spatial overhead. In this work, we prove that random unitaries can be generated in optimal depth without ancillae. For multiplicative-error approximate kkk-designs on nnn qubits, our circuits achieve a depth of O~(k)(log⁡n)1/δ\widetilde{O} (k) (\log n)^{1/δ}O(k)(logn)1/δ on δδδ-dimensional architectures and O~(k)log⁡log⁡n\widetilde{O}(k) \log \log nO(k)loglogn with all-to-all connectivity. Furthermore, by introducing a general exactification lemma, we lift our construction to optimal-depth exact kkk-designs, yielding an exponential resource reduction over state-of-the-art exact constructions. Our results minimize the space-time costs for a wide range of quantum protocols.
Matchgate unitaries are ubiquitous in quantum computation due to their relation to non-interacting fermions and because they can be used to benchmark quantum computers. Implementing such unitaries on fault-tolerant devices requires first compiling them into a discrete universal gate set, typically Clifford+T+T+T. Here, we propose a different approach for their synthesis: compile matchgate unitaries using only matchgate gates. To this end, we first show that the matchgate-Clifford group (the intersection of the matchgate and Clifford groups) plus the T‾\overline{T}T gate (a TTT unitary up to a phase) is universal for the matchgate group. Our approach leverages the connection between nnn-qubit matchgate circuits and the standard representation of SO(2n)\mathbb{SO}(2n)SO(2n), which reduces the compilation from 2n×2n2^n\times 2^n2n×2n unitaries to 2n×2n2n\times2n2n×2n ones, thus reducing exponentially the size of the target matrix. Moreover, we rigorously show that this scheme is efficient, as an approximation error εSO(2n)\varepsilon_{\mathbb{SO}(2n)}εSO(2n)​ incurred in this smaller-dimensional representation translates at most into an O(n εSO(2n))O(n \,\varepsilon_{\mathbb{SO}(2n)})O(nεSO(2n)​) error in the exponentially large unitary. In addition, we study the exact version of the matchgate synthesis problem, and we prove that all matchgate unitaries UUU such that U⊗U∗U\otimes U^*U⊗U∗ has entries in the ring Z[1/2,i]\mathbb{Z}\big[1/\sqrt 2,i\big]Z[1/2​,i] can be exactly synthesized by a finite sequence of gates from the matchgate-Clifford+T‾+\overline{T}+T set, without ancillas. We then use this insight to map optimal exact matchgate synthesis to Boolean satisfiability, and compile the circuits that diagonalize the free-fermionic XXXXXX Hamiltonian on n=4, 8n=4,\,8n=4,8 qubits.
Constructing ensembles of circuits which efficiently approximate the Haar measure over various groups is a fundamental problem in quantum information theory, with breakthrough recent results showing that for the unitary group this can be achieved with depths scaling logarithmically in the system size. Here we prove that, for groups G possessing an invariant state G⊗k∣Ψ⟩=∣Ψ⟩{G}^{\otimes k}\left\vert \Psi \right\rangle=\left\vert \Psi \right\rangleG⊗k∣Ψ⟩=∣Ψ⟩ satisfying certain conditions on its entanglement structure, no subset of G consisting of sublinear-depth one-dimensional circuits with constant-locality gates can form an approximate k-design over G. More generally, on a D-dimensional lattice of side-length n, our results imply that such group designs require depths scaling at least as n1/D. Among other examples, we show that there is a constant separation between the maximum depth and gate counts for which no circuit can approximate even the second moment of random matchgate circuits, and those required to implement the matchgate Haar distribution exactly. Finally, we relax the assumption of working with local gates, and prove the impossibility of obtaining approximate designs over G using any circuit comprised of a sublinear number of gates generated by Pauli strings. Significant effort has been spent to find low-depth constructions of random unitaries that appear Haar-random to a restricted observer, and earlier works showed logarithmic-depth approximate designs over the full unitary group using local random circuits. In this paper, the authors provide a general criterion ruling out shallow designs on a wide variety of groups.