Theory of Computing
-------------------
Title     : Upper Bounds on Quantum Query Complexity Inspired by the Elitzur--Vaidman Bomb Tester
Authors   : Cedric Yen-Yu Lin and Han-Hsuan Lin
Volume    : 12
Number    : 18
Pages     : 1-35
URL       : https://theoryofcomputing.org/articles/v012a018

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)$. We investigate its relationship with the usual
quantum query complexity $Q(f)$, and show that $B(f)=\Theta(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)=\Theta(\sqrt{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.5}\log n)$
(Durr 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.

A conference version of this paper appeared in the Proceedings of the
30th Computational Complexity Conference, 2015.
DOI: 10.4230/LIPIcs.CCC.2015.537