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

Question

I read the paper

• Ahmed Younes, "A Bounded-error Quantum Polynomial Time Algorithm for Two Graph Bisection Problems", 2015. doi:10.1007/s11128-015-1069-y

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.

• Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani, "Strengths and Weaknesses of Quantum Computing", 1997. doi: 10.1137/S0097539796300933

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?

• Ahmed Younes, Jonathan E. Rowe, "A Polynomial Time Bounded-error Quantum Algorithm for Boolean Satisfiability", 2015

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.