⚛️ quantum physics

Quantum query complexity of Hurwitz stability testing

This paper establishes the quantum query complexity of Hurwitz stability testing, proving a lower bound of $\Omega(\sqrt{n}/\nu)$ and presenting quantum algorithms with nearly optimal upper bounds of $\Theta(\sqrt{n}/\nu)$ for normal matrices and $O(\sqrt{n}\nu^{-2}\log(\sqrt{n}/\nu))$ for general matrices, thereby characterizing the problem's dependence on system dimension and spectral gap.

Original authors: Maxwell Fitzsimmons, Mohamed Serry, Meenu Kumari, Jun Liu

Published 2026-11-02

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Maxwell Fitzsimmons, Mohamed Serry, Meenu Kumari, Jun Liu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the world of engineering and physics, many systems are described by how they change over time. A bridge swaying in the wind, a chemical reaction in a vat, or the flow of electricity in a circuit can all be modeled as a collection of variables that shift from one moment to the next. For these systems to be useful and safe, they must be stable. This means that if you nudge the system slightly away from its resting state, it should naturally settle back down rather than spiraling out of control. In the language of mathematics, this settling behavior depends on the hidden numbers, called eigenvalues, that define the system's internal structure. If these numbers all lie in a specific region of the mathematical landscape, the system is guaranteed to calm down; if even one lies in the wrong region, the system will eventually fail. Checking whether a system has this stability is a fundamental task for engineers, but as systems grow larger and more complex, the calculations required to check them become incredibly difficult for classical computers.

Researchers have recently turned to quantum computers to see if they can solve this problem faster. A new study by a team at the University of Waterloo and the National Research Council of Canada investigates exactly how many steps a quantum computer needs to take to decide if a complex system is stable. The team focused on a specific type of stability known as Hurwitz stability, which applies to continuous systems like the ones mentioned above. They worked within a framework where the computer does not see the entire system at once but instead queries a digital representation of it, asking specific questions about its properties. The researchers discovered that the difficulty of the task depends heavily on two things: the size of the system and a measure of how close the system is to becoming unstable. If a system is very close to the edge of instability, it is much harder to verify its safety, even for a quantum machine.

The team proved that for a system with a certain size, there is a fundamental limit to how fast a quantum computer can check for stability. They showed that the number of queries required grows with the square root of the system's size and inversely with the distance to instability. This lower bound holds true even for the simplest kinds of systems, meaning no clever trick can bypass this limit. However, the researchers also developed a method to achieve this speed for a specific class of systems where the internal components behave in a regular, predictable way. For these systems, their algorithm matches the theoretical limit almost perfectly, requiring only a logarithmic increase in effort as the system grows. This suggests that for many well-behaved physical models, quantum computers can indeed verify stability with near-optimal efficiency.

The situation becomes more complicated for systems that are less regular, where the internal parts interact in messy, unpredictable ways. In these general cases, the researchers found that their best algorithm requires significantly more steps than the theoretical minimum. Specifically, the number of steps needed grows with the inverse square of the distance to instability, whereas the theoretical limit only requires the inverse. This gap indicates that while quantum computers are powerful, they still face a hurdle when dealing with the most chaotic and complex systems. The study does not claim to have solved this harder case, but rather isolates the specific difficulty, leaving it as an open question for future research. The work clarifies that the advantage of quantum computing in this field is not a magic bullet that solves everything instantly, but a precise tool whose speed is tightly bound by the mathematical nature of the problem itself.

To understand the mechanics of their discovery, one must look at how the researchers approached the problem. Instead of trying to calculate every single hidden number of the system, which would be slow and prone to error, they devised a way to test a specific property directly. They constructed a quantum process that acts like a filter, designed to detect if any part of the system is behaving dangerously. If the system is safe, this filter produces no signal; if it is unsafe, the filter lights up. The challenge was to build this filter using only the limited information available from the quantum queries. The team showed that by using a mathematical technique to approximate this filter, they could determine the system's fate with high confidence. The efficiency of this process depended on how "sharp" the filter needed to be. For systems that are far from the edge of instability, a coarse filter works fine. But for systems teetering on the brink, the filter must be incredibly precise, which demands more queries and more time.

The study also highlights a crucial distinction between different types of systems. For systems where the internal components are independent or aligned in a simple way, the researchers' method is nearly perfect, matching the best possible speed allowed by the laws of quantum mechanics. However, for systems where the components are tangled and dependent on each other in complex ways, the method requires extra effort. The researchers demonstrated that this extra effort is not just a flaw in their specific algorithm but is tied to the inherent difficulty of representing these complex systems. They showed that the mathematical object used to represent the "danger" in the system can become very large and unwieldy when the system is non-regular, forcing the computer to work harder to process it. This finding isolates a specific gap in our current understanding: we know how fast we could go, but we do not yet know how to build an algorithm that reaches that speed for the most difficult cases.

The implications of this work extend beyond just a single mathematical puzzle. Stability testing is a cornerstone of control theory, used to design everything from autopilot systems to power grids. As these systems become more integrated and complex, the ability to verify their safety quickly becomes critical. The researchers' results provide a clear map of what is possible with quantum technology today. They show that for a wide range of practical applications, quantum computers can offer a significant speedup, reducing the number of computational steps needed to verify safety compared to classical approaches in certain theoretical scenarios. However, they also provide a realistic warning that for the most chaotic and unpredictable systems, the quantum advantage is not yet fully realized. The study does not promise a future where all stability problems are solved instantly, but it does offer a rigorous foundation for understanding the limits and potential of quantum computation in engineering.

Ultimately, the paper serves as a guidepost for the future of quantum algorithm design. By proving that the speed of stability testing is fundamentally linked to the system's size and its distance from failure, the researchers have set a benchmark for what future algorithms should aim to achieve. They have shown that for regular systems, the goal is already within reach, while for irregular systems, the path forward requires new mathematical insights to bridge the gap between what is theoretically possible and what is currently achievable. The work stands as a testament to the power of combining deep mathematical theory with practical quantum computing constraints, offering a clear and honest picture of where the technology stands and where it needs to go.

Technical Summary: Quantum Query Complexity of Hurwitz Stability Testing

1. Problem Formulation

The paper addresses the fundamental control theory problem of determining whether a linear dynamical system $\dot{x} = Ax$ is Hurwitz stable. A matrix $A \in \mathbb{C}^{n \times n}$ is Hurwitz stable if and only if all its eigenvalues lie in the open left half-plane, ensuring that every trajectory converges to zero.

The authors study the quantum query complexity of this decision problem under the block-encoding access model. The input is an exact normalized block-encoding of $A$ , denoted $U_A$ . Crucially, the algorithm operates under a "promise" or known lower bound $\nu > 0$ on the imaginary-axis distance:
$\omega_A := \min_{t \in \mathbb{R}} \sigma_{\min}(A - itI)$
where $\sigma_{\min}$ denotes the smallest singular value. The condition $\nu \le \omega_A$ ensures that $A$ has no eigenvalues on the imaginary axis and provides a quantitative margin for stability. The goal is to decide if $A$ is Hurwitz using the minimum number of queries to $U_A$ and its adjoint.

2. Methodological Strategy

The authors decompose the problem into two primary stages:

A. Reduction to Spectral Projector Zero-Testing

The stability condition is reformulated using the matrix sign function. For a matrix $A$ with no imaginary eigenvalues, the matrix sign function $\text{sign}(A)$ is defined via the Jordan decomposition. The authors utilize the spectral projector onto the right-half-plane invariant subspace:
$\text{sign}_+(A) := \frac{I + \text{sign}(A)}{2}$
A key property is that $A$ is Hurwitz if and only if $\text{sign}_+(A) = 0$ . Thus, the problem reduces to determining whether a specific block-encoded idempotent matrix (the projector) is the zero matrix.

B. Zero-Testing Block-Encoded Idempotents

The paper first establishes the query complexity for testing if an unknown idempotent matrix $P$ (where $P^2=P$ ) is zero, given a $(\beta, b, \epsilon_+)$ -block-encoding $U_P$ .

Algorithm: The algorithm employs Amplitude Estimation. It prepares a maximally entangled state, applies the block-encoding, and measures the probability of the ancilla qubits being in the $|0\rangle$ state. This probability is proportional to the squared Frobenius norm of the projected matrix.
Complexity: For a projector with normalization factor $\beta$ and error $\epsilon_+ \le 1/(4\sqrt{n})$ , the algorithm determines if $P=0$ with constant success probability using $\Theta(\beta\sqrt{n})$ queries.

C. Constructing the Projector from $A$

To apply the zero-test to $\text{sign}_+(A)$ , the authors must construct a block-encoding of this projector from the block-encoding of $A$ .

General Case (Non-Normal): They use a Padé approximation implemented via a structured matrix inverse to approximate $\text{sign}_+(A)$ . This construction introduces a normalization factor $\beta$ that depends on the gap $\nu$ .
Normal/Hermitian Case: For normal matrices, the problem simplifies because $\text{sign}_+(A)$ is an orthogonal projector (with norm 1). The construction utilizes standard linear combination of unitaries (LCU) techniques on the Hermitian part of $A$ .

3. Key Results and Complexity Bounds

The paper provides matching upper and lower bounds (up to logarithmic factors) for the query complexity, summarized in Table 1 of the paper.

Lower Bound

The authors prove a fundamental lower bound of $\Omega(\sqrt{n}/\nu)$ .

This bound holds even when $A$ is restricted to be a real diagonal matrix.
The proof utilizes a reduction from a search problem with weak unitary oracles, demonstrating that the $\sqrt{n}$ scaling is necessary due to the dimension, and the $1/\nu$ scaling is necessary due to the spectral gap.

Upper Bounds

The upper bounds depend on the matrix structure:

General Matrices (Non-Normal):
The algorithm achieves a query complexity of:
$O\left( \frac{\sqrt{n}}{\nu^2} \log\left(\frac{\sqrt{n}}{\nu}\right) \right)$
This result stems from the cost of constructing the projector approximation (scaling as $\nu^{-1} \log(\dots)$ ) combined with the zero-testing cost (scaling as $\sqrt{n}$ ).
Normal or Hermitian Matrices:
For matrices where $AA^\dagger = A^\dagger A$ , the complexity improves to:
$O\left( \frac{\sqrt{n}}{\nu} \log n \right)$
This matches the lower bound up to a logarithmic factor $\log n$ . The improvement arises because the spectral projector is an orthogonal projector with norm 1, avoiding the additional $\nu^{-1}$ factor associated with oblique projectors in the general case.

4. Significance and Claims

The paper claims the following contributions and significance:

Near-Optimality for Normal Matrices: The dimension dependence ( $\sqrt{n}$ ) and the gap dependence ( $1/\nu$ ) for normal matrices are shown to be nearly optimal, matching the lower bound up to a logarithmic factor.
Identification of an Open Gap: For general non-normal matrices, a gap remains between the lower bound ( $\Omega(\sqrt{n}/\nu)$ ) and the upper bound ( $O(\sqrt{n}/\nu^2 \dots)$ ). The paper identifies the factor of $1/\nu$ in the upper bound as an "open conditioning gap." It is currently unknown whether this dependence is necessary or an artifact of the current construction methods.
Uniformity: Unlike previous eigenvalue estimation approaches that rely on state preparation overlap or specific Jordan block structures, these bounds are uniform across the class of matrices satisfying the $\nu$ -gap promise.
Robustness: The results hold for arbitrary matrices, including non-diagonalizable ones, provided the imaginary-axis distance is bounded away from zero.

The authors explicitly state that the matrix-sign construction used (Padé approximation) is not novel in itself, but the integration of this construction with amplitude estimation to derive these specific query bounds is the primary contribution. They do not claim to have resolved the conditioning gap for non-normal matrices, leaving it as a direction for future work.