Quantum algorithms for optimal graph traversal problems

被引：2
作者：
Doern, Sebastian [1 ]
机构：
[1] Univ Ulm, Inst Theoret Informat, D-89069 Ulm, Germany
来源：
QUANTUM INFORMATION AND COMPUTATION V | 2007年 / 6573卷
关键词：
quantum algorithms; graph theory; graph traversal problems;
D O I：
10.1117/12.719158
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We study the quantum complexity of algorithms for optimal graph traversal problems. We look at eulerian tours, optimal postman tours, approximation of travelling salesman tours and self avoiding walks. We present quantum algorithms and quantum lower bounds for these problems. Our results improve the best classical algorithms for the corresponding problems.
引用
收藏
页数：10
相关论文
共 28 条
  • [1] Quantum walk algorithm for element distinctness
    Ambainis, A
    [J]. 45TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 2004, : 22 - 31
  • [2] Quantum lower bounds by quantum arguments
    Ambainis, A
    [J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2002, 64 (04) : 750 - 767
  • [3] AMBAINIS A, 2006, P STACS 06
  • [4] Quantum lower bounds by polynomials
    Beals, R
    Buhrman, H
    Cleve, R
    Mosca, M
    De Wolf, R
    [J]. JOURNAL OF THE ACM, 2001, 48 (04) : 778 - 797
  • [5] BERZINA A, 2004, P SOFSEM 04, P140
  • [6] Boyer M, 1998, FORTSCHR PHYS, V46, P493, DOI 10.1002/(SICI)1521-3978(199806)46:4/5<493::AID-PROP493>3.0.CO
  • [7] 2-P
  • [8] BUHRMAN H, 2001, P 16 IEEE C COMP COM, P131
  • [9] DORN S, 2006, UNPUB THEORY COMPUTI
  • [10] DORN S, 2004, THESIS U APPL SCI MI
123