The shrinking ice floe: how big will the quantum computing market be if classical computing keeps getting better at hard problems?

This article is not official Deloitte research. It is also longer than usual, with more digressions than usual. But I had fun writing it, and I hope you have fun reading it. It’s not quite as geeky as you might fear. But still pretty geeky.

The biggest scientific breakthrough of 2020 was likely last week’s announcement that Google-owned and London-based DeepMind AI system AlphaFold had cracked the protein structure prediction (aka the protein folding) problem in a rigorous independent assessment. This was rightly celebrated in the science media worldwide: it is good news for scientists and companies and people, as it “could significantly accelerate biological research over the long term, unlocking new possibilities in disease understanding and drug discovery among other fields.”

But – and nobody else seems to be talking about this – it may also be bad news for the quantum computing industry. Explaining why will be exactly as horribly complex as you might expect a discussion of protein folding and quantum computers to be. (Some predictions I make are hard…but predicting that this is a confusing subject is a slam dunk!)

A Brief History of Thymine (and other proteins)[1]

1. DNA was first isolated by Friedrich Miescher in 1869. The exact importance of the material was not understood at first, but Miescher did have a theory that it was involved with heredity: good theory! He died in 1895, and the first Nobel in his field was not awarded until 1901, so no Nobel for him.
2. Between 1885 and 1901 Albrecht Kossel was able to isolate, describe and name the five nucleic acid bases: adenine, cytosine, guanine, thymine, and uracil. These bases are the “alphabet” that make up all DNA and RNA, and he was awarded the Nobel Prize for his achievement in 1910.
3. But the alphabet on its own didn’t tell us much, and the next key breakthrough was James Watson and Francis Crick (critically supported by imaging from Rosalind Franklin and Maurice Wilkins) figuring out how the structure of DNA, which was a double helix with pairs of bases (adenine always paired with thymine, and guanine always matched with cytosine.) This insight into structure allowed scientists to figure out how DNA could copy itself, and in 1962 Crick, Watson and Wilkins (but not Franklin, who had died in 1958) were awarded the Nobel Prize.
4. The next “grand challenge” was to sequence the human genome: informally begun in 1985, the Human Genome Project officially began in 1990 with a goal of identifying and mapping all three billion base pairs within 15 years, and was completed in April of 2003, two years ahead of schedule. It was a collaborative effort, and although the project as a whole didn’t win a Nobel, John Sulton, one of the main architects of the project, did win in 2002.

Protein folding is even harder than fitted sheet folding

After the discovery of DNA, bases, and their arrangement, scientists were pretty excited: it was like they knew how to read English, knew all the letters in Hamlet, and even knew the exact order of all the letters. It’s a lot easier to read Hamlet with the right layout, punctuation, chapter headings and so on (the formatting) but it’s not indispensable…if you have the right letters in the right order you can make sense of it.

Around 1960, scientists got a nasty shock: proteins don’t lie around like long strings of letters after they are made, instead they rapidly (milliseconds or less when inside the cell) fold themselves into highly complex structures…and it is the shapes of those structures that determine function.

If you look at the image below, you can see that a string of bases that make up the protein for globin (which, if you add heme, makes up hemoglobin which allows you to live) do nothing as a straight line structure, but when twisted and knotted into the shapes in the finished quaternary structure make perfect little cages to hold the heme molecules.

Thus was born the protein folding problem. As recently as 2017 (nearly 60 years after the problem was first recognised) Jankovi? and Polovi? wrote (emphasis mine):

“The protein folding problem is the most important unsolved problem in structural biochemistry. The problem consists of three related puzzles: i) what is the physical folding code? ii) what is the folding mechanism? and iii) can we predict the 3D structure from the amino acid sequences of proteins? Bearing in mind the importance of protein folding, misfolding, aggregation and assembly in many different disciplines, from biophysics to biomedicine, finding solutions that would be generally applicable is of the utmost importance in biosciences.”

Predicting the 3D structure using a classical computer

Although classical (non-quantum) computers can predict protein structure fairly well for very small proteins, they have had a lot of trouble doing well for larger proteins. Around 1969, Cyrus Levinthal pointed out that a protein of 100 bases could possibly fold itself in 3^198 ways. Using a computer to brute force calculate (the equivalent of a million monkeys eventually writing Hamlet) all the possibilities would take too long, and sometimes the same string of bases can fold in different but still useful shapes, depending on a variety of factors.

Because of the complexity of the problem, the only practical solution to date has been to use various imaging techniques – which don’t work for most proteins in their natural state and are an enormous amount of work. Determining a particular protein’s structure would have been a career’s work for a scientist, assuming they were lucky enough to actually figure it out.

But computer scientists can do better than a million monkeys and wondered if they could solve the problem using more sophisticated approaches than brute force calculation. The Critical Assessment of protein Structure Prediction, or CASP, was a bi-annual competition to do just that, and it started in 1994. It has been called “the Olympics for molecular modelers.” See the chart below for results since 2006. Here are my takeaways:

1. The six CASPs between 2006 and 2016 showed that not much progress was being made: the GDT score (it isn’t a percentage, but that’s a reasonable way to interpret the y axis) bounced around between 30 and 40 for a decade.
2. Not only was the field failing to improve, it was failing in general: a score of 30-40 is not terribly useful in predicting structure.
3. But 2018 saw a near 20 point jump by AlphaFold, and over 50 for the first time, which is beginning to get useful!
4. Then 2020 saw another 30 point jump by AlphaFold2, to nearly 90 on the GDT, which is nearly as accurate as actually imaging the folded protein using the most precise technologies available today.[2]

To put DeepMind’s achievement in context, after the last CASP competition in 2018, someone started a prediction market website asking if we would see a 90% accurate solution…before 2031. That now looks like that breakthrough will occur about a decade earlier than most were expecting!

Weren’t we supposed to be talking about quantum computers?

Yes, and in order to understand why, I need to spend another ten thousand words talking about how quantum computers (QCs) work.

OK, let’s not do that! Luckily, we can proceed as if QCs are magical black boxes. There is no need to understand the inner workings, all you need to know is that:

1. They work differently than classical computers.
2. It is believed that for certain useful tasks, one day they will be much (much much) better/faster than classical computers. When this happens, they will have achieved quantum superiority aka quantum supremacy.
3. That doesn’t mean that your smartphone or PC needs to become a QC! Just because a QC is much better at one kind of computing problem does not mean it is better at ALL computing problems.
4. Think of classical and quantum computers as being like tools in a workshop. A jig saw[3] is much better than a handsaw, hacksaw, chainsaw or circular saw for cutting shapes and curves in wood less than 5 cm thick. But it can’t cut trees, two-by-fours, metal, and so on as well as other kinds of saws. For its specific task a jig saw is irreplaceable…but it is not some magic saw that is superior in all respects.
5. There have been claims from Google in October 2019 using a super-cooled chip called Sycamore and from a team in China in December 2020 using a photonic approach that they have achieved quantum superiority. There is some debate in the QC community if the QC devices really outperformed classical computers, and/or if the problem being solved was useful: being faster at a non-useful problem is kind of meaningless.[4]
6. I have been a tech analyst and/or tech investor since 1990. In the past three decades, I have never seen a quantum computing pitch that didn’t mention that QC would be the perfect tool for solving the protein folding problem, and this would be worth a lot of money. After all, protein folding is, literally, a problem of quantum chemistry. Here is one 2018 article calling QCs “The Dream Machine for Customizing Biology…” and another paper from IBM (very active in the QC space) talking about the main applications for QCs in life sciences has the image below.

Where does the ice floe come in?

In a morning research meeting back in 2005, I talked about a Canadian chip company (ATI Technologies, since acquired by AMD) that was seeing its Total Addressable Market (TAM) for dedicated graphic chips in computers get eaten up by much larger chip companies such as Intel, who had started bundling graphic chip functionality into their own CPUs.

I said it was kind of like a polar bear who got trapped on an ice floe drifting south towards Newfoundland. It might be that the floe was large enough, and the current cold enough that the ice would last long enough to come aground near St. John's, where the bear could hop off, be elected Premier, and live a grand old life of Jiggs dinner every night. (The analogy kind of broke down around this point.) 

But if the floe were small, or it drifted into a warmer current, or both…the poor bear would have nowhere to go and would need to swim for it, likely unsuccessfully. Critically, once the bear was on their floe, events were out of their hands/paws. It wasn’t the bear’s FAULT that the ice was too small, or the current too warm...but those things mattered and had serious consequences.

In the race for supremacy, classical computers are not standing still

They keep getting better. Sometimes it is through improvements in a subset of artificial intelligence (AI) called machine learning, specifically deep learning, the technique that powered DeepMind’s solution in CASP14. Sometimes it is through other bits of software or hardware cleverness.

I try to stay on top of all the announcements, and my own sense is that since I wrote a 2019 Deloitte TMT prediction on quantum computing (published in December of 2018) that I have seen more improvements in classical computing (some hardware, but mainly better software, specifically better AI/machine learning software) at solving these hard problems than progress in building quantum computing devices with more quantum bits (qubits) and more stable and reliable qubits, which combined produce improvements in what IBM calls quantum volume, and is the emerging gold standard for talking about QCs.

The problem with that for the QC industry is the ice floe issue. Back in 2019, there were many hard problems that it was felt quantum computers were likely to be much better than classical computers in solving. QCs hadn’t yet solved them either at that point, but people in the various fields thought that QCs were likely to beat classical devices to the finish line, so invested a lot of money in the quantum space.

If classical computers and algorithms improve rapidly and get there first, and solve the hard problems roughly as well as QCs…then for those problems classical hardware and software will win. QCs cost millions of dollars, are new and untested, typically require specialized PhDs to program (and there aren’t many of those), and are finicky. Classical machines are comparatively cheap as dirt, have been around for decades, and have entire suites of tools to make using them easy for programmers (of which there are literally millions) and scientists. No contest, if the two approaches produce roughly similar results.

I’ve seen this movie before

Around 1975, there was a new semiconductor kid in town. Although almost all chips were made with silicon at that time, Gallium Arsenide (aka GaAs) semiconductors looked really interesting: GaAs had much higher electron mobility (among other benefits) and was going to be really useful for all sort of applications, especially those requiring higher frequencies than silicon chips could manage. There were disadvantages to GaAs such as cost and manufacturability, but a 1985 Fortune article suggested that GaAs would be a $50 billion business by 2000: “By the end of the century, gallium arsenide could account for one-third of the semiconductor industry's business -- which is expected to spiral by then from last year's $15 billion to an astounding $150 billion annually.”

The chart above, of GaAs revenues from 1990-2016, shows that the new material did grow quite a bit…but was well short of $50 billion, or even $5 billion by 2000...despite the fact that the overall semi industry reached $200 billion in revenues that year! In fact, the industry didn’t even surpass the $5 billion mark until 2011. What happened?

Some of it was due to the fact that the disadvantages of GaAs chips didn’t go away as quickly as some had hoped. But the biggest problem was that the ice floe kept getting smaller: silicon improved in ways that materials scientists were surprised by, and silicon chips were able to do more and more things (especially around higher frequencies) that had previously been thought impossible for silicon and needed GaAs. Every time that happened, the market for GaAs got a bit smaller.

Concluding thoughts

1. We could see a QC innovation explosion next week, where some company or companies figure stuff out, and quantum volumes double or maybe even increase by an order of magnitude (10x) in a short time. That could be a game-changer.
2. Classical computers could hit a wall across a number of hard problems, and stop improving and stealing markets from quantum.
3. Even if classical keeps shrinking the QC ice floe, there are still lots of hard problems left, worth billions and tens of billions of dollars, that quantum looks poised to capture by 2030 or 2040. Whether the 2035 market for QC is $20 billion or $40 billion, that is still a lot of money, and much more than the current QC market which is a couple of hundred million dollars or less per year at present. (It depends a bit on how you count it, plus not everything is publicly announced.)
4. Even a shrinking ice floe might bump into a much larger ice shelf, filled with fat, juicy seals. This is what happened to graphics chips (GPUs) 15 years ago. Yes, companies like Intel were stealing the market for graphics chips on computers…but since then people have started using GPUs for other things, such as more-autonomous cars, cryptocurrency mining, high performance computers (aka supercomputers) and especially machine learning. Although GPUs were not used by DeepMind in CASP14 (AlphaFold runs on its own special processors from Google called the TPU) the data center business for Nvidia, the largest GPU company today, is about $2 billion per quarter, or almost as big as all of Nvidia’s revenues back in 2005.
5. There are various quantum devices out there today, from Google, Honeywell, IBM, IonQ, Rigetti and Canada’s own D-Wave quantum annealer. They are all relatively early devices, and we are still learning what they can and can’t do. Although protein folding may look like a market that classical machines can do better than first thought, there are many markets such as optimization problems, Monte Carlo simulations, quantum processes in chemistry and biology, and so on. QCs may also be really useful for machine learning and AI. When we build a much larger and more stable QC than exists today, it may well solve unexpected problems really well, and much better than classical computers.

[1] This is my attempt to make a cute pun on Hawking’s famous book A Brief History of Time. I suspect it doesn’t work.

[2] The chart shows the average (mean) GDT score of under 90. Other sources say that the AlphaFold2 median score across all targets was 92.4 GDT. I must be honest and admit I don’t know if median is a good way of looking at accuracy…but previous CASP GDT scores have always been the mean, so I am assuming that is the proper measure.

[3] Early jigsaw puzzles were made out of wood, and were made using jig saws…hence the puzzle’s name!

[4] To be fair, it was only the media coverage of the Chinese announcement that used the term “quantum supremacy.” They specifically forbore from using that term in their paper, instead using “quantum computational advantage.” The Chinese approach used something called boson sampling, which is a hard problem for classical computers, but may or may not be useful computationally.