  The aim of the paper is to answer a long-standing open problem on the
relationship between NP and BQP. The paper shows that BQP contains NP by
proposing a BQP quantum algorithm for the MAX-E3-SAT problem which is a
fundamental NP-hard problem. Given an E3-CNF Boolean formula, the aim of the
MAX-E3-SAT problem is to find the variable assignment that maximizes the number
of satisfied clauses. The proposed algorithm runs in $O(m^2)$ for an E3-CNF
Boolean formula with $m$ clauses and in the worst case runs in $O(n^6)$ for an
E3-CNF Boolean formula with $n$ inputs. The proposed algorithm maximizes the
set of satisfied clauses 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 resources. In addition to solving the MAX-E3-SAT problem, the
proposed algorithm can also be used to decide if an E3-CNF Boolean formula is
satisfiable or not, which is an NP-complete problem, based on the maximum
number of satisfied clauses.
