Upper bounds on quantum query complexity inspired by the Elitzur-Vaidman bomb tester

Inspired by the Elitzur-Vaidman bomb testing problem [arXiv:hep-th/9305002], we introduce a new query complexity model, which we call bomb query complexity B(f). We investigate its relationship with the usual quantum query complexity Q(f), and show that B(f)=Θ(Q(f)²). This result gives a new method to upper bound the quantum query complexity: we give a method of finding bomb query algorithms from classical algorithms, which then provide nonconstructive upper bounds on Q(f)=Θ\(sqrt{B(f\)}). We subsequently were able to give explicit quantum algorithms matching our upper bound method. We apply this method on 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.5sqrt{log n}\) [arXiv:quant-ph/0606127]. Applying this method to the maximum bipartite matching problem gives an O\(n^1.75\) algorithm, improving the best known trivial O\(n²\) upper bound.