I read the paper

which is published in Springer's journal Quantum Information Processing. The paper seems to claim that it provides a BQP algorithm for the NP-hard problems of min-bisection and max-bisection.

If true, this should imply that $NP\subseteq BQP$, which would be very surprising because it is common conjecture that $NP\not\subseteq BQP$. There is even a result that relative to an random oracle, $NP\nsubseteq BQP$ with probability 1.

I'm puzzled because it seems to me that the complexity analysis of the paper concerns query complexity not time complexity. In other words, it is not clear the algorithm is in BQP. On the other, the implications of the paper should have been clear to any reviewer in quantum computing so I expect that the reviewers really checked all the details of the paper to confirm the result otherwise it wouldn't be published.

Is the algorithm in the paper really in BQP? Does the paper really imply that NP $\subseteq$ BQP?


1 Answer 1


Another paper with the same idea by Ahmed Younes and Jonathan E. Rowe, A Polynomial Time Bounded-error Quantum Algorithm for Boolean Satisfiability. The algorithm is not polynomial time.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.