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 <[email protected] > <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 [email protected]. To post to this group, send email to [email protected]. Visit this group at https://groups.google.com/group/everything-list. For more options, visit https://groups.google.com/d/optout.
