3 ms·
This is a pretty dense read. My summary (and I’d appreciate correction from those who follow this more closely): There is a set of problems where the runtime
by nl 9y ago
This is a pretty dense read.
My summary (and I’d appreciate correction from those who follow this more closely):
There is a set of problems where the runtime complexity increase exponentially as the problem size increases on classical computers.
If you can show you have a device where the time complexity only increases linearly and you are faster in clock time then you have shown that your device is superior to classical computing.
Here Google chooses a problem and shows that their 9 qbit quantum device (which they developed) shows exponential speed up between 5 and 9 qbits.
They project that speed up and error rates forward and find it should achieve quantum supremacy at 50 qbits.
(At least that’s my reading. Corrections and expansion very welcome)
- teawithcarl 9y agoYes, I believe you catch the gist of it. It’s a calculation which proves there is indeed a complexity point whereby quantum computing will exceed classical computing ... by proving mathematically that adding enough qubits will suffice that. Keep in mind this proof still hints at “a class of problems/calculations” which qubits will overwhelm, not a general overwhelming of everything. At least that’s my reading. Still this mathematical proof is indeed interesting.
- justifier 9y agogp> it’s a calculation which proves there is indeed a complexity point whereby quantum computing will exceed classical computing 'Prove' is correct for the research but a bit strong for the language of your summary The important caveat: tfa> determination of the smallest computational task that is prohibitively hard for today’s classical computers. 'today's classical computers'.. or more timeless: 'contingent on p!=np'