Simulating quantum computation by contracting tensor networks

Details Simulating quantum computation by contracting tensor networks Simulating quantum computation by contracting tensor networks

2005-11-08

arxiv.org/abs/quant-ph/0511069v7

SIAM Journal on Computing, 38(3):963-981, 2008

Physics

Quantum Physics

7 figures

Scientific paper

10.1137/050644756

The treewidth of a graph is a useful combinatorial measure of how close the graph is to a tree. We prove that a quantum circuit with $T$ gates whose underlying graph has treewidth $d$ can be simulated deterministically in $T^{O(1)}\exp[O(d)]$ time, which, in particular, is polynomial in $T$ if $d=O(\log T)$. Among many implications, we show efficient simulations for log-depth circuits whose gates apply to nearby qubits only, a natural constraint satisfied by most physical implementations. We also show that one-way quantum computation of Raussendorf and Briegel (Physical Review Letters, 86:5188--5191, 2001), a universal quantum computation scheme with promising physical implementations, can be efficiently simulated by a randomized algorithm if its quantum resource is derived from a small-treewidth graph.

Affiliated with

Also associated with

No associations

Rating

Simulating quantum computation by contracting tensor networks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Simulating quantum computation by contracting tensor networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Simulating quantum computation by contracting tensor networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-294227