By Roger A. Grimes
You were alive during an incredibly significant historic computer event that happened last Friday (9/20/19) – it was publicly announced that quantum supremacy was achieved. And make no doubt about it, this is as significant as the creation of the Internet and what it means is both fantastical and threatening.
Because I just finished up my latest book on quantum computing and the coming cryptographic break, Cryptography Apocalypse (https://www.amazon.com/Cryptography-Apocalypse-Preparing-Quantum-Computing/dp/1119618193), I’ve been heavily into this subject for the last few years. I’ve interviewed over a hundred quantum physicists and quantum computer experts and they are all sitting gob smacked this week.
A few days ago, it was reported (https://gizmodo.com/google-says-its-achieved-quantum-supremacy-a-world-fir-1838299829 and https://fortune.com/2019/09/20/google-claims-quantum-supremacy) that Google, one of the primary heavy hitters in the race to make usable quantum computers, temporarily posted a research paper on a NASA web site which revealed a Google quantum computer had reached quantum supremacy.
Quantum supremacy is the moment in time when a quantum computer finally does something that a traditional, binary, classical, computer cannot. It can be achieved in terms of raw computational speed or performing even an otherwise “ordinary” math problem that a classical computer simply isn’t capable of (i.e. it doesn’t have to be speed related). Google’s report seems to indicate it was a bit of both. According to the now retracted report (more on that in a moment), Google was able to accomplish in 3 minutes using a quantum computer what the world’s fastest computer would take 10,000 years to do. We’ll talk more about this particular detail. Most of the other early articles covering the quantum supremacy achievement don’t appear to understand the significance.
Ever since Richard Feynman talked about using the fantastical properties of quantum mechanics to make a new paradigm of computing in 1959, the world has waited for the day when quantum supremacy would happen. The first quantum computer was made in 1998 and it has taken mankind another 21 years to get them to the point to where they will begin to take over particular tasks and new tasks that regular computers can’t perform. After this moment, no serious large company, government, or country will want to stay on or focus on the older types of computers. There was a computer world before and there is now a new computer world, shiny and new, after. Yes, traditional computers will stay in our lives for decades to come, but a technological wall has been breached, and it means wonderous new things, both good and bad. Within the next decade, any company or organization without a quantum computer will be seen as old and fuddy-duddy. You might as well just pull out an abacus and move beads around. Quantum supremacy is a HUGE milestone in the world of computing. And you were alive to see it happen.
Google Retracted the Report
For reasons currently unknown, Google retracted their report before more than a few people saw it. They are now being very close lipped about it. There is a chance that the report was fake, due to a hack, or posted well before Google has actually achieved quantum supremacy, but this explanation seems less likely. For one, Google, IBM, and China have been publicly declaring (https://www.wired.com/story/google-alibaba-spar-over-timeline-for-quantum-supremacy/) that they were going to achieve quantum supremacy soon, as early as this year (although they also said that the previous year or two). But this year’s proclamations seemed different and more serious. A lot of people, skeptical and otherwise, have been waiting for a supremacy announcement from one of the heavy hitters to land before the end of the year. Me, I’ve been telling anyone who will listen to me for the last year that I thought it was going to be happening before the end of the year, and that perhaps it has already occurred and we just didn’t know. I gave that speech the night before the Google “leak” at a Blockspaces meeting (https://www.eventbrite.com/e/quantum-day-of-reckoning-w-roger-grimes-masterminds-social-tickets-70728838861#).
Now there is still a chance that Google hasn’t achieved quantum supremacy, but it seems to that if it hadn’t happened, that Google would be disavowing the post and not being radio silent on the subject. Seems more like this was an accidental release ahead of some previously discussed PR push strategy. These sorts of premature leaks are not uncommon in the computer world. Perhaps Google was waiting to make the announcement at a big conference, in conjunction with another entity, or has been gag ordered by an NDA until a certainly release date. It’s even possible that they haven’t achieved it yet but are close and the report they released was in beta form. Either way, if I was a betting man…and I am a betting man…I think quantum supremacy has been achieved or will be achieved very, very soon. I expect the official confirmation within days to weeks. Schrödinger’s cat is out of the bag.
What a Quantum World Brings Us
Quantum computing will bring us many wonderful things, many of which we cannot imagine right now. I look back at what I believed was possible back when I first got into computers seriously, back in 1986, with my first $2500 PC, with green monochrome screen and 20 megabyte hard drive. I could not have imagined that during my lifetime that we would have devices which could fit my entire dream record collection on a small device the size of a finger. I could not have imagined that we would have terabytes of storage space for sale under $100 on a chip the size of a postage stamp. I could not have imagined that I could use my small phone to look up any fact of the world in seconds, and that we would be using a large portion of that god-like power to watch cat videos.
Quantum computers will allow us to better understand how the universe works. Quantum mechanics, particles, and properties are how everything in the universe works – you, me, traditional computers, and all of nature. Up until this point, we could not model how everything in the universe (or multiple universes, for that matter) truly works. It’s all been theory and speculation. Now, with enough serious quantum computers, for the first time, we can literally model and figure out how everything that is everything works. We will get better weather prediction, better chemicals, better medicines with less side effects, better traffic management, better artificial intelligence, and better be able to predict and detect where scarce resources, like gas and oil, are. Everything can be better predicted and focused.
Of course, it also means that it will bring us more accurate and destructive military weapons, defenses, and offenses. That’s the way of the world. You can bet that the world’s governments, militaries, and large organizations are going to wring every last competitive benefit from quantum computers. Quantum computers will give us harder to break and eavesdrop on encryption. Notice I didn’t say unbreakable encryption. Many quantum scientists say that…but that’s only in a lab. In the real world, quantum encryption is likely to be hacked just like everything before it, but it will be significantly harder to do. But if you hear “unhackable”, please keep your laughter to low volumes.
The Cryptographic Break Might Be Near Or Has Already Happened
In Google’s announcement, they discussed a very specific comparison – that they had solved in 3 minutes what would take the world’s most powerful computer 10,000 years to do. The world’s most powerful computer is called Summit (https://www.ornl.gov/news/ornl-launches-summit-supercomputer) and is run by the Oakridge National Laboratory in Oakridge, TN, United States. It contains over 101,000 dual core processors and 27,600 graphics processors and is capable of over 200 petaflops (200,000 trillion calculations per second). And Google’s quantum computer can do what it does in 10,000 years in 3 minutes.
To people in quantum computing, Google’s announcement is particularly informative. Quantum computer’s raw computing performance for many problems isn’t that extraordinary. There are even many cases where quantum computers are slower than traditional computers. But we do know of two particular types of problems where quantum computers especially excel. One type is called un-structured searches. Because of a quantum algorithm, known as Grover’s algorithm (https://en.wikipedia.org/wiki/Grover's_algorithm), quantum computers can give a quadratic (square root) speed up on un-order searches. Most relevantly, it halves the protection of symmetric keys and hashes. It essentially lessens the protective security of AES-256 to AES-128 and SHA2-256 to SHA2-128, and so on. Anyone wishing to be protected against the cryptographic gains of quantum computing should double the key sizes of their symmetric ciphers and hashes.
The other problem where quantum computers really have a far large advantage is solving (i.e. factoring) equations that use very large prime numbers in mathematical formulas, which is what most of our modern day, traditional public key, asymmetric algorithms are based on. In 1994, a quantum physicist known as Peter Shor, showed that these types of very hard to factor problems could be solved in seconds to minutes on a quantum computer. We just need enough qubits (quantum bits) to help out. Since 1994, everyone has understood that if we could create quantum computers and create them with enough qubits (Shor’s algorithm requires double plus a few more qubits for every bit of an asymmetric key you are trying to crack), that today’s asymmetric ciphers and digital signature schemes would fall.
Back in 1994, it was quite a thing to realize. But we didn’t even have a working quantum computer. That took until 1998, and even then it only had 2 qubits. But even with 2 qubits, the quantum computing team proved that using Shor’s algorithm would work on any size prime number equation if we had the right number of stable qubits. Since then, all the quantum computer manufacturers (and there are over a 100 separate groups working on quantum computers), have been trying to add more and more qubits and stability (error correction) to their computers. For many years, quantum vendors just to publicly announce each incremental advance in qubit size (or stability) whenever they occurred.
And then for reasons no one understand, last year they stopped giving updates (while at the same time some of them announcing that they were closed to quantum supremacy). The sudden radio silence led me to believe that we were definitely getting ready to hear some big announcement this year, and I said so in my book and every presentation on quantum computers I gave. It would be an understatement to say that my declaration was met by mostly skepticism, ridicule, and even laughter, especially by those closest and working the longest in quantum computers. I was taking a professional risk every time I said I thought quantum supremacy was near, even though major vendors were also, occasionally, for the last few years saying the same thing. But I couldn’t get past why all the sudden radio silence on qubit count and stability announcements and the glaring fact that you can’t get to pending quantum supremacy without either significantly increasing the number of qubits or making the existing ones far more stable.
Then Google announced (and retracted) their reach of quantum supremacy. You can’t take back what you already leaked out, especially when you’re not publicly discounting that it was either an accident or a premature release. As long as that retracted report isn’t determined to be a complete hoax, I think it means quantum supremacy has been reached or is very, very near. Who makes official reports on major computing milestones without some basis of fact to support it?
It has been reported (https://fortune.com/2019/09/20/google-claims-quantum-supremacy) that Google’s leaked research paper used a third type of problem that quantum computers can significantly outperform classical computers on, sampling random numbers, and did so by increasing the stability of a small number of qubits. It’s not nearly as interesting as cracking large prime number equations, but it still means they have likely achieved very stable qubits, which benefits every other possible quantum problem. It benefits the problems solved by Grover’s and Shor’s algorithms.
And if you have one or 50+ really stable qubits, it’s not that hard to make a million of them. If there is something that the United States (since the days of Henry Ford) and China can do it’s make a lot of something once the first one is made. To be sure, I’m overly simplifying the difficulty of creating quantum computers with more and more qubits. But I’m not the one announcing that quantum supremacy has been reached. There is no way to get to quantum supremacy and not be significantly further down the road to creating significantly more powerful quantum computers and then moving onto cracking much of the encryption running the world.
And this means we are likely closer to breaking a lot of the traditional cryptography the world depends on, and possibly closer than most of us imagined. The National Institute of Standards and Technology (NIST) is conducting a public contest to submit and select the US’s new quantum-resistant asymmetric ciphers and digital signature schemes (https://csrc.nist.gov/News/2019/pqc-standardization-process-2nd-round-candidates). Over 80 post-quantum ciphers and schemes were submitted in round 1. Twenty-six of them (17 asymmetric ciphers and 9 digital signatures) algorithms were selected for round 2. NIST estimated that final candidates would be selected between 2022 and 2024, although they reserved the right to quicken up the contest based upon significant changes in quantum computers.
Reaching quantum supremacy certainly counts as a significant event. To be clear, there were people like me already thinking that quantum supremacy would be reached this year. But most observers and people were not so sure. Now that it has likely been done, everyone’s post quantum migration plans probably need to be sped up to earlier estimations.
Preparing for a Post-Quantum World
So how do you prepare for a post-quantum world? It’s a series of steps, including:
- Take a data-protection inventory of all data and systems. Figure out what data needs to be protected for how long, and what ciphers, schemes, and key sizes are being used to protect them currently. Determine what is most critical to protect when.
- Remove very critical data from being able to be eavesdropped on when protected by quantum-susceptible ciphers and schemes.
- Double the size of any symmetric ciphers and hashes, at least have a minimum of 256-bits of protection. Use 512-bits of protection for anything you want to keep secret beyond a few years.
- Increase the key size of your asymmetric ciphers and digital signatures to 4096-bit for anything you care to keep secret for more than a few years.
- Start watching what NIST does. When they announce the post-quantum cipher winners, start moving your critical data and systems to them ASAP.
- Be prepared to start looking at quantum-based random number generators, quantum-based key distribution systems, and quantum computing.
- Eventually, maybe a decade or so from now, you’ll be moving to quantum-based (not quantum-resistant) crypto.
Here’s a graphical representation of the main stages:
If you are interested in the details of what you and your company can do now to prepare for the coming quantum cryptographic break, I can’t truly think of a better resource than the book I just wrote on the subject, called Cryptography Apocalypse (https://www.amazon.com/Cryptography-Apocalypse-Preparing-Quantum-Computing/dp/1119618193).
The chapter list is:
Part I – Quantum Computing Primer
Chap. 1- What is Quantum?
Chap. 2 – Quantum Computers
Chap. 3- How Can Quantum Computing Break Today’s Cryptography?
Chap. 4- When Will the Quantum Break Happen?
Chap. 5- What Will A Post-Quantum World Look Like
Part II - Preparing for the Quantum Break
Chap. 6- Quantum Resistant Cryptography
Chap. 7 - Quantum Cryptography
Chap. 8- Quantum Networking
Chap. 9- Preparing Now
Appendix of Quantum Information Sources
Chapter 9 is the whole reason to read this book. A thousand people know more than me about quantum mechanics and quantum computers, although I think I do a fairly good job at summarizing both. But I haven’t seen any article or book that tells you precisely what your company should be doing today to prepare for the coming quantum cryptographic break. It takes you step-by-step, including letters for senior management, FAQs, presentations, and project plans. Of course, I could be a little biased.