Details

Autor(en) / Beteiligte

• Markov, Igor L.
• Shi, Yaoyun

Titel

Simulating Quantum Computation by Contracting Tensor Networks

Ist Teil von

• SIAM journal on computing, 2008-01, Vol.38 (3), p.963-981

Ort / Verlag

Philadelphia: Society for Industrial and Applied Mathematics

Erscheinungsjahr

2008

Link zum Volltext

Quelle

EBSCOhost Business Source Ultimate

Beschreibungen/Notizen

• 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 a 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 (Phys. Rev. Lett., 86 (2001), pp. 5188-5191), 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 with a constant maximum degree. (The requirement on the maximum degree was removed in [I. L. Markov and Y. Shi, preprint:quant-ph/0511069].)