On Mon, Oct 22, 2018 at 8:18 AM Philip Thrift <[email protected]> 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.
