Upper Bounds on Quantum Query Complexity Inspired by the Elitzur--Vaidman Bomb Tester

摘要

Inspired by the Elitzur--Vaidman bomb testing problem (1993), weintroduce a new query complexity model, which we call bomb querycomplexity , $B(f)$. We investigate its relationship with the usualquantum query complexity $Q(f)$, and show that $B(f)=Theta(Q(f)^2)$. This result gives a new method to derive upper bounds on quantumquery complexity: we give a method of finding bomb query algorithmsfrom classical algorithms, which then provide non-constructive upperbounds on $Q(f)=Theta(sqrt{B(f)})$. Subsequently, we were able togive explicit quantum algorithms matching our new bounds. We applythis method to the single-source shortest paths problem on unweightedgraphs, obtaining an algorithm with $O(n^{1.5})$ quantum querycomplexity, improving the best known algorithm of $O(n^{1.5}log n)$(Dürr et al. 2006, Furrow 2008). Applying this method to themaximum bipartite matching problem gives an algorithm with$O(n^{1.75})$ quantum query complexity, improving the best known(trivial) $O(n^2)$ upper bound. A conference version of this paper appeared in the Proceedings of the 30th Computational Complexity Conference, 2015.