Graph expansions and simulating one-way quantum computation
APA
Shi, Y. (2008). Graph expansions and simulating one-way quantum computation . Perimeter Institute. https://pirsa.org/08040052
MLA
Shi, Yaoyan. Graph expansions and simulating one-way quantum computation . Perimeter Institute, Apr. 30, 2008, https://pirsa.org/08040052
BibTex
@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}} }
University of Michigan
Talk Type
Subject
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.