Blog
About

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

      Quantum algorithms for graph problems with cut queries

      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

          Let \(G\) be an \(n\)-vertex graph with \(m\) edges. When asked a subset \(S\) of vertices, a cut query on \(G\) returns the number of edges of \(G\) that have exactly one endpoint in \(S\). We show that there is a bounded-error quantum algorithm that determines all connected components of \(G\) after making \(O(\log(n)^5)\) many cut queries. In contrast, it follows from results in communication complexity that any randomized algorithm even just to decide whether the graph is connected or not must make at least \(\Omega(n/\log(n))\) many cut queries. We further show that with \(O(\log(n)^7)\) many cut queries a quantum algorithm can with high probability output a spanning forest for \(G\). En route to proving these results, we design quantum algorithms for learning a graph using cut queries. We show that a quantum algorithm can learn a graph with maximum degree \(d\) after \(O(d \log(n)^2)\) many cut queries, and can learn a general graph with \(O(\sqrt{m} \log(n)^{3/2})\) many cut queries. These two upper bounds are tight up to the poly-logarithmic factors, and compare to \(\Omega(dn)\) and \(\Omega(m/\log(n))\) lower bounds on the number of cut queries needed by a randomized algorithm for the same problems, respectively. The key ingredients in our results are the Bernstein-Vazirani algorithm, approximate counting with "OR queries", and learning sparse vectors from inner products as in compressed sensing.

          Related collections

          Author and article information

          Journal
          16 July 2020
          Article
          2007.08285

          http://creativecommons.org/licenses/by/4.0/

          Custom metadata
          42 pages
          cs.DS quant-ph

          Quantum physics & Field theory, Data structures & Algorithms

          Comments

          Comment on this article