Abstract
Inspired by the Elitzur--Vaidman bomb testing problem (1993), we introduce a new query complexity model, which we call bomb query complexity, B(f)B(f). We investigate its relationship with the usual quantum query complexity Q(f), and show that B(f)=Θ(Q(f)^2).
This result gives a new method to derive upper bounds on quantum query complexity: we give a method of finding bomb query algorithms from classical algorithms, which then provide non-constructive upper bounds on Q(f)=Θ(√B(f)). Subsequently, we were able to give explicit quantum algorithms matching our new bounds. We apply this method to the single-source shortest paths problem on unweighted graphs, obtaining an algorithm with O(n^1.5) quantum query complexity, improving the best known algorithm of O(n^1.5log(n))(Dürr et al. 2006, Furrow 2008). Applying this method to the maximum bipartite matching problem gives an algorithm with O(n^1.75) quantum query complexity, improving the best known (trivial) O(n^2) upper bound.