When Measuring a Stable System Can Be as Hard as Quantum Computing

Two familiar questions, an unusual scale

The first problem concerns an autonomous linear system: its initial state is specified, and its subsequent motion follows a fixed matrix. An output measures part of that state. The quantity of interest is the output’s squared magnitude, accumulated over all future time. For sufficiently stable dynamics, this infinite-horizon energy is finite and can be characterized through a Lyapunov equation.

The second problem adds control inputs. A linear-quadratic regulator, or LQR, balances two penalties: the size of the measured output and the effort spent controlling it. Its optimal total cost is characterized by an algebraic Riccati equation.

These are established mathematical tools. The unusual feature of this study is how the systems are supplied. Rather than listing their matrices, the input contains small Boolean circuits that report the locations and values of nonzero entries in requested rows or columns. Such descriptions can represent matrices whose dimensions are exponentially larger than the descriptions themselves.

That distinction determines what “efficient” means. The authors measure runtime against the compact description’s length, not the number of entries in an explicitly written matrix. They also request a single scalar decision, not an entire matrix solution.

What BQP-complete means here

The paper defines the Succinct Lyapunov Value problem, SLV, and the Succinct LQR Value problem, SLQRV. Each asks whether a value lies below a lower threshold or above a higher one. Inputs are promised not to fall between them.

BQP is the class of decision problems that quantum computers can solve in polynomial time with bounded error. Calling a problem BQP-complete establishes two things: an efficient quantum algorithm can solve it, and every problem in BQP can be efficiently translated into it.

The authors prove completeness for SLV with their fixed sparsity and encoding parameters set to five, and for SLQRV with a sufficiently large fixed parameter governing its promises. These are carefully bounded problem classes, not unrestricted claims about every Lyapunov or Riccati calculation.

How a control system encodes a quantum computation

For the hardness proof, the researchers start with an arbitrary bounded-error quantum computation. They convert it into a real circuit with rational gate entries, preserving enough separation between its accepting and rejecting cases.

They then arrange the gates along a one-way mathematical “clock.” Each clock position represents a computation stage; sparse connections carry the state forward through the appropriate gate. Damping makes the resulting continuous-time system strictly dissipative: its state norm decays rather than grows.

The construction is calibrated so that the total energy measured at a selected terminal coordinate equals the square of the circuit’s acceptance probability. After the circuit conversion, rejecting cases have acceptance probability at most 2/5 and accepting cases at least 3/5. Their energies therefore lie at or below 4/25, or at or above 9/25.

This gives a concrete translation from quantum decision-making to energy evaluation. Remarkably, every eigenvalue of the constructed dynamics matrix is the same negative number. The computation resides in the feed-forward coupling structure, showing why eigenvalues alone do not describe the difficulty of this evaluation task.

Why the quantum algorithm qualifies

For the other half of completeness, the paper builds on an existing quantum approach to Riccati equations. It uses block encodings—ways of representing matrices within larger quantum operations—and a spectral projector that selects the stable part of an associated Hamiltonian matrix.

From that projector, the algorithm obtains a quantum representation of the Riccati solution and estimates the scalar cost for the specified initial coordinate. It does not print the full solution matrix.

A central technical step is deriving bounds that keep these operations efficient under the stated assumptions. Those promises constrain matrix sizes in norm, numerical precision, the decision gap, and quantitative stabilizability and detectability. Stabilizing gains need only exist within the bounds; they are not supplied as inputs. The uncontrolled energy problem embeds into this controlled problem by setting the control matrix to zero.

What the result does not establish

The classical limitation is conditional. Unless BPP, the bounded-error randomized classical class, equals BQP, no classical randomized algorithm can match the polynomial-time guarantee on every promised instance. The paper does not prove those classes differ, establish a particular exponential speedup, or report a hardware demonstration.

Restricted systems can remain classically tractable. The authors show an easy regime for SLV with a uniformly positive dissipation margin and constant decision gap. Their hard construction instead has a margin that shrinks with system size.

The source is the full text of version 1 of the arXiv preprint, posted November 9, 2026. Its contribution is a mathematical complexity classification, presented in preprint form—not an experimentally validated engineering advantage.