PIRSA:14010085 Scientific Series Quantum Information

DOI10.48660/14010085

Series: Perimeter Institute Quantum Discussions

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}}
}

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.

Resources

Next talk

Related Talks