That is interesting. It tends to go along with my thesis that quantum computers can solve NP as P, but we can't receive the readout without a classical information system that bounds this in polynomial time. This is in effect the BPQ nature of quantum computers. The catch though is that the polynomial bounds on a quantum computer are generally much lower with time than with a straight up classical computer. From what I understand this is known on a case by case basis, but there is no general proof of it.
LC On Monday, October 22, 2018 at 9:19:21 AM UTC-5, John Clark wrote: > > On Mon, Oct 22, 2018 at 8:18 AM Philip Thrift <cloud...@gmail.com > <javascript:>> wrote: > > > *If you look at the sum-over-histories semantics of quantum computers, >> then parallelism could increase exponentially in the number of qubits, but >> in actual implementation that exponential growth might not be that much >> over linear, and when the number of qubits gets big, problems arise. * >> > > That had been the worry until very recently, it had been feared Quantum > Computers would never be practical because as the problems they worked on > got bigger the error rate of the components of the computer would have to > get better and better until you would need impossible precision to do > anything. And until recently nobody had a rigorous proof that Quantum > Computers were inherently superior to conventional computers. We still > don't know if a quantum computer could solve all nondeterministic > polynomial time problem in polynomial time but just a few months ago a > proof was found that even if, to everybody's surprise, it turned out that > P=NP and even if we had a algorithm that could solve NP problems on a > conventional computer in polynomial time there would STILL be a class of > problems a conventional computer couldn't solve efficiently but a quantum > computer could. > > https://eccc.weizmann.ac.il/report/2018/107/ > > And then just a few days ago a proof was found that the error rate of the > components of the Quantum Computer could remain constant as the size of > this class of problems increased and the Quantum Computer would still work. > That means they would be scalable, if you can build a small Quantum > Computer you can build a large one. Even better the machine would work even > if the components were arranged in a simple 2D grid, and that makes it > far easier to actually engineer such a machine: > > http://science.sciencemag.org/content/sci/362/6412/289.full.pdf > > http://science.sciencemag.org/content/sci/362/6412/308.full.pdf > > It should be noted that this has so far only been mathematically proven > for a new and exotic class of problems, and nobody knows if they are of > interest in themselves or if they are interesting only because a > conventional computer can't solve them efficiently but a Quantum Computer > can. We still don't have a proof this is also true of the class of problems > we are more familiar with but I think most think it probably is. So maybe > someday somebody will come up with a conventional algorithm that works as > well as Shor's Quantum Factoring Algorithm, but I doubt it. > > 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 post to this group, send email to everything-list@googlegroups.com. Visit this group at https://groups.google.com/group/everything-list. For more options, visit https://groups.google.com/d/optout.
