Quantum algorithms for optimal graph traversal problems
Sebastian Dörn · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · 2007
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.