Study Maps 24 Problems Where Quantum Computers Could Gain an Edge

Insider Brief

• Researchers identified 24 computational problems with potential for substantial quantum speedups and outlined the conditions needed to achieve them.
• The study covers areas including chemistry, optimization and data analysis, connecting theoretical quantum methods with possible practical applications.
• Preparing data, correcting errors and reading results can erase potential gains, requiring researchers to assess the full calculation against leading classical methods.

Quantum computers could deliver substantial speedups on 24 computational problems, but a new study also reveals the challenging conditions that would make those gains useful.

Researchers affiliated with the Open Quantum Institute, hosted at CERN, Google Quantum AI, Microsoft, Oratomic, NVIDIA, JPMorganChase, MIT, Harvard University and other institutions have assembled a guide to problems with credible prospects for quantum advantage — or, the ability for quantum machines to outperform classical computing methods.

For each problem, the researchers describe the mathematical structure, data requirements and other conditions needed to preserve a quantum computer’s potential edge. The aim is to help scientists and industry specialists identify where theoretical gains could translate into practical applications.

The paper, which was posted to the preprint server arXiv, is a synthesis of existing research. It cautions that a theoretical speed advantage does not guarantee faster results in practice. A quantum algorithm may require far fewer steps than a classical method on large problems, yet still take longer to produce a useful answer. Preparing data, correcting errors and reading the results can erase the expected time savings, the researchers write.

The collection spans number theory, optimization, statistical inference, quantum simulation, linear algebra and the analysis of shapes and connections in data. Potential applications include chemistry, materials research, signal processing and code breaking, although the evidence and maturity vary substantially across entries.

A Higher Bar for Advantage

The researchers focus on speedups greater than quadratic, a threshold they argue will likely be needed to overcome the substantial operating costs of early quantum computers equipped with error correction.

A quadratic speedup means that if a classical computer needs roughly 1 million steps, a quantum algorithm might need about 1,000. That does not necessarily mean it finishes 1,000 times faster, because each quantum step can take more time and resources

The compendium instead includes stronger improvements, ranging from cubic and quartic gains to exponential separations. These describe how the work required grows as problems get larger, rather than how many times faster a quantum computer would be on every calculation.

The comparisons are generally against the best classical methods currently known. The team stresses that those methods can improve and an advantage over today’s leading classical algorithm does not necessarily prove that no better classical approach exists.

The study also distinguishes several kinds of evidence, including rigorous mathematical results, evidence limited to particular classes of classical methods, and numerical or heuristic studies. Its maximum-speedup labels describe the strongest result identified under specified conditions, rather than a promise for every instance of a problem.

The researchers favor starting with computational tasks for which quantum advantages are already supported, then looking for real problems that fit their requirements. Starting with a pressing business or scientific challenge and searching for a quantum solution is often unsuccessful because useful quantum algorithms depend on mathematical structures that many problems lack.

Where the Conditions Matter

Solving systems of linear equations — sets of equations that describe relationships among quantities, such as currents in an electrical circuit — shows how large potential quantum speed gains can depend on strict conditions.

These equations appear throughout science and engineering, such as calculating forces on bridges, analyzing currents in electrical circuits and modeling heat flowing through materials. The study indicates that quantum algorithms can offer exponential improvements in some settings, but the numbers that define the equations must be organized in ways that a quantum computer can load quickly. The equations must also be solvable without numerical difficulties that slow the calculation.

The output is another constraint. A quantum computer also stores the answer in a form that must be measured to obtain usable numbers. For example, an engineer modeling heat flow might need a broad measure of how heat spreads, rather than the temperature at every point in a material. Quantum methods are better suited to extracting a few such measures; retrieving every temperature value could erase the time savings, according to the study.

The researchers detailed a similar problem with loading arbitrary data. If preparing the input requires work proportional to the dataset’s size, an apparent exponential improvement in the central calculation may disappear, according to the paper.

In chemistry, the study examines how quantum computers could calculate a molecule’s lowest possible energy, known as its ground-state energy. This helps researchers determine how its atoms arrange themselves and how it might react with other molecules — information useful for developing battery materials or substances that capture carbon dioxide.

The study suggests three criteria for producing practical quantum advantage. First, the system must fit within available computing resources. Researchers must also be able to prepare a suitable initial quantum state. Finally, the chosen problem must resist efficient classical methods, the researchers write.

The study identifies preparing those initial states and establishing which scientifically relevant systems are consistently difficult for classical computers as important unresolved challenges. It places the ground-state energy result it reviews in its earlier research category, while noting that more advanced work on the same broader problem may exist outside the entry’s scope.

Another example involves finding patterns buried in noisy data, such as measurements with random errors. The study describes a quantum method that could sharply reduce the work needed to uncover certain patterns as datasets grow larger, though the advantage depends on specific conditions.

That improvement applies within a particular range of signal strength and problem structure. It does not extend to ordinary matrix principal component analysis, which already has efficient classical methods. Showing that similar gains survive in messier datasets, including sparse or contaminated data, remains a research task, according to the study.

Even a candidate with evidence of favorable scaling may require formidable hardware. For a specific random constraint-satisfaction problem, the paper cites an analysis placing the quantum-classical crossover at approximately 15 hours using roughly 74 million physical qubits, under the assumed error rate and error-correction design. The estimate illustrates the distance that can separate a mathematical advantage from an affordable computation.

From Candidate Problems to Useful Work

The researchers group the 24 computational problems identified in the study into two stages based on how much is known about their potential quantum advantage.

Stage I includes tasks where research suggests quantum computers could have an edge, but scientists still need to identify specific examples where that advantage would hold. Stage II goes further, identifying examples they can readily construct that quantum computers are expected to solve faster than the best available classical methods and machines.

The next step is showing that those examples address a useful scientific or technological question. Simulating a molecule faster, for instance, matters only if the result helps researchers understand its behavior or develop a new material, according to the study.

Each of the 24 entries explains the problem, where it might be useful, how quantum and classical methods compare, and what conditions are needed for a quantum advantage. The guide is aimed at scientists and other specialists who understand computing but may not know how to apply quantum methods to their work.

Researchers must also be able to check whether an answer is reliable. Depending on the problem, that could involve checking it with a classical computer, running another quantum calculation or comparing the result with a physical experiment.

Much of the remaining work involves making the full calculation more efficient, from preparing the information a quantum computer needs to reading its answer. Researchers must also test whether the methods work on a wider range of problems and retain their advantage as classical computing methods improve.

The guide’s 24 entries give researchers a starting point: problems where quantum computers could offer substantial gains, the conditions those gains depend on and the questions that remain before they can be put to practical use.

The research team included Philipp Kammerlander of the Open Quantum Institute; Thomas E. O’Brien, Robbie King, Rolando D. Somma, Mária Kieferová, Alexander Schmidhuber, Siddhartha Jain, Andi Gu, Guang Hao Low, Dar Gilboa and Ryan Babbush of Google Quantum AI; Brad Lackey and Matthias Troyer of Microsoft; Yuri Alexeev and Elica Kyoseva of NVIDIA; Shouvanik Chakrabarti and Ruslan Shaydulin of JPMorganChase; Pietro M. Posta and Matthias Christandl of the University of Copenhagen; Barry C. Sanders of the University of Calgary; and Catherine Lefebvre of the Geneva Science and Diplomacy Anticipator.

For a deeper, more technical dive, please review the paper on arXiv. It’s important to note that arXiv is a pre-print server, which allows researchers to receive quick feedback on their work. However, it is not — nor is this article, itself — official peer-review publications. Peer-review is an important step in the scientific process to verify results.