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 <johnkcl...@gmail.com> wrote: > On Sat, Sep 21, 2019 at 4:27 PM Lawrence Crowell < > goldenfieldquaterni...@gmail.com> 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 everything-list+unsubscr...@googlegroups.com. > 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 everything-list+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/everything-list/CA%2BBCJUgKwHhgs5pWmoZbN2Mqv1cufHf3O6qhJwAfC%3DYTxd3vPA%40mail.gmail.com.
