[ExI] Quantum Computers

John Clark johnkclark at gmail.com
Mon Oct 22 14:22:13 UTC 2018


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 computer 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.extropy.org/pipermail/extropy-chat/attachments/20181022/96f65a34/attachment.html>


More information about the extropy-chat mailing list