Lin, Cedric YenYu ;
Lin, HanHsuan
Upper Bounds on Quantum Query Complexity Inspired by the ElitzurVaidman Bomb Tester
Abstract
Inspired by the ElitzurVaidman bomb testing problem [Elitzur/Vaidman 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 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)=Theta(sqrt(B(f))). We subsequently were able to give explicit quantum algorithms matching our upper bound method. We apply this method on the singlesource 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) * sqrt(log(n))) [Furrow, 2008]. 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.
BibTeX  Entry
@InProceedings{lin_et_al:LIPIcs:2015:5063,
author = {Cedric YenYu Lin and HanHsuan Lin},
title = {{Upper Bounds on Quantum Query Complexity Inspired by the ElitzurVaidman Bomb Tester}},
booktitle = {30th Conference on Computational Complexity (CCC 2015)},
pages = {537566},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897811},
ISSN = {18688969},
year = {2015},
volume = {33},
editor = {David Zuckerman},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5063},
URN = {urn:nbn:de:0030drops50635},
doi = {10.4230/LIPIcs.CCC.2015.537},
annote = {Keywords: Quantum Algorithms, Query Complexity, ElitzurVaidman Bomb Tester, Adversary Method, Maximum Bipartite Matching}
}
2015
Keywords: 

Quantum Algorithms, Query Complexity, ElitzurVaidman Bomb Tester, Adversary Method, Maximum Bipartite Matching 
Seminar: 

30th Conference on Computational Complexity (CCC 2015)

Issue date: 

2015 
Date of publication: 

2015 