The authors study the classical simulability and computational power of so-called matchgate circuits in the presence of additional resources, and find striking parallels to the known results for Clifford circuits. They also clarify under which conditions universal quantum computation is achieved with this gate set.
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.
We study the classical simulation complexity, in both the weak and strong senses, of matchgate (MG) computations supplemented with all combinations of settings involving inclusion of intermediate adaptive or nonadaptive computational basis measurements, product state or magic and general entangled state inputs, and single- or multiple-line outputs. We find a striking parallel to known results for Clifford circuits, after some rebranding of resources. We also give bounds on the amount of classical simulation effort required in the case of limited access to intermediate measurements and entangled inputs. In further settings we show that adaptive MG circuits remain classically efficiently simulable if arbitrary two-qubit entangled input states on consecutive lines are allowed, but become quantum universal for three or more lines. And if adaptive measurements in noncomputational bases are allowed, even with just computational basis inputs, we get quantum universal power again.
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-qubit circuit containing N gates, m of which are universality-enabling gates and 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 as n→∞, the resource cost, T, scales as O((m+1en)2m+2). For m scaling as a linear function of n, however, T scale as O(22nH(nm+1)), where H(λ) is the binary entropy function.
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
Let G ( A , B ) denote the two-qubit gate that acts as the one-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 allow 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 generalize the simulation result above to provide further classes of classically efficiently simulatable quantum circuits, which we call Gaussian quantum circuits.