We propose a method to reliably and efficiently extract the fidelity of many-qubit quantum circuits composed of continuously parametrized two-qubit gates called matchgates. This method, which we call matchgate benchmarking , relies on advanced techniques from randomized benchmarking as well as insights from the representation theory of matchgate circuits. We argue the formal correctness and scalability of the protocol, and moreover deploy it to estimate the performance of matchgate circuits generated by two-qubit XY spin interactions on a quantum processor.We propose a method to reliably and efficiently extract the fidelity of many-qubit quantum circuits composed of continuously parametrized two-qubit gates called matchgates. This method, which we call matchgate benchmarking , relies on advanced techniques from randomized benchmarking as well as insights from the representation theory of matchgate circuits. We argue the formal correctness and scalability of the protocol, and moreover deploy it to estimate the performance of matchgate circuits generated by two-qubit XY spin interactions on a quantum processor.

arXiv:2011.13048QuantumFeb 21, 202237 citations

Notes on Interrogating Random Quantum Circuits

Luís T. A. N. Brandão, René Peralta

Jan 1, 20203 citations

Modeling quantum circuits

Margareta Vamos

Jan 1, 20111 citation

Quantum matchgate computations and linear threshold gates

Maarten Van den Nest

Abstract The theory of matchgates is of interest in various areas in physics and computer science. Matchgates occur, for example, in the study of fermions and spin chains, in the theory of holographic algorithms and in several recent works in quantum computation. In this paper, we completely characterize the class of Boolean functions computable by unitary two-qubit matchgate circuits with some probability of success. We show that this class precisely coincides with that of the linear threshold gates. The latter is a fundamental family that appears in several fields, such as the study of neural networks. Using the above characterization, we further show that the power of matchgate circuits is surprisingly trivial in those cases where the computation is to succeed with high probability. In particular, the only functions that are matchgate-computable with success probability greater than 3/4 are functions depending on only a single bit of the input.Abstract The theory of matchgates is of interest in various areas in physics and computer science. Matchgates occur, for example, in the study of fermions and spin chains, in the theory of holographic algorithms and in several recent works in quantum computation. In this paper, we completely characterize the class of Boolean functions computable by unitary two-qubit matchgate circuits with some probability of success. We show that this class precisely coincides with that of the linear threshold gates. The latter is a fundamental family that appears in several fields, such as the study of neural networks. Using the above characterization, we further show that the power of matchgate circuits is surprisingly trivial in those cases where the computation is to succeed with high probability. In particular, the only functions that are matchgate-computable with success probability greater than 3/4 are functions depending on only a single bit of the input.

arXiv:1005.1143Proceedings of the Royal Society A Mathematical Physical and Engineering SciencesSep 9, 201013 citations

Matchgate synthesis via Clifford matchgates and $T$ 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.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.05425Feb 6, 20260 citations

A Lightweight Protocol for Matchgate Fidelity Estimation

Jędrzej Burkat, Sergii Strelchuk

We present a low-depth randomised protocol for estimating the entanglement fidelity between an $n$ -qubit matchgate circuit $\mathcal{U}$ and its noisy implementation $\mathcal{E}$ . Our method uses a Pauli-Liouville representation adapted to Clifford algebra elements, in which matchgate superoperators acquire a block-diagonal form. This structure enables efficient direct fidelity estimation using only Pauli state preparation and measurement, while avoiding the exponentially costly sampling step required for generic unitary channels. Compared with the protocol of Flammia and Liu [PRL 106, 230501], our algorithm gives an exponential improvement in classical sampling complexity and a multiplicative $1/\sqrt{n}$ reduction in expected shot count for matchgate circuits. The protocol also extends, without asymptotic overhead, to matchgate circuits sandwiched between Clifford circuits. For nearest-neighbour $XY(θ)$ gates and Givens rotations we demonstrate an increase in superoperator sparsity, giving an additional $1/\sqrt{n}$ reduction in expected shot count and, to our knowledge, the first scalable fidelity estimation protocol for these important matchgate subgroups.We present a low-depth randomised protocol for estimating the entanglement fidelity between an $n$-qubit matchgate circuit $\mathcal{U}$ and its noisy implementation $\mathcal{E}$. Our method uses a Pauli-Liouville representation adapted to Clifford algebra elements, in which matchgate superoperators acquire a block-diagonal form. This structure enables efficient direct fidelity estimation using only Pauli state preparation and measurement, while avoiding the exponentially costly sampling step required for generic unitary channels. Compared with the protocol of Flammia and Liu [PRL 106, 230501], our algorithm gives an exponential improvement in classical sampling complexity and a multiplicative $1/\sqrt{n}$ reduction in expected shot count for matchgate circuits. The protocol also extends, without asymptotic overhead, to matchgate circuits sandwiched between Clifford circuits. For nearest-neighbour $XY(θ)$ gates and Givens rotations we demonstrate an increase in superoperator sparsity, giving an additional $1/\sqrt{n}$ reduction in expected shot count and, to our knowledge, the first scalable fidelity estimation protocol for these important matchgate subgroups.

arXiv:2404.07974Apr 11, 20242 citations

+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.

We present a low-depth randomised protocol for estimating the entanglement fidelity between an

n

-qubit matchgate circuit

\mathcal{U}

and its noisy implementation

\mathcal{E}

. Our method uses a Pauli-Liouville representation adapted to Clifford algebra elements, in which matchgate superoperators acquire a block-diagonal form. This structure enables efficient direct fidelity estimation using only Pauli state preparation and measurement, while avoiding the exponentially costly sampling step required for generic unitary channels. Compared with the protocol of Flammia and Liu [PRL 106, 230501], our algorithm gives an exponential improvement in classical sampling complexity and a multiplicative

1/\sqrt{n}

reduction in expected shot count for matchgate circuits. The protocol also extends, without asymptotic overhead, to matchgate circuits sandwiched between Clifford circuits. For nearest-neighbour

XY(θ)

gates and Givens rotations we demonstrate an increase in superoperator sparsity, giving an additional

1/\sqrt{n}

reduction in expected shot count and, to our knowledge, the first scalable fidelity estimation protocol for these important matchgate subgroups.