Graph expansions and simulating one-way quantum computation

          @misc{ scivideos_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 for Theoretical Physics},
            year = {2008},
            month = {apr},
            note = {PIRSA:08040052 see, \url{https://scivideos.org/index.php/pirsa/08040052}}
          }
          

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.