4 ms·
It's worth pointing out that they already claim to have proven NP ⊆ BQP > The common belief concerning the relationship between NP and BQP was that NP is not c
by Rauchg 11y ago
It's worth pointing out that they already claim to have proven NP ⊆ BQP
> The common belief concerning the relationship between NP and BQP was that NP is not contained in BQP (e.g see chapter 15 of [8]. However, a recent paper by one of the current authors has shown that an NP-hard problem (Graph
Bisection) can be efficiently solved, with low failure probability, by a quantum algorithm [13]. This implies that NP is in fact contained within BQP, as any NP problem can be polynomially reduced to an NP-hard problem
- jsprogrammer 11y ago>any NP problem can be polynomially reduced to an NP-hard problem Except that there is some probability that the algorithm will be unable to solve the problem?
- eru 11y agoSuccess/Failure would be independent between runs. Ie if you fail, you just run again.