Title | Upper bounds on quantum query complexity inspired by the Elitzur-Vaidman bomb tester |

Publication Type | Journal Article |

Year of Publication | 2016 |

Authors | Lin, CYen-Yu, Lin, H-H |

Journal | Theory of Computing |

Volume | 12 |

Issue | 18 |

Pages | 1-35 |

Date Published | 2016/11/28 |

Abstract | Inspired by the Elitzur-Vaidman bomb testing problem [arXiv:hep-th/9305002], 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 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}\sqrt{\log n})$ [arXiv:quant-ph/0606127]. 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. |

URL | http://theoryofcomputing.org/articles/v012a018/ |

DOI | 10.4086/toc.2016.v012a018 |

Original Publication | Proceeding CCC '15 Proceedings of the 30th Conference on Computational Complexity, Pages 537-566 |