[Blog] On the realisability of quantum advantage

By Farhang Hadad Farshi, Quantum Technology Expert at Da Vinci Labs.

Quantum computers are believed to be capable of performing efficiently certain computational tasks that are considered to be intractable for classical computing machines. This advantage is rooted in the quantum computer’s capacity to leverage interference - the most fundamental hallmark of quantum behavior.

To be more precise, the algorithms designed for quantum computers orchestrate intricate patterns of interference enabling them to solve certain problems in a significantly shorter period of time. This means that for a quantum computer, the solution time grows at a significantly slower rate than that of a classical computer, as the size of the problem increases.

A vast collection of computationally hard problems have been proposed to benefit from such asymptotic quantum speedup ranging from cryptanalysis, chemistry, and materials science, to optimization and machine learning. While asymptotic speedup is essential, it alone cannot ensure practical quantum advantage.

It is of central importance to also consider the fundamental limitations that bound the performance of a realistic quantum computer in order to assess whether a tangible benefit over classical computers can be achieved. This gives rise to a key question: which class of the proposed applications are likely to pan out?

A recent study [1] has provided a comprehensive answer to this question by considering some of the fundamental limitations linked with the near-future quantum computers such as the number of gate operations per unit time that determines the upper bound on the input/output bandwidths.

Having an optimistic outlook for quantum computers, they find that the applications that are more likely to yield a practical quantum advantage are those that allow exponential speedup such as quantum simulation applied in chemistry and material science, as well as cryptanalysis based on Shor's algorithm.

More importantly they conclude that a large range of problems with quadratic speedups such as many current machine learning approaches, or solving systems of nonlinear equations that model turbulence, are unlikely to yield practical quantum advantage unless significant algorithmic improvements are made.

As a considerable number of scientific and industrial applications, including the modeling of turbulent aerodynamics and space mission optimization, fall under the category of problems with non-exponential (quadratic) speedup, it is crucial to explore the possibilities for significantly upgrading the algorithms for such applications.

EQUALITY is precisely designed to explore such possibilities of developing cutting-edge algorithms for solving practical industrial problems using realistic quantum computing machines. 

[1] T. Hoefler, T. Häner, M. Troyer, Communications of the ACM, 66, 5, pp 82-87, 2023. DOI: 10.1145/3571725.