On Monday, September 23, 2019 at 8:23:44 AM UTC-5, John Clark wrote: > > On Mon, Sep 23, 2019 at 7:42 AM Bruno Marchal <[email protected] > <javascript:>> wrote: > > *> Mathematically, it is still an open problem if a quantum computer >> really speed-up the computations, but like with P = NP, most experts have >> few doubt that this is the case.* > > > I think you mean P is not equal to NP, most mathematicians would be > astonished if it turned out that P=NP .... but that doesn't mean it > couldn't happen. > > John K Clark >
Quantum computers do give a speed up, but it is not exponential in some way that permits P = NP. At least so far this has not been demonstrated. Quantum computing would maybe solve this as P = NP if the output could be done entirely in a nonlocal fashion, but quantum computing requires a classical communication of a result, or intermittent classical results, which spoils that hope. Quantum gravity may in some way come to the rescue, or at least expand the computability domain of quantum computing. We still though will have the issue of local operators and classical communications (LOCC). The issue of P vs NP is very difficult as it turns out, and it appears to involve the Riemann zeta function. There are potentially very deep results lurking here waiting to be found. LC -- You received this message because you are subscribed to the Google Groups "Everything List" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/everything-list/4b7c2140-41b7-4220-9141-81bb39dd643f%40googlegroups.com.
