It’s been a long day for me, so I can’t write this up as well as I’d like. No one seems to have mentioned what might be a breakthrough in computing.
Using the standard models for computing, accomplishing tasks such as factoring large integers, breaking codes, etc., takes a very long time; no one on this planet currently knows how to factor an n-digit integer into primes without taking exponential time (i.e., a^n for some a > 1). A few decades ago, a new paradigm was introduced: quantum computing. Quantum computing uses the collapse of wave functions which is a central concept (and mystery) in quantum mechanics, and allows an exponential amount of work to be accomplished in linear time. To use the pie metaphor which is common here, imagine how many ways there are to eat a slice of pie, and suppose you do them all at once.
Decades ago, a linear-time algorithm for factoring integers was written by Shor, but there weren’t any machines to run it on.
Google announced today a breakthrough in the physical aspects of quantum computing. They ran a calculation (to verify the fairness of a random number generator) in under 4 minutes that they claim would take 10,000 years using conventional hardware and algorithms, establishing “quantum supremacy.” (No, this has nothing to do with weirdos goosestepping in white sheets.)
It may not sound like much, but you have to start somewhere.
IBM (the other major name in quantum computing research) disputes this; they cut down the 10,000-year estimate to a few days. Still nothing to sneeze at.
(This debate is sure to keep going for a while.)
One of my students emailed me a couple of links with information, as well as the debate:
One of the links provides a 3-minute video on “Quantum Supremacy”.