“The Quantum Tortoise and the Classical Hare: A simple framework for understanding which problems quantum computing will accelerate (and which it will not)” is co-authored by Neil Thompson, research scientist at MIT Sloan and the MIT Computer Science and Artificial Intelligence Laboratory (CSAIL), Sukwoong Choi, assistant professor at University at Albany and digital fellow at MIT Initiative on the Digital Economy, and William S. Moses (MIT CSAIL PhD ’23), incoming assistant professor at University of Illinois Urbana-Champaign. This work is part of a larger collaboration between Accenture and the MIT Initiative on the Digital Economy, and is funded by Accenture.
“Many business leaders are looking to quantum computing as the promising successor to classical computing, but research shows–and leaders in quantum computing agree–it will continue to underperform classical computing in many areas,” says Thompson. “As a result, to understand where quantum computing will perform better first requires understanding why it can be.”
Thank you for reading this post, don’t forget to subscribe!
The research paper finds that quantum computers must meet two conditions to yield an improvement on classical computers. First, they must be powerful enough to solve the problem at hand, which is a challenge because most quantum computers are currently so small they can only run toy problems, such as factoring numbers so small that using a classical computer makes more sense). Second, it must gain enough of an advantage from having a better algorithm that it can run a problem in less time than it would take a classical computer.
While these factors sound straightforward, they have powerful implications regarding which problems will benefit from quantum computing and which won’t. Better yet, they can often be calculated before investing in a project.
“Companies often consistently face fixed sets of problems, and decision-makers might wonder if these problems could be solved more quickly and efficiently with quantum computing,” Thompson says. “Our framework provides a way to analyze the potential impact of switching to quantum computing before making the investment.”
Thompson notes this research can be used across industries—such as automotive, chemistry, and finance—where companies have started to examine applications of quantum computing. In particular, the framework considers how well a quantum computer might solve a problem using Shor’s algorithm, which is one of a few well-known quantum algorithms, compared with how well a classical computer might solve a problem. The analysis reveals that many problems, particularly those of small to moderate size, will most likely not benefit from quantum computing in the near-term.
The reason that quantum computers will often be slower than classical ones (and therefore be the “tortoise” in this paper) is that the hardware itself runs slower, doing fewer operations per second.
“You might think this would doom them to always be slower, but sometimes they have more efficient ways of solving problems that are unavailable to classical computers,” says Thompson These quantum algorithms, if they provide enough of an advantage, can allow quantum computers to outpace their classical brethren. Unfortunately, even if quantum computers could theoretically be better, they often aren’t in practice because current and near-term quantum computers have limited computational capacity, so they aren’t powerful enough to run the problems where quantum computers are better.
The framework has an economic dimension, which the authors term “quantum economic advantage.” This represents the crossover point, when businesses would start wanting to use quantum computing because it represents the lowest-cost way of achieving a particular level of performance.
Recommended AI News: MLCommons Consortium Chooses Cognata’s Synthetic Dataset to Set Industry Benchmarks
This study gives managers and their teams the tools for understanding when quantum economic advantage is achieved, which requires evaluating the two key criteria:
- Feasibility: Can the quantum computer, given its speed and size, effectively handle the problem at hand?
- Algorithm Advantage: If the quantum computer is capable, would it actually process the task faster than a classical computer of comparable cost?
“We need to consider the speed of the computer versus the route,” Thompson said. “Thinking of it like a race, in getting from point A to point B, the algorithm is the route. If the race is short, it may not be worth investing in better route planning. For it to be worth it, it has to be a longer race.”
A consequence of these conditions is that larger problems show the most benefit from quantum computing. For example, computers might be used to look for a particular DNA sequence in a human genome. While the best classical algorithm for this problem is less powerful than the best quantum algorithm, classical computers are much faster and can run more applications at the same time. As problem sizes get larger, the “algorithmic benefit” of quantum computing becomes more important. In particular, the length of a typical human genome (~3 billion DNA “letters”) is not big enough for quantum to be better, so it shouldn’t be used for this purpose. By contrast, large databases of genomes (with more than 1 trillion letters) could be large enough where quantum is a better option.
“Ultimately, this research suggests that quantum computing will be the more attractive option under one of two conditions for businesses,” Thompson said. “First, that the quantum algorithm is exponentially faster than the classical algorithm, or second, that the quantum algorithm is significantly better and the problem size is quite large.”
Building on this analysis, Thompson says future research will delve into which specific problems and industries will benefit most from quantum—and which won’t.