<div><span class="gmail_quote">On 12/30/07, <b class="gmail_sendername">Miguel Mitrofanov</b> <<a href="mailto:miguelimo38@yandex.ru">miguelimo38@yandex.ru</a>> wrote:</span></div>
<div>
<blockquote class="gmail_quote" style="PADDING-LEFT: 1ex; MARGIN: 0px 0px 0px 0.8ex; BORDER-LEFT: #ccc 1px solid">> If I understand correctly, a quantum computer might solve problems in<br>> NP in polynomial time, which is assumed not to be possible for
<br>> deterministic computers.<br><br>No! Moreover, there is a hypothesis that the only problems quantum<br>computer can solve in polynomial time are those that the usual<br>computer can.</blockquote>
<div> </div>
<div>
<div>According to <a href="http://en.wikipedia.org/wiki/Quantum_computer">http://en.wikipedia.org/wiki/Quantum_computer</a></div>
<div> </div>
<div>The class of problems that can be efficiently solved by quantum computers is called BQP, for "bounded error, quantum, polynomial time". Quantum computers only run probabilistic algorithms, so BQP on quantum computers is the counterpart of BPP on classical computers. It is defined as the set of problems solvable with a polynomial-time algorithm, whose probability of error is bounded away from one quarter.[18] A quantum computer is said to "solve" a problem if, for every instance, its answer will be right with high probability. If that solution runs in polynomial time, then that problem is in BQP.
</div>
<div> </div>
<div>BQP is suspected to be disjoint from NP-complete and a strict superset of P, but that is not known. Both integer factorization and discrete log are in BQP. Both of these problems are NP problems suspected to be outside BPP, and hence outside P. Both are suspected to not be NP-complete.
<br> </div>
<div> </div>
<div>---</div>
<div> </div>
<div>So, if you come up with a polynomial-time algorithm for integer factorization that doesn't use quantum computers, you could probably make a lot of money cracking people's RSA keys.</div>
<div> </div>
<div> -- ryan<br><br> </div></div><br> </div>