QUANTUM COMPUTATION AND THE EVALUATION OF TENSOR NETWORKS

被引：43

作者：

Arad, Itai ^{[1
]}

Landau, Zeph ^{[1
]}

机构：

[1] Univ Calif Berkeley, Dept Elect Engn & Comp Sci, Berkeley, CA 94720 USA

来源：

SIAM JOURNAL ON COMPUTING | 2010年 / 39卷 / 07期

关键词：

tensor networks; quantum algorithms; statistical mechanical models; COMPLEXITY; JONES; POLYNOMIALS; ALGORITHM; COMPUTERS;

D O I：

10.1137/080739379

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We present a quantum algorithm that additively approximates the value of a tensor network to a certain scale. When combined with existing results, this provides a complete problem for quantum computation. The result is a simple new way of looking at quantum computation in which unitary gates are replaced by tensors and time is replaced by the order in which the tensor network is "swallowed." We use this result to derive new quantum algorithms that approximate the partition function of a variety of classical statistical mechanical models, including the Potts model.

引用

页码：3089 / 3121

页数：33

共 45 条

[1]

Aharonov D., 2007, QUANTPH0702008 ARXIV

[2]

Aharonov D., 2006, QUANTPH0605181 ARXIV

[3] A Polynomial Quantum Algorithm for Approximating the Jones Polynomial [J].

Aharonov, Dorit ;

Jones, Vaughan ;

Landau, Zeph .

ALGORITHMICA, 2009, 55 (03) :395-421

[4] COMPLEXITY OF FINDING EMBEDDINGS IN A K-TREE [J].

ARNBORG, S ;

CORNEIL, DG ;

PROSKUROWSKI, A .

SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1987, 8 (02) :277-284

[5]

Baxter R., 2008, Exactly Solved Models in Statistical Mechanics

[6] Approximate counting and quantum computation [J].

Bordewich, M ;

Freedman, M ;

Lovász, L ;

Welsh, D .

COMBINATORICS PROBABILITY & COMPUTING, 2005, 14 (5-6) :737-754

[7]

Callen HB., 1985, Thermodynamics and an Introduction to Thermostatistics

[8]

Childs A.M., 2003, P 35 ANN ACM S THEOR, P59, DOI [DOI 10.1145/780542.780552, 10.1145/780542.780552]

[9]

DAWSON CM, 2005, QUANTPH0505030 ARXIV

[10] The relative complexity of approximate counting problems [J].

Dyer, M ;

Goldberg, LA ;

Greenhill, C ;

Jerrum, M .

ALGORITHMICA, 2004, 38 (03) :471-500

← 1 2 3 4 5 →