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

      A Bounded-error Quantum Polynomial Time Algorithm for Two Graph Bisection Problems

      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

          The aim of the paper is to propose a bounded-error quantum polynomial time (BQP) algorithm for the max-bisection and the min-bisection problems. The max-bisection and the min-bisection problems are fundamental NP-hard problems. Given a graph with even number of vertices, the aim of the max-bisection problem is to divide the vertices into two subsets of the same size to maximize the number of edges between the two subsets, while the aim of the min-bisection problem is to minimize the number of edges between the two subsets. The proposed algorithm runs in \(O(m^2)\) for a graph with \(m\) edges and in the worst case runs in \(O(n^4)\) for a dense graph with \(n\) vertices. The proposed algorithm targets a general graph by representing both problems as Boolean constraint satisfaction problems where the set of satisfied constraints are simultaneously maximized/minimized using a novel iterative partial negation and partial measurement technique. The algorithm is shown to achieve an arbitrary high probability of success of \(1-\epsilon\) for small \(\epsilon>0\) using a polynomial space resources.

          Related collections

          Author and article information

          Journal
          23 May 2015
          Article
          10.1007/s11128-015-1069-y
          1505.06284
          7e3c7d7c-298f-47c0-a9da-09172417d214

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

          History
          Custom metadata
          17 Pages, 5 figures
          quant-ph cs.CC cs.DS

          Comments

          Comment on this article