Repository logo
 

Jordan-Wigner formalism for arbitrary 2-input 2-output matchgates and their classical simulation


Type

Article

Change log

Authors

Jozsa, Richard 
Miyake, Akimasa 

Abstract

In Valiant's matchgate theory, 2-input 2-output matchgates are 4x4 matrices that satisfy ten so-called matchgate identities. We prove that the set of all such matchgates (including non-unitary and non-invertible ones) coincides with the topological closure of the set of all matrices obtained as exponentials of linear combinations of the 2-qubit Jordan-Wigner (JW) operators and their quadratic products, extending a previous result of Knill. In Valiant's theory, outputs of matchgate circuits can be classically computed in poly-time. Via the JW formalism, Terhal & DiVincenzo and Knill established a relation of a unitary class of these circuits to the efficient simulation of non-interacting fermions. We describe how the JW formalism may be used to give an efficient simulation for all cases in Valiant's simulation theorem, which in particular includes the case of non-interacting fermions generalised to allow arbitrary 1-qubit gates on the first line at any stage in the circuit. Finally we give an exposition of how these simulation results can be alternatively understood from some basic Lie algebra theory, in terms of a formalism introduced by Somma et al.

Description

Keywords

quant-ph, quant-ph

Journal Title

Quant. Inform. Comp.

Conference Name

Journal ISSN

Volume Title

15

Publisher

Rinton Press

Publisher DOI

Publisher URL

Sponsorship
RJ was supported in part by the EC network Q-ALGO. AM was supported in part by National Science Foundation grants PHY-1212445 and PHY-1314955.