PIRSA:14010085

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

Brod, D. (2014). The computational power of matchgates and the XY interaction on arbitrary graphs. Perimeter Institute. https://pirsa.org/14010085

Brod, Daniel. The computational power of matchgates and the XY interaction on arbitrary graphs. Perimeter Institute, Jan. 08, 2014, https://pirsa.org/14010085 

          @misc{ pirsa_PIRSA:14010085,
            doi = {10.48660/14010085},
            url = {https://pirsa.org/14010085},
            author = {Brod, Daniel},
            keywords = {Quantum Information},
            language = {en},
            title = {The computational power of matchgates and the XY interaction on arbitrary graphs},
            publisher = {Perimeter Institute},
            year = {2014},
            month = {jan},
            note = {PIRSA:14010085 see, \url{https://pirsa.org}}
          }

Daniel Brod

Universidade Federal Fluminense

Talk number
PIRSA:14010085
Collection
Talk Type
Subject
Abstract
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 gates can also act on more distant qubits. In this talk, I will address the power of matchgates when they can act on pairs of qubits according to the edges of arbitrary graphs. Specifically, we show that matchgates 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 that the same dichotomy holds for the XY interaction, a proper subset of matchgates that arises naturally in some implementations of quantum computing. This is based on a joint work with Ernesto Galvão and another with Andrew Childs.