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.
Matchgates are an especially multiflorous class of two-qubit nearest-neighbour quantum gates, defined by a set of algebraic constraints. They occur for example in the theory of perfect matchings of graphs, non-interacting fermions and one-dimensional spin chains. We show that the computational power of circuits of matchgates is equivalent to that of space-bounded quantum computation with unitary gates, with space restricted to being logarithmic in the width of the matchgate circuit. In particular, for the conventional setting of polynomial-sized (logarithmic-space generated) families of matchgate circuits, known to be classically simulatable, we characterize their power as coinciding with polynomial-time and logarithmic-space-bounded universal unitary quantum computation.
Matchgates are an especially multiflorous class of two-qubit nearest-neighbour quantum gates, defined by a set of algebraic constraints. They occur for example in the theory of perfect matchings of graphs, non-interacting fermions and one-dimensional spin chains. We show that the computational power of circuits of matchgates is equivalent to that of space-bounded quantum computation with unitary gates, with space restricted to being logarithmic in the width of the matchgate circuit. In particular, for the conventional setting of polynomial-sized (logarithmic-space generated) families of matchgate circuits, known to be classically simulatable, we characterize their power as coinciding with polynomial-time and logarithmic-space-bounded universal unitary quantum computation.
An essential requirement for any quantum computing architecture is the existence of a universal set of quantum gates. Examples of such sets are the 2-qubit CNOT gate in combination with arbitrary 1-qubit gates, and the 3-qubit Toffoli gate together with the 1-qubit Hadamard. A third set, which has not been implemented so far, is Valiant's 2-qubit matchgate G(A,B) which is universal with the SWAP operation. This paper presents how symmetric Valiant gates are decomposed which are sufficient for universal quantum computation, using another universal class of gates - a controlled-Zthetasgate and single qubit unitaries. Various symmetric matchgates (G(H,H), G(X,X) and G(T,T)) in a two-photon experiment to build quantum logic gates using higher-dimensional Hilbert spaces are implemented. The gate operations are characterized via quantum process tomography.
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 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 SO(2n), which reduces the compilation from 2n×2n unitaries to 2n×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) incurred in this smaller-dimensional representation translates at most into an 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 U such that U⊗U∗ has entries in the ring Z[1/2,i] can be exactly synthesized by a finite sequence of gates from the matchgate-Clifford+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.
In the circuit model, quantum computers rely on the availability of a universal quantum gate set. A particularly intriguing example is a set of two-qubit-only gates: 'matchgates', along with swap (the exchange of two qubits). In this paper, we show a simple decomposition of arbitrary matchgates into better-known elementary gates and implement a matchgate in a single-photon linear optics experiment. The gate performance is fully characterized via quantum process tomography. Moreover, we represent the resulting reconstructed quantum process in a novel way, as a fidelity map in the space of all possible non-local two-qubit unitaries. We propose the non-local distance —which is independent of local imperfections such as uncorrelated noise or uncompensated local rotations—as a new diagnostic process measure for the non-local properties of the implemented gate.
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.