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

Strong matchgate designs in nearly optimal depth — E8 Intelligence Research

Andrew Stewart Caldin

Published Nov 10, 2026• 0 citations
Publisher

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

DOI
10.5281/zenodo.24099381

Related papers

Strong matchgate designs in nearly optimal depth

Maxwell West, M. Cerezo, Martin Larocca

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.

quant-pharXiv:2609.26677•Sep 23, 2026•3 citations

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

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

Strong unitary designs in optimal depth and space

Teodor Parella-Dilmé, Júlia Barberà-Rodríguez, Salvatore F. E. Oliviero +1 more

Unitary designs provide finite-moment approximations to Haar-random unitaries, with wide-ranging applications across physics and quantum information, from scrambling and black-hole dynamics to foundational primitives in quantum algorithms. Strong unitary designs capture a more demanding operational notion of approximation, requiring indistinguishability from Haar randomness even for quantum algorithms that may access a unitary not only in the forward direction, but also through its inverse, transpose, and complex conjugate. Motivated by the physical requirement that scrambling arise within the system itself, Schuster, Ma, Lombardi, Brandão, and Huang (arXiv:2509.26310) left open whether strong unitary designs can be generated in logarithmic depth using only the system qubits. For every fixed design order $k$ and measurable-error tolerance, we construct strong approximate unitary $k$-designs in optimal $Θ(\log n)$ all-to-all circuit depth using only the $n$ original system qubits. Our new ingredient is a logarithmic-depth Pauli-mixing bound for the perfect-matching ensemble, whose layers pair the qubits uniformly at random and apply independent random two-qubit gates. This bound controls the mixed forward-reverse two-query case, which we combine with existing design and gluing results to obtain strong unitary designs of arbitrary fixed order.

quant-pharXiv:2608.13491•Aug 14, 2026•5 citations

Golden Gates: Solovay-Kitaev, Fibonacci Anyons, and the Golden Ratio — E8 Intelligence Research

Andrew Stewart Caldin

FINDING: The Solovay-Kitaev theorem guarantees efficient approximation of any single-qubit unitary using finite gate sets; its optimal implementations ("golden gates") are deeply tied to algebraic number theory and, for Fibonacci anyons, to the golden ratio. | MATH: The theorem states: For any finite set \(S \subset SU(2)\) generating a dense subgroup, any \(U \in SU(2)\) can be \(\varepsilon\)-approximated in \(O(\log^c(1/\varepsilon))\) gates, \(c \approx 3.97\) (improved to \(c=1\) for certain sets). Exact synthesis for Fibonacci anyons uses the braid group \(B_3\) representation where the fusion space dimension grows as \(F_n\) (Fibonacci numbers). The key constant: the golden ratio \(\varphi = (1+\sqrt{5})/2 = 1.618...\), with its inverse \(\varphi^{-1} = 0.618...\), and the related \(\varphi^{-2} = 0.382...\). The Fibonacci anyon braid matrices have entries in \(\mathbb{Z}[\varphi]\), the ring of integers of \(\mathbb{Q}(\sqrt{5})\). | CONNECTION: Direct and explicit. The Fibonac Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com

•Oct 19, 2026•0 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
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
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.
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.
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.
Unitary designs provide finite-moment approximations to Haar-random unitaries, with wide-ranging applications across physics and quantum information, from scrambling and black-hole dynamics to foundational primitives in quantum algorithms. Strong unitary designs capture a more demanding operational notion of approximation, requiring indistinguishability from Haar randomness even for quantum algorithms that may access a unitary not only in the forward direction, but also through its inverse, transpose, and complex conjugate. Motivated by the physical requirement that scrambling arise within the system itself, Schuster, Ma, Lombardi, Brandão, and Huang (arXiv:2509.26310) left open whether strong unitary designs can be generated in logarithmic depth using only the system qubits. For every fixed design order kkk and measurable-error tolerance, we construct strong approximate unitary kkk-designs in optimal Θ(log⁡n)Θ(\log n)Θ(logn) all-to-all circuit depth using only the nnn original system qubits. Our new ingredient is a logarithmic-depth Pauli-mixing bound for the perfect-matching ensemble, whose layers pair the qubits uniformly at random and apply independent random two-qubit gates. This bound controls the mixed forward-reverse two-query case, which we combine with existing design and gluing results to obtain strong unitary designs of arbitrary fixed order.
FINDING: The Solovay-Kitaev theorem guarantees efficient approximation of any single-qubit unitary using finite gate sets; its optimal implementations ("golden gates") are deeply tied to algebraic number theory and, for Fibonacci anyons, to the golden ratio. | MATH: The theorem states: For any finite set S⊂SU(2)S \subset SU(2)S⊂SU(2) generating a dense subgroup, any U∈SU(2)U \in SU(2)U∈SU(2) can be ε\varepsilonε-approximated in O(log⁡c(1/ε))O(\log^c(1/\varepsilon))O(logc(1/ε)) gates, c≈3.97c \approx 3.97c≈3.97 (improved to c=1c=1c=1 for certain sets). Exact synthesis for Fibonacci anyons uses the braid group B3B_3B3​ representation where the fusion space dimension grows as FnF_nFn​ (Fibonacci numbers). The key constant: the golden ratio φ=(1+5)/2=1.618...\varphi = (1+\sqrt{5})/2 = 1.618...φ=(1+5​)/2=1.618..., with its inverse φ−1=0.618...\varphi^{-1} = 0.618...φ−1=0.618..., and the related φ−2=0.382...\varphi^{-2} = 0.382...φ−2=0.382.... The Fibonacci anyon braid matrices have entries in Z[φ]\mathbb{Z}[\varphi]Z[φ], the ring of integers of Q(5)\mathbb{Q}(\sqrt{5})Q(5​). | CONNECTION: Direct and explicit. The Fibonac Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com
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.