Some more details in this article: https://fortune.com/2019/09/20/google-claims-quantum-supremacy/
Jason On Sat, Sep 21, 2019, 5:59 PM John Clark <[email protected]> wrote: > On Sat, Sep 21, 2019 at 4:27 PM Lawrence Crowell < > [email protected]> wrote: > > > Since quantum computers are in a superposition of various states a >> search down a branching tree, say a search along a maze, can be done in a >> superposition of states. This would appear to argue that a quantum computer >> can do an NP, nondeterministic polynomial or non-polynomial, problem in P >> time and space. Not quite, for in order to read the outcome there must be >> classical signals transmitted on state preparations and so forth. This >> means quantum computers are polynomial, but considered to be "bounded >> quantum polynomial." This means they are a considerable speed up, but not >> exponentially so. >> > > I think that's a very reasonable assumption but it has not been proven, it > hasn't even been proven that a conventional algorithm running on a > conventional computer that would produce a exponential speedup does not > exist; however very recently something interesting HAS been proven by Raz > and Tal. This new result does not prove a quantum computer could solve > all nondeterministic polynomial time problems in polynomial time but it > does prove that even if, to virtually all mathematicians astonishment, it > turned out that P=NP and even if we found an algorithm that could solve NP > problems on a conventional computer in polynomial time there would STILL be > a class of problems a conventional computers couldn’t solve efficiently but > a quantum computer could. This new class of problems is very exotic and > it's so new nobody knows yet if they are of fundamental interest in > themselves or if they're interesting for no reason other than that a > conventional computer can’t solve them but a Quantum Computer can. > Polynomial-time quantum algorithms can not be simulated by classical > algorithms in polynomial-time > <https://eccc.weizmann.ac.il/report/2018/107/> > > John K Clark > > > > -- > 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/CAJPayv06WBTrtG0GKhV6SpcQQrcxiAweEZ51uL7hVZjbq30LfQ%40mail.gmail.com > <https://groups.google.com/d/msgid/everything-list/CAJPayv06WBTrtG0GKhV6SpcQQrcxiAweEZ51uL7hVZjbq30LfQ%40mail.gmail.com?utm_medium=email&utm_source=footer> > . > -- 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/CA%2BBCJUgKwHhgs5pWmoZbN2Mqv1cufHf3O6qhJwAfC%3DYTxd3vPA%40mail.gmail.com.
