Quantum Computers Get Their Own Native Math Problem — and It's a Control Theory Classic

BQP-completeness for Lyapunov and LQR value problems: the first proof that core control-theory computations are exactly as hard as quantum computing itself.

Imagine you're trying to figure out how much energy a skyscraper's dampening system will absorb over its entire lifetime — not just the next earthquake, but every vibration from now to infinity. For small buildings, you solve a neat matrix equation and you're done. But what if the building has 2^n floors, described by a compact blueprint rather than a full floor plan? That's the problem this paper formalizes, and the answer turns out to be: this IS quantum computing, in a precise complexity-theoretic sense. The committed claim: evaluating infinite-horizon output energies (Lyapunov values) and optimal control costs (LQR values) for succinctly described linear systems is BQP-complete. That means these problems are (a) solvable in polynomial time on a quantum computer and (b) at least as hard as anything a quantum computer can do. No classical randomized algorithm can solve all instances efficiently, unless BPP = BQP — a collapse most theorists consider extremely unlikely. The core technical move is elegant. For BQP-hardness, the authors encode arbitrary quantum circuits into the dynamics of a dissipative linear system, so that the Lyapunov value of a specific initial state recovers the acceptance probability of the circuit. The state dimension is exponential in the circuit description length, but the system matrices are sparse and specified by Boolean circuits — hence 'succinct.' For containment in BQP, they show the more general algebraic Riccati equation (which characterizes LQR) can be solved by a quantum algorithm in time polynomial in the succinct input length, using Hamiltonian simulation techniques. Where does this sit on the ladder? The natural predecessors are Janzing and Wocjan's BQP-completeness results for matrix problems (2007) and the broader program connecting linear algebra to quantum complexity (Harrow-Hassidim-Lloyd's HHL algorithm, 2009). This paper extends that lineage into control theory specifically — Lyapunov and Riccati equations had not been placed in BQP-completeness results before. It is not an incremental improvement on a benchmark; it is a classification result. The comparison isn't 'we beat Method X by 3%' but 'we proved this problem class lives exactly here in the complexity zoo.' Integrity is straightforward for a theory paper: the result is a mathematical proof, not a simulation or experiment. The reduction and the quantum algorithm are both constructive. The validation is internal consistency and correctness of the proof, which will be checked by peer review and the complexity-theory community. There is no cherry-picking risk in the usual empirical sense — but the 'promise problem' formulation (guaranteed gap between YES and NO instances) is doing real load-bearing work, and the practical relevance depends on whether real-world control problems land in the promise gap. The milestone question is subtle. This is a structural result, not a scaling benchmark. It doesn't say 'we solved a 10^6-dimensional Lyapunov equation on a quantum computer.' It says 'when someone builds a fault-tolerant quantum computer, this class of problem will be among its natural applications — and no classical shortcut exists.' The next concrete step is implementing the quantum Riccati solver on near-term hardware for modest system dimensions and measuring whether the theoretical polynomial advantage survives real gate noise. The experiment the authors did not run: an actual quantum circuit implementation, even on a simulator. The paper is pure complexity theory. The honest read is (a) — this is a classification paper, not an implementation paper, and building the circuit would be a separate research program requiring fault-tolerant hardware that doesn't yet exist at the needed scale. But it also means the practical gap between theorem and application remains wide.