  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.
