# BQP algorithm for two graph bisection problems and its implications on NP $\subseteq$ BQP

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?

• Afaik, this paper is not well-known in the quantum computing community. It is somewhat suspicious that it has not been listed in the Quantum Algorithm Zoo. I am also fairly confused to see the paper in that journal. Jan 14 '16 at 18:01
• I have seen some suggestions that the algorithm does post-selection (and therefore is not surprising since @ScottAaronson showed PostBQP = PP). For example here algorithmicassertions.com/quantum/2015/08/01/… and here scottaaronson.com/blog/?p=2408#comment-743305. Jan 14 '16 at 21:31