Use Cases for Near-Term Quantum Computers

What is the ‘killer app’ for noisy quantum computers in the near term?

With Google offering a $5m prize over the next three years to find the best use for near-term quantum computers, we ought to ask: What is the most promising application of NISQ devices?

Algorithmic Speed-Ups

Quantum Algorithm Zoo contains as of September 2024 around 70 quantum algorithms with their theoretical speed-ups. This is not an exhaustive list, but it is a good enough start. Python is perfect for extracting the salient data from the HTML, which I have done in a Zoose Codespace notebook.

Across all categories, we see the following distribution:

The most common speed-ups are: superpolynomial (46%) and polynomial (42%), which also includes quartic (1%). I have separated quartic from regular polynomial speed-ups for reasons that will become clear in a moment. Exponential speed-ups are pretty rare though (3%).

Quantum Advantage

Achieving quantum advantage is unfortunately not a matter of having an algorithm that is a bit faster than on a classical computer due to both noise, for which quantum error correction is necessary, and the I/O bottleneck.

In fact,

“[q]uadratic speed-ups […] are insufficient for practical quantum advantage.” Hoefler et al. (2023)

However,

a quartic speed-up […] is often sufficient to restore the viability of achieving quantum advantage. Babbush et al. (2021)

Hence, exponential, superpolynomial, and quartic or better polynomial speed-ups are sufficient for quantum advantage on NISQ machines. That covers only half of all algorithms on Quantum Algorithm Zoo, because most polynomial speed-ups are worse than quartic.

Well-known algorithms with exponential speed-ups are Shor’s algorithm for prime factorization, the quantum Fourier transform (QFT), which forms the core of Shor’s algorithm, and the Harrow–Hassidim–Lloyd (HHL) algorithm for solving sparse linear systems. Simulations of quantum mechanical systems in physics and chemistry also fall in this group.

Polynomial speed-ups are known for tensor PCA (quartic), Grover’s algorithm, and quadratic unconstrained binary optimization (QUBO).

Algorithms such as quantum annealing, QAOA (quantum approximate optimization algorithm), VQE (variational quantum eigensolver) algorithms for solving ODEs and PDEs in computational fluid dynamics (CFD), or quantum machine learning (QML) have unknown speed-ups. These may or may not be sufficient for quantum advantage, but no proofs exist except in specific cases. For instance, k-nearest neighbour, which is powered by Grover’s algorithm, only sports a quadratic speed-up.

In QML, especially quantum convolutional networks, recent research promises:

“You only need as many data points as the number of parameters in your model” Caro et al. (2022)

This can obviously reduce the amount of data needed significantly. Although with millions or billions of parameters in a model, you tend to bump into the I/O bottleneck sooner rather than later. That also goes for solving large linear systems with HHL or searching large unsorted databases with Grover’s algorithm.

In the category of QML, optimization, and numerics, only 38% of algorithms have a possible quantum advantage. Many of these have severe limitations, such as only for certain types of problems, so that any quantum advantage in the near term remains doubtful.

NISQ Use Cases

What are the best use cases for near-scale intermediate quantum computers? Richard Feynman’s idea that sparked the R&D into quantum computing: the simulation of quantum physical processes in chemistry or materials science. Optimization and quantum machine learning are popular, though quantum advantage is not at all guaranteed.

Quantum cryptography is often cited as a key application, though with the current prime factorization record standing at 21 = 7·3, we are still far away from cracking asymmetric cryptography schemes, such as RSA.

Symmetric cryptography algorithms are safe from Shor’s algorithm, but they might fear a brute-force attack with the aid of Grover’s, which can crack n-bit keys in 2^n/2 steps. Still, that requires 2⁶⁴ steps for AES-128, or 585 years at 1 GHz, which is unrealistic as 1 GHz is ten times faster than the current fastest quantum gates. What is more, we cannot evaluate one iteration of Grover’s algorithm in a single cycle, as that requires a few hundred noiseless quantum gates per iteration.

That said, companies are wise to learn more about post-quantum cryptography (PQC) to ensure their data remains safe from future attacks on quantum computers.

While quantum networks are already being built, they are not going to be relevant in the near term. What is more, such networks are for quantum key distribution (QKD) for secure communications.