<p>Another paper with the same idea by Ahmed Younes and Jonathan E. Rowe, <a href="http://arxiv.org/abs/1507.05061" rel="nofollow">A Polynomial Time Bounded-error Quantum Algorithm for Boolean Satisfiability</a>. <a href="https://news.ycombinator.com/item?id=9931052" rel="nofollow">The algorithm is not polynomial time.</a></p>

CC BY-SA 3.0
2016-01-15T11:08:45.093Z
Per comments on http://algorithmicassertions.com/quantum/2015/08/27/Simulating-a-Claimed-BQP-NP-Algorithm.html , the paper was withdrawn.
Emil Jeřábek
CC BY-SA 3.0
2016-01-15T02:48:24.483Z
2016-01-15T02:48:24.483Z
user37111
<p>I read the paper </p>

<ul>
<li>Ahmed Younes, "<a href="http://arxiv.org/abs/1505.06284" rel="nofollow">A Bounded-error Quantum Polynomial Time Algorithm for Two Graph Bisection Problems</a>", 2015. <a href="http://link.springer.com/article/10.1007%2Fs11128-015-1069-y" rel="nofollow">doi:10.1007/s11128-015-1069-y</a></li>
</ul>

<p>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.</p>

<p>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.</p>

<ul>
<li>Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani,
"<a href="http://arxiv.org/abs/quant-ph/9701001" rel="nofollow">Strengths and Weaknesses of Quantum Computing</a>", 1997. <a href="http://dx.doi.org/10.1137/S0097539796300933" rel="nofollow">doi: 10.1137/S0097539796300933</a></li>
</ul>

<p>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.</p>

<p>Is the algorithm in the paper really in BQP?
Does the paper really imply that NP $\subseteq$ BQP?</p>

<ul>
<li>Ahmed Younes, Jonathan E. Rowe, "<a href="http://arxiv.org/abs/1507.05061" rel="nofollow">A Polynomial Time Bounded-error Quantum Algorithm for Boolean Satisfiability</a>", 2015</li>
</ul>

CC BY-SA 3.0
2016-01-14T18:01:21.173Z
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](http://math.nist.gov/quantum/zoo/). I am also fairly confused to see the paper in that journal.
Juan Bermejo Vega
CC BY-SA 3.0
2016-01-14T21:31:21.007Z
I have seen some suggestions that the algorithm does post-selection (and therefore is not surprising since @ScottAaronson showed PostBQP = PP). For example here http://algorithmicassertions.com/quantum/2015/08/01/Checking-a-Claimed-BQP-NP-Algorithm.html and here http://www.scottaaronson.com/blog/?p=2408#comment-743305.
Sasho Nikolov
<cc.complexity-theory><np-hardness><quantum-computing>
BQP algorithm for two graph bisection problems and its implications on NP $\subseteq$ BQP
neophyte
# BQP algorithm for two graph bisection problems and its implications on NP $\subseteq$ BQP

(Asked by: username_0 on 2016-01-14)

I read the paper

* Ahmed Younes, "[A Bounded-error Quantum Polynomial Time Algorithm for Two Graph Bisection Problems](http://arxiv.org/abs/1505.06284)", 2015. [doi:10.1007/s11128-015-1069-y](http://link.springer.com/article/10.1007%2Fs11128-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](http://arxiv.org/abs/quant-ph/9701001)", 1997. [doi: 10.1137/S0097539796300933](http://dx.doi.org/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](http://arxiv.org/abs/1507.05061)", 2015

**Tags:** cc.complexity-theory, np-hardness, quantum-computing
> **Comments:**
> **username_1**: 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](http://math.nist.gov/quantum/zoo/). I am also fairly confused to see the paper in that journal.  
> **username_2**: I have seen some suggestions that the algorithm does post-selection (and therefore is not surprising since @ScottAaronson showed PostBQP = PP). For example here http://algorithmicassertions.com/quantum/2015/08/01/Checking-a-Claimed-BQP-NP-Algorithm.html and here http://www.scottaaronson.com/blog/?p=2408#comment-743305.  

---

## 1 answers

### Answer by username_3 on 2016-01-15. Score: 4

Another paper with the same idea by Ahmed Younes and Jonathan E. Rowe, [A Polynomial Time Bounded-error Quantum Algorithm for Boolean Satisfiability](http://arxiv.org/abs/1507.05061). [The algorithm is not polynomial time.](https://news.ycombinator.com/item?id=9931052)

> **Comments:**
> **username_4**: Per comments on http://algorithmicassertions.com/quantum/2015/08/27/Simulating-a-Claimed-BQP-NP-Algorithm.html , the paper was withdrawn.  

---

