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

DOI 10.48660/14010085
Collection
Talk Type Scientific Series
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.