01064nas a2200145 4500008004100000245008600041210006900127260001500196300001200211490000700223520060700230100002100837700002300858856003700881 2014 eng d00aThe computational power of matchgates and the XY interaction on arbitrary graphs0 acomputational power of matchgates and the XY interaction on arbi c2014/09/01 a901-9160 v143 a 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.
1 aBrod, Daniel, J.1 aChilds, Andrew, M. uhttp://arxiv.org/abs/1308.1463v1