Efficient Quantum Algorithms for Simulating Sparse Hamiltonians

被引：0

作者：

Dominic W. Berry

Graeme Ahokas

Richard Cleve

Barry C. Sanders

机构：

[1] The University of Queensland,Department of Physics

[2] University of Calgary,Institute for Quantum Information Science

[3] University of Calgary,Department of Computer Science

[4] University of Waterloo,School of Computer Science

[5] University of Waterloo,Institute for Quantum Computing

[6] Macquarie University,Centre for Quantum Computer Technology

来源：

Communications in Mathematical Physics | 2007年 / 270卷

关键词：

Quantum Algorithm; Quantum Walk; Trace Distance; Nonzero Matrix Element; Tensor Product Structure;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

We present an efficient quantum algorithm for simulating the evolution of a quantum state for a sparse Hamiltonian H over a given time t in terms of a procedure for computing the matrix entries of H. In particular, when H acts on n qubits, has at most a constant number of nonzero entries in each row/column, and ||H|| is bounded by a constant, we may select any positive integer k such that the simulation requires O((log*n)t1+1/2k) accesses to matrix entries of H. We also show that the temporal scaling cannot be significantly improved beyond this, because sublinear time scaling is not possible.

引用

页码：359 / 371

页数：12

共 28 条

[1] Grover L.(1997)Quantum mechanics helps in searching for a needle in a haystack Phys. Rev. Lett. 79 325-328
[2] Kempe J.(2006)The complexity of the local Hamiltonian problem SIAM J. Computing 35 1070-1097
[3] Kitaev A.(1982)Simulating physics with computers Int. J. Theoret. Phys. 21 467-488
[4] Regev O.(1996)Universal quantum simulators Science 273 1073-1078
[5] Feynman R.P.(2002)An example of the difference between quantum and classical random walks J. Quant. Inf. Proc. 1 35-43
[6] Lloyd S.(2003)Quantum random-walk search algorithm Phys. Rev. A 67 052307-323
[7] Childs A.(2004)Spatial search by quantum walk Phys. Rev. A 70 022314-407
[8] Farhi E.(1990)Fractal decomposition of exponential operators with applications to many-body theories and Monte Carlo simulations Phys. Lett. A 146 319-53
[9] Gutmann S.(1991)General theory of fractal path integrals with applications to many-body theories and statistical physics J. Math. Phys. 32 400-201
[10] Shenvi N.(1986)Deterministic coin tossing with applications to optimal parallel list ranking Inform. and Control 70 32-797

← 1 2 3 →