Upper bounds for query complexity inspired by the Elitzur-Vaidman bomb tester
- 講者Han-Hsuan Lin 博士 (Center for Theoretical Physics, Massachusetts Institute of Technology)
邀請人：鐘楷閔 - 時間2016-10-06 (Thu.) 14:00 ~ 16:00
- 地點資訊所新館107演講廳
摘要
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.
BIO
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.