Matchgate synthesis via Clifford matchgates and $T$ gates

• URL: http://arxiv.org/abs/2602.05425v1
• Date: Thu, 05 Feb 2026 08:15:52 GMT
• Title: Matchgate synthesis via Clifford matchgates and $T$ gates
• Authors: Berta Casas, Paolo Braccia, Élie Gouzien, M. Cerezo, Diego García-Martín,
• Abstract summary: Matchgate unitaries are ubiquitous in quantum computation due to their relation to non-interacting fermions.<n>We propose a different approach for their synthesis: compile matchgate unitaries using only matchgate gates.<n>We show that this scheme is efficient, as an approximation error $varepsilon_mathbbSO (2n)$ incurred in this smaller-dimensional representation translates at most into an $O(n,varepsilon_mathbbSO (2n))$ error in the exponentially large unitary.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Multi-qubit Toffoli with exponentially fewer T gates [3.5887330421214063]
  We show how to get away with exponentially fewer $T$ gates, at the cost of incurring a tiny $1/mathrmpoly(n)$ error.<n>More precisely, the $n$-qubit Toffoli gate can be implemented to within error $epsilon$ in the diamond distance by a randomly chosen Clifford+$T$ circuit.
  arXiv  Detail & Related papers  (2025-10-08T16:56:23Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  We show that this problem has randomized communication complexity $Omega(frac1kcdot n2log|mathbbF|)$. As an application, we obtain an $Omega(frac1kcdot n2log|mathbbF|)$ space lower bound for any streaming algorithm with $k$ passes.
  arXiv  Detail & Related papers  (2024-10-26T06:21:42Z)
• Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan [49.1574468325115]
  We revisit the sample and computational complexity of completing a rank-1 tensor in $otimes_i=1N mathbbRd$. We present a characterization of the problem which admits an algorithm amounting to Gauss-Jordan on a pair of random linear systems.
  arXiv  Detail & Related papers  (2024-08-10T04:26:19Z)
• Incompressibility and spectral gaps of random circuits [2.359282907257055]
  reversible and quantum circuits form random walks on the alternating group $mathrmAlt (2n)$ and unitary group $mathrmSU (2n)$, respectively.<n>We prove that the gap for random reversible circuits is $Omega(n-3)$ for all $tgeq 1$, and the gap for random quantum circuits is $Omega(n-3)$ for $t leq Theta(2n/2)$.
  arXiv  Detail & Related papers  (2024-06-11T17:23:16Z)
• Efficient Fault-Tolerant Single Qubit Gate Approximation And Universal Quantum Computation Without Using The Solovay-Kitaev Theorem [0.0]
  A recent improvement of the Solovay-Kitaev theorem implies that to approximate any single-qubit gate to an accuracy of $epsilon > 0$ requires $textO(logc[1/epsilon)$ quantum gates with $c > 1.44042$. Here I give a partial answer to this question by showing that this is possible using $textO(log[/epsilon] loglog[/epsilon] cdots)$ FT gates chosen from a finite set depending on the value of $
  arXiv  Detail & Related papers  (2024-06-07T11:21:05Z)
• Exact Synthesis of Multiqubit Clifford-Cyclotomic Circuits [0.8411424745913132]
  We show that when $n$ is a power of 2, a multiqubit unitary matrix $U$ can be exactly represented by a circuit over $mathcalG_n$. We moreover show that $log(n)-2$ ancillas are always sufficient to construct a circuit for $U$.
  arXiv  Detail & Related papers  (2023-11-13T20:46:51Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  Under nonlinear measurements, most prior results are non-uniform, i.e., they hold with high probability for a fixed $mathbfx*$ rather than for all $mathbfx*$ simultaneously. Our framework accommodates GCS with 1-bit/uniformly quantized observations and single index models as canonical examples. We also develop a concentration inequality that produces tighter bounds for product processes whose index sets have low metric entropy.
  arXiv  Detail & Related papers  (2023-09-25T17:54:19Z)
• The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
  For every $delta>0,$ we construct CNF and formulas of size with approximate degree $Omega(n1-delta),$ essentially matching the trivial upper bound of $n. We show that for every $delta>0$, these models require $Omega(n1-delta)$, $Omega(n/4kk2)1-delta$, and $Omega(n/4kk2)1-delta$, respectively.
  arXiv  Detail & Related papers  (2022-09-04T10:01:39Z)
• An Algorithm for Reversible Logic Circuit Synthesis Based on Tensor Decomposition [0.0]
  An algorithm for reversible logic synthesis is proposed. Map can be written as a tensor product of a rank-($2n-2$) tensor and the $2times 2$ identity matrix.
  arXiv  Detail & Related papers  (2021-07-09T08:18:53Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
  arXiv  Detail & Related papers  (2020-08-24T06:50:57Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  We exploit the finite noise structure of finite sums to derive a matching $O(n2)$-upper bound under the global oracle model. Following a similar approach, we propose a novel adaptation of SVRG which is both emphcompatible with oracles, and achieves complexity bounds of $tildeO(n2+nsqrtL/mu)log (1/epsilon)$ and $O(nsqrtL/epsilon)$, for $mu>0$ and $mu=0$
  arXiv  Detail & Related papers  (2020-02-09T03:39:46Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.