pdf icon
Volume 12 (2016) Article 18 pp. 1-35
Upper Bounds on Quantum Query Complexity Inspired by the Elitzur--Vaidman Bomb Tester
Received: August 17, 2015
Revised: February 29, 2016
Published: November 28, 2016
Download article from ToC site:
[PDF (324K)] [PS (1945K)] [Source ZIP]
Keywords: algorithms, query complexity, quantum algorithms, quantum query complexity, graph algorithms, Elitzur-Vaidman bomb tester, adversary method, maximum bipartite matching
ACM Classification: F.1.2, F.1.3, F.2.2
AMS Classification: 81P68, 68Q12, 68Q17, 68Q05

Abstract: [Plain Text Version]

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)$ (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.

A conference version of this paper appeared in the Proceedings of the 30th Computational Complexity Conference, 2015.