2006/06/15 by Furrow, Bartholomew
#FOS: Physical sciences #Quantum Physics (quant-ph)
paper · doi:10.48550/arxiv.quant-ph/0606127
We create a variety of new quantum algorithms that use Grover's algorithm and similar techniques to give polynomial speedups over their classical counterparts. We begin by introducing a set of tools that carefully minimize the impact of errors on running time; those tools provide us with speedups to already-published quantum algorithms, such as improving Durr, Heiligman, Hoyer and Mhalla's algorithm for single-source shortest paths [quant-ph/0401091] by a factor of lg N. The algorithms we construct from scratch have a range of speedups, from O(E)->O(sqrt(VE lg V)) speedups in graph theory to an O(N3)->O(N2) speedup in dynamic programming.