28
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

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

      Preprint
      ,

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          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.

          Related collections

          Most cited references23

          • Record: found
          • Abstract: not found
          • Article: not found

          The Zeno’s paradox in quantum theory

            Bookmark
            • Record: found
            • Abstract: not found
            • Article: not found

            An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs

              Bookmark
              • Record: found
              • Abstract: not found
              • Article: not found

              Quantum Walk Algorithm for Element Distinctness

                Bookmark

                Author and article information

                Journal
                2014-10-03
                2014-11-26
                Article
                1410.0932
                2e829473-7e8e-4f19-abb4-0a721fd69f1b

                http://arxiv.org/licenses/nonexclusive-distrib/1.0/

                History
                Custom metadata
                MIT-CTP/4592
                32 pages. Minor revisions and corrections. Regev and Schiff's proof that P(OR) = \Omega(N) removed
                quant-ph cs.CC

                Quantum physics & Field theory,Theoretical computer science
                Quantum physics & Field theory, Theoretical computer science

                Comments

                Comment on this article