Discrete quantum walks hit exponentially faster

被引:111
作者
Kempe, J [1 ]
机构
[1] Univ Paris 11, LRI, CNRS, UMR 8623, F-91405 Orsay, France
[2] Univ Calif Berkeley, Div Comp Sci, Berkeley, CA 94720 USA
[3] Univ Calif Berkeley, Dept Chem, Berkeley, CA 94720 USA
关键词
Stochastic Process; Probability Theory; Polynomial Time; Discrete Time; Mathematical Biology;
D O I
10.1007/s00440-004-0423-2
中图分类号
O21 [概率论与数理统计]; C8 [统计学];
学科分类号
020208 ; 070103 ; 0714 ;
摘要
This paper addresses the question: what processes take polynomial time on a quantum computer that require exponential time classically? We show that the hitting time of the discrete time quantum walk on the n-bit hypercube from one corner to its opposite is polynomial in n. This gives the first exponential quantum-classical gap in the hitting time of discrete quantum walks. We provide the basic framework for quantum hitting time and give two alternative definitions to set the ground for its study on general graphs. We outline a possible application to sequential packet routing.
引用
收藏
页码:215 / 235
页数:21
相关论文
共 28 条
  • [1] Aharonov Dorit, 2001, arXiv: quant-ph/0012090, P50
  • [2] Aldous D., REVERSIBLE MARKOV CH
  • [3] AMBAINIS A, 2001, P 33 ACM S THEOR COM, P60, DOI DOI 10.1145/380752.380757
  • [4] [Anonymous], [No title captured], DOI [10.1145/237814.237866, DOI 10.1145/237814.237866]
  • [5] Strengths and weaknesses of quantum computing
    Bennett, CH
    Bernstein, E
    Brassard, G
    Vazirani, U
    [J]. SIAM JOURNAL ON COMPUTING, 1997, 26 (05) : 1510 - 1523
  • [6] Childs A. M., 2003, P 35 ANN ACM S THEOR, P59, DOI DOI 10.1145/780542.780552
  • [7] An Example of the Difference Between Quantum and Classical Random Walks
    Childs, Andrew M.
    Farhi, Edward
    Gutmann, Sam
    [J]. QUANTUM INFORMATION PROCESSING, 2002, 1 (1-2) : 35 - 43
  • [8] A RANDOM POLYNOMIAL-TIME ALGORITHM FOR APPROXIMATING THE VOLUME OF CONVEX-BODIES
    DYER, M
    FRIEZE, A
    KANNAN, R
    [J]. JOURNAL OF THE ACM, 1991, 38 (01) : 1 - 17
  • [9] Quantum computation and decision trees
    Farhi, E
    Gutmann, S
    [J]. PHYSICAL REVIEW A, 1998, 58 (02): : 915 - 928
  • [10] Grigni M., 2001, P 33 ANN ACM S THEOR, P68