Share Email Print

Proceedings Paper

Quantum algorithms for optimal graph traversal problems
Author(s): Sebastian Dörn
Format Member Price Non-Member Price
PDF $14.40 $18.00
cover GOOD NEWS! Your organization subscribes to the SPIE Digital Library. You may be able to download this paper for free. Check Access

Paper Abstract

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.

Paper Details

Date Published: 25 April 2007
PDF: 10 pages
Proc. SPIE 6573, Quantum Information and Computation V, 65730D (25 April 2007); doi: 10.1117/12.719158
Show Author Affiliations
Sebastian Dörn, Univ. Ulm (Germany)

Published in SPIE Proceedings Vol. 6573:
Quantum Information and Computation V
Eric J. Donkor; Andrew R. Pirich; Howard E. Brandt, Editor(s)

© SPIE. Terms of Use
Back to Top