Universal Computation by Quantum Walk

被引：795

作者：

Childs, Andrew M. ^{[1
,2
]}

机构：

[1] Univ Waterloo, Dept Combinator & Optimizat, Waterloo, ON N2L 3G1, Canada

[2] Univ Waterloo, Inst Quantum Comp, Waterloo, ON N2L 3G1, Canada

来源：

PHYSICAL REVIEW LETTERS | 2009年 / 102卷 / 18期

基金：

加拿大自然科学与工程研究理事会;

关键词：

COMPLEXITY; ALGORITHMS;

D O I：

10.1103/PhysRevLett.102.180501

中图分类号：

O4 [物理学];

学科分类号：

0702 ;

摘要：

In some of the earliest work on quantum computing, Feynman showed how to implement universal quantum computation with a time-independent Hamiltonian. I show that this remains possible even if the Hamiltonian is restricted to be the adjacency matrix of a low-degree graph. Thus quantum walk can be regarded as a universal computational primitive, with any quantum computation encoded in some graph. The main idea is to implement quantum gates by scattering processes.

引用

页数：4

共 23 条

[1]

AHARONOV A., 2003, P 35 ANN ACM S THEOR, P20, DOI DOI 10.1145/780542.780546

[2] Adiabatic quantum computation is equivalent to standard quantum computation [J].

Aharonov, Dorit ;

Van Dam, Wim ;

Kempe, Julia ;

Landau, Zeph ;

Lloyd, Seth ;

Regev, Oded .

SIAM JOURNAL ON COMPUTING, 2007, 37 (01) :166-194

[3] The power of quantum systems on a line [J].

Aharonov, Dorit ;

Gottesman, Daniel ;

Irani, Sandy ;

Kempe, Julia .

48TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 2007, :373-+

[4] Any AND-OR formula of size can be evaluated in time on a quantum computer [J].

Ambainis, Andris ;

Childs, Andrew M. ;

Reichardt, Ben W. ;

Spalek, Robert ;

Zhang, Shengyu .

48TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 2007, :363-+

[5] Quantum walk algorithm for element distinctness [J].

Ambainis, Andris .

SIAM JOURNAL ON COMPUTING, 2007, 37 (01) :210-239

[6] A new universal and fault-tolerant quantum basis [J].

Boykin, PO ;

Mor, T ;

Pulver, M ;

Roychowdhury, V ;

Vatan, F .

INFORMATION PROCESSING LETTERS, 2000, 75 (03) :101-107

[7] Quantum Verification of Matrix Products [J].

Buhrman, Harry ;

Spalek, Robert .

PROCEEDINGS OF THE SEVENTHEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2006, :880-889

[8]

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

[9] Spatial search by quantum walk [J].

Childs, AM ;

Goldstone, J .

PHYSICAL REVIEW A, 2004, 70 (02) :022314-1

[10] Quantum computation and decision trees [J].

Farhi, E ;

Gutmann, S .

PHYSICAL REVIEW A, 1998, 58 (02) :915-928

← 1 2 3 →