Institute of Information Science, Academia Sinica

Inspired by the Elitzur-Vaidman bomb testing problem, 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)=[@BackSlash]Theta(Q(f)^2)$.

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)=[@BackSlash]Theta([@BackSlash]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.5}[@BackSlash]sqrt{[@BackSlash]log n})$. Applying this method to the maximum bipartite matching problem gives an $O(n^{1.75})$ algorithm, improving the best known trivial $O(n^2)$ upper bound.

Han-Hsuan Lin received his Ph.D. in physics from M.I.T. in 2015. After that, he came back to Taiwan for the mandatory military service. He research interests are quantum algorithms and quantum computational complexity.