PIRSA:08040052 Conference Quantum Information

DOI10.48660/08040052

Conference/School: Quantum Information and Graph Theory: Emerging Connections - 2008

Shi, Y. (2008). Graph expansions and simulating one-way quantum computation . Perimeter Institute. https://pirsa.org/08040052

Shi, Yaoyan. Graph expansions and simulating one-way quantum computation . Perimeter Institute, Apr. 30, 2008, https://pirsa.org/08040052 

@misc{ pirsa_PIRSA:08040052,
  doi = {10.48660/08040052},
  url = {https://pirsa.org/08040052},
  author = {Shi, Yaoyan},
  keywords = {Quantum Information},
  language = {en},
  title = {Graph expansions and simulating one-way quantum computation },
  publisher = {Perimeter Institute},
  year = {2008},
  month = {apr},
  note = {PIRSA:08040052 see, \url{https://pirsa.org}}
}

Abstract

It is well-known that if a graph G_1 can be obtained from another graph G_2 by removing a degree-2 vertex and combing its two neighbors, the graph state |G_1> can be obtained from |G_2> through LOCC. In this talk, I will describe how to construct a graph G\' from a given graph G so that (a) The maximum degree of G\', Delta(G\'), is no more than 3. (b) G can be obtained from G\' by a sequence of contraction operations described above. (c) The treewidth of G\', tw(G\'), is no more than tw(G)+1. (d) The construction takes exp(O(tw(G))) time. Those properties imply that a one-way quantum computation on the graph state |G> can be simulated by a randomized algorithm in time exp(O(tw(G))). Previously, it was known that such a computation can be simulated in time exp(O(tw(G) Delta(G))) [Markov and Shi, to appear in SICOMP], which is substantially more expensive than our bound when Delta(G) is large. Joint work with Igor Markov, based on arXiv:0707.3622.

Resources

Next talk

Related Talks