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

Physical Review A

Extending matchgates to universal quantum computation via the Hubbard model

Jia-Wei Ji, David L. Feder

Published Nov 19, 2019• 3 citations
Publisher

Abstract

Quantum circuits solely comprising matchgates can perform nontrivial (but nonuniversal) quantum algorithms. Because matchgates can be mapped to noninteracting fermions, these circuits can be efficiently simulated on a classical computer. Universal quantum computation is attainable by adding any nonmatchgate parity-preserving gate, from which one may infer that interacting fermions are natural candidates for universal quantum computation. We consider the quantum computational power of fermions hopping on a one-dimensional double-well lattice within the context of matchgates. In particular, we show that universal quantum computation can be implemented using spinless (spin-polarized) fermions and nearest-neighbor interactions, as well as with spin-half fermions with on-site interactions (i.e., the Hubbard model). We suggest that these schemes are currently within reach in the context of ultracold atomic gases.

DOI
10.1103/physreva.100.052324

Related papers

The Hubbard Model for Universal Quantum Computation

Jiawei Ji

Quantum circuits based only on matchgates are able to perform non-trivial (but not universal) quantum algorithms. Because matchgates can be mapped to non-interacting fermions, these circuits can be efficiently simulated on a classical computer. One can perform universal quantum computation by adding any non-matchgate parity-preserving gate, implying that interacting fermions are natural candidates for universal quantum computation. Most work to date has focused on Majorana fermions, which are difficult to realize and manipulate in the laboratory, despite the advantage of topologically protecting quantum information. We instead show that universal quantum computation can be implemented using interacting spinless (spin-polarized) fermions and further propose a scheme for achieving universal quantum computation with the Hubbard model, which may be realized in the laboratory based on current experimental techniques.

•Jan 24, 2019•0 citations

Extending matchgates into universal quantum computation

Daniel J. Brod, Ernesto F. Galvão

Matchgates are a family of two-qubit gates associated with noninteracting fermions. They are classically simulatable if acting only on nearest neighbors but become universal for quantum computation if we relax this restriction or use swap gates [Jozsa and Miyake, Proc. R. Soc. A 464, 3089 (2008)]. We generalize this result by proving that any nonmatchgate parity-preserving unitary is capable of extending the computational power of matchgates into universal quantum computation. We identify the single local invariant of parity-preserving unitaries responsible for this, and discuss related results in the context of fermionic systems.

arXiv:1106.1863•Physical Review A•Aug 5, 2011•39 citations

Geometries for universal quantum computation with matchgates

Daniel J. Brod, Ernesto F. Galvão

Matchgates are a group of two-qubit gates associated with free fermions. They are classically simulatable if restricted to act between nearest neighbors on a one-dimensional chain, but become universal for quantum computation with longer-range interactions. We describe various alternative geometries with nearest-neighbor interactions that result in universal quantum computation with matchgates only, including subtle departures from the chain. Our results pave the way for new quantum computer architectures that rely solely on the simple interactions associated with matchgates.

arXiv:1207.2126•Physical Review A•Nov 6, 2012•14 citations

Matchgates and classical simulation of quantum circuits

Richard Jozsa, Akimasa Miyake, ,

Let G(A, B) denote the 2-qubit gate which acts as the 1-qubit SU(2) gates A and B in the even and odd parity subspaces respectively, of two qubits. Using a Clifford algebra formalism we show that arbitrary uniform families of circuits of these gates, restricted to act only on nearest neighbour (n.n.) qubit lines, can be classically efficiently simulated. This reproduces a result originally proved by Valiant using his matchgate formalism, and subsequently related by others to free fermionic physics. We further show that if the n.n. condition is slightly relaxed, to allowing the same gates to act only on n.n. and next-n.n. qubit lines, then the resulting circuits can efficiently perform universal quantum computation. From this point of view, the gap between efficient classical and quantum computational power is bridged by a very modest use of a seemingly innocuous resource (qubit swapping). We also extend the simulation result above in various ways. In particular, by exploiting properties of Clifford operations in conjunction with the Jordan-Wigner representation of a Clifford algebra, we show how one may generalise the simulation result above to provide further classes of classically efficiently simulatable quantum circuits, which we call Gaussian quantum circuits. 1

•Dec 8, 2008•114 citations

The computational power of matchgates and the XY interaction on arbitrary graphs

Daniel J. Brod, Andrew M. Childs

Matchgates are a restricted set of two-qubit gates known to be classically simulable when acting on nearest-neighbor qubits on a path, but universal for quantum computation when the qubits are arranged on certain other graphs. Here we characterize the power of matchgates acting on arbitrary graphs. Specifically, we show that they are universal on any connected graph other than a path or a cycle, and that they are classically simulable on a cycle. We also prove the same dichotomy for the XY interaction, a proper subset of matchgates related to some implementations of quantum computing.

Quantum Information and Computation•Sep 1, 2014•14 citations

Extending Matchgate Simulation Methods to Universal Quantum Circuits

Avinash Mocherla, Lingling Lao, Dan E. Browne

Matchgates are a family of parity-preserving two-qubit gates, nearest-neighbour circuits of which are known to be classically simulable in polynomial time. In this work, we present a simulation method to classically simulate an $\boldsymbol{n}$-qubit circuit containing $\boldsymbol{N}$ gates, $\boldsymbol{m}$ of which are universality-enabling gates and $\boldsymbol{N-m}$ of which are matchgates, in the setting of single-qubit Pauli measurements and product state inputs. The universality-enabling gates we consider include the SWAP, CZ, and CPhase gates. For fixed $\boldsymbol{m}$ as $\boldsymbol{n} \rightarrow \boldsymbol{\infty}$, the resource cost, $\boldsymbol{T}$, scales as $\boldsymbol{\mathcal{O}\left(\left(\frac{en}{m+1}\right)^{2m+2}\right)}$. For $\boldsymbol{m}$ scaling as a linear function of $\boldsymbol{n}$, however, $\boldsymbol{T}$ scale as $\boldsymbol{\mathcal{O}\left(2^{2nH\left(\frac{m+1}{n}\right)}\right)}$, where $\boldsymbol{H}(λ)$ is the binary entropy function.

arXiv:2302.02654•Feb 6, 2023•25 citations
Quantum circuits solely comprising matchgates can perform nontrivial (but nonuniversal) quantum algorithms. Because matchgates can be mapped to noninteracting fermions, these circuits can be efficiently simulated on a classical computer. Universal quantum computation is attainable by adding any nonmatchgate parity-preserving gate, from which one may infer that interacting fermions are natural candidates for universal quantum computation. We consider the quantum computational power of fermions hopping on a one-dimensional double-well lattice within the context of matchgates. In particular, we show that universal quantum computation can be implemented using spinless (spin-polarized) fermions and nearest-neighbor interactions, as well as with spin-half fermions with on-site interactions (i.e., the Hubbard model). We suggest that these schemes are currently within reach in the context of ultracold atomic gases.
Quantum circuits based only on matchgates are able to perform non-trivial (but not universal) quantum algorithms. Because matchgates can be mapped to non-interacting fermions, these circuits can be efficiently simulated on a classical computer. One can perform universal quantum computation by adding any non-matchgate parity-preserving gate, implying that interacting fermions are natural candidates for universal quantum computation. Most work to date has focused on Majorana fermions, which are difficult to realize and manipulate in the laboratory, despite the advantage of topologically protecting quantum information. We instead show that universal quantum computation can be implemented using interacting spinless (spin-polarized) fermions and further propose a scheme for achieving universal quantum computation with the Hubbard model, which may be realized in the laboratory based on current experimental techniques.
Matchgates are a family of two-qubit gates associated with noninteracting fermions. They are classically simulatable if acting only on nearest neighbors but become universal for quantum computation if we relax this restriction or use swap gates [Jozsa and Miyake, Proc. R. Soc. A 464, 3089 (2008)]. We generalize this result by proving that any nonmatchgate parity-preserving unitary is capable of extending the computational power of matchgates into universal quantum computation. We identify the single local invariant of parity-preserving unitaries responsible for this, and discuss related results in the context of fermionic systems.
Matchgates are a group of two-qubit gates associated with free fermions. They are classically simulatable if restricted to act between nearest neighbors on a one-dimensional chain, but become universal for quantum computation with longer-range interactions. We describe various alternative geometries with nearest-neighbor interactions that result in universal quantum computation with matchgates only, including subtle departures from the chain. Our results pave the way for new quantum computer architectures that rely solely on the simple interactions associated with matchgates.
Let G(A, B) denote the 2-qubit gate which acts as the 1-qubit SU(2) gates A and B in the even and odd parity subspaces respectively, of two qubits. Using a Clifford algebra formalism we show that arbitrary uniform families of circuits of these gates, restricted to act only on nearest neighbour (n.n.) qubit lines, can be classically efficiently simulated. This reproduces a result originally proved by Valiant using his matchgate formalism, and subsequently related by others to free fermionic physics. We further show that if the n.n. condition is slightly relaxed, to allowing the same gates to act only on n.n. and next-n.n. qubit lines, then the resulting circuits can efficiently perform universal quantum computation. From this point of view, the gap between efficient classical and quantum computational power is bridged by a very modest use of a seemingly innocuous resource (qubit swapping). We also extend the simulation result above in various ways. In particular, by exploiting properties of Clifford operations in conjunction with the Jordan-Wigner representation of a Clifford algebra, we show how one may generalise the simulation result above to provide further classes of classically efficiently simulatable quantum circuits, which we call Gaussian quantum circuits. 1
Matchgates are a restricted set of two-qubit gates known to be classically simulable when acting on nearest-neighbor qubits on a path, but universal for quantum computation when the qubits are arranged on certain other graphs. Here we characterize the power of matchgates acting on arbitrary graphs. Specifically, we show that they are universal on any connected graph other than a path or a cycle, and that they are classically simulable on a cycle. We also prove the same dichotomy for the XY interaction, a proper subset of matchgates related to some implementations of quantum computing.
Matchgates are a family of parity-preserving two-qubit gates, nearest-neighbour circuits of which are known to be classically simulable in polynomial time. In this work, we present a simulation method to classically simulate an n\boldsymbol{n}n-qubit circuit containing N\boldsymbol{N}N gates, m\boldsymbol{m}m of which are universality-enabling gates and N−m\boldsymbol{N-m}N−m of which are matchgates, in the setting of single-qubit Pauli measurements and product state inputs. The universality-enabling gates we consider include the SWAP, CZ, and CPhase gates. For fixed m\boldsymbol{m}m as n→∞\boldsymbol{n} \rightarrow \boldsymbol{\infty}n→∞, the resource cost, T\boldsymbol{T}T, scales as O((enm+1)2m+2)\boldsymbol{\mathcal{O}\left(\left(\frac{en}{m+1}\right)^{2m+2}\right)}O((m+1en​)2m+2). For m\boldsymbol{m}m scaling as a linear function of n\boldsymbol{n}n, however, T\boldsymbol{T}T scale as O(22nH(m+1n))\boldsymbol{\mathcal{O}\left(2^{2nH\left(\frac{m+1}{n}\right)}\right)}O(22nH(nm+1​)), where H(λ)\boldsymbol{H}(λ)H(λ) is the binary entropy function.