Succinct Infinite-Horizon Lyapunov and LQR Value Problems Are BQP-Complete

In the world of engineering and physics, there is a constant need to predict how systems behave over time. Whether designing a stable bridge, guiding a spacecraft, or regulating an electrical grid, engineers rely on mathematical models to calculate the total energy a system will use or the cost of keeping it on course. For simple systems, these calculations are straightforward. However, when the systems become massive—composed of millions of interacting parts—the math becomes so dense that even the most powerful supercomputers struggle to find the answer in a reasonable amount of time. This is where the boundary between what computers can do and what they cannot begins to blur. Scientists have long suspected that quantum computers, which operate on the strange rules of subatomic particles, could solve these specific types of massive calculation problems far faster than any classical machine. But for this belief to be more than just a hope, it needed proof that these problems are inherently difficult for classical computers, not just that quantum ones happen to be fast.

A team of researchers at the University of Waterloo has now provided that proof, settling a long-standing question about the limits of computation in control theory. They focused on two specific tasks: calculating the total energy output of a stable system and determining the best possible cost to control a system over an infinite future. In the real world, these are the numbers engineers need to know to ensure a system is efficient and safe. The researchers took these problems and made them as hard as possible to describe by using a "succinct" representation. Instead of listing every single number in a massive matrix—which would take up terabytes of memory—they used a compact set of logical instructions, similar to a computer program, that could generate the numbers on demand. This allowed them to describe systems with dimensions so large that writing them out explicitly would be impossible, yet the description itself remained small enough to fit on a single page.

The team then asked a fundamental question: Can a standard computer, even one that uses random chance to speed things up, solve these succinctly described problems quickly? Their answer was a definitive no. They proved that solving these specific energy and control problems is as hard as simulating any possible quantum computer. In the language of computer science, they showed that these problems are "BQP-complete." This means that if a classical computer could solve these control problems efficiently, it would also be able to solve every problem that a quantum computer can solve. Since most experts believe that classical computers cannot do this, the researchers concluded that no classical algorithm, no matter how clever or randomized, can solve these specific control problems in a time that scales reasonably with the size of the input.

To reach this conclusion, the researchers did not just guess; they built a mathematical bridge. They demonstrated that any calculation a quantum computer performs can be translated directly into one of these control problems. If you wanted to know the result of a complex quantum experiment, you could encode that experiment into the description of a system's energy or control cost. If a classical computer could quickly tell you the answer to that energy question, it would effectively be running the quantum experiment for you. Because the researchers showed this translation works for every possible quantum task, they proved that the difficulty of the control problem is exactly the same as the difficulty of quantum computation itself.

The study also showed that quantum computers can actually solve these problems efficiently. By using specific quantum algorithms designed to handle these types of matrix calculations, a quantum machine can find the answer in a time that grows slowly as the system gets larger. This creates a clear divide: the problem is easy for a quantum computer but provably hard for a classical one, assuming the widely held belief that quantum and classical computing power are fundamentally different. The researchers did not just find a faster way to do the math; they identified a specific class of engineering questions that serve as a litmus test for the power of quantum mechanics.

This work matters because it moves the conversation from speculation to certainty. For years, the promise of quantum computing in engineering was based on the idea that quantum machines would simply be faster at linear algebra. This paper confirms that for certain critical questions about system stability and control, the advantage is not just a matter of speed, but of capability. It establishes that there are real-world engineering questions that are fundamentally out of reach for classical computers, no matter how much time or memory they are given. The researchers did not claim to have built a quantum controller for a jet engine or a power grid, but they have proven that the mathematical foundation for such a controller belongs to a realm where only quantum computers can tread.

The findings also clarify the nature of the difficulty. The problems are not hard because the numbers are messy or the systems are chaotic. They are hard because the way the information is packed into the description hides a complexity that classical computers cannot peel back without simulating the entire quantum process. The researchers showed that even when the systems are strictly stable and well-behaved, the sheer scale of the hidden information creates a barrier. This barrier is not a temporary lack of better algorithms; it is a structural limit of classical computation.

In the end, the paper draws a sharp line in the sand. It tells us that for a specific, important class of infinite-horizon control problems, the future of efficient calculation lies exclusively with quantum technology. If engineers ever need to optimize systems of such immense scale that they can only be described by compact logical rules, they will have to rely on quantum machines. The classical approach, even with all its probabilistic tricks, will simply hit a wall. This result does not just add a new entry to a list of quantum advantages; it defines a new category of problems where the quantum world is not just an option, but the only path forward.