Researchers set a lower bound for quantum equation solving

Researchers at Quantinuum K.K., the National University of Singapore, and RIKEN have established a lower bound on the complexity of solving linear systems with quantum computers. Published August 4, 2026, in Quantum Science and Technology, the work defines a concrete limit to quantum speedup for this specific task, moving beyond theoretical possibility to measurable constraints.

The team proved a lower bound of Ω(κ sqrt(s)) for quantum algorithms solving linear systems with constant error, where κ represents the condition number and s denotes the sparsity of the system. This study utilized no new data creation or analysis, representing a purely theoretical advancement in understanding quantum computational limits.

Quantum Linear System Solvers and Query Complexity

Researchers have demonstrated that quantum computers face inherent complexity when solving linear systems of equations, regardless of hardware advancements. The investigation centers on quantum linear system (QLS) solvers, a foundational class of quantum algorithms with applications spanning machine learning and differential equation solving. Performance is measured by quantifying the number of times the algorithm must consult the input data. This finding is particularly significant because it addresses a long-standing question regarding the influence of sparsity on QLS complexity, a topic previously considered unproven due to the lack of formal proof.

Several authors have indicated that a manuscript detailing an earlier, related result has been in preparation since at least 2018, as evidenced by citations in their research papers. This study represents a purely theoretical advancement; no new data were created or analyzed, emphasizing its mathematical nature.

The researchers employed a reduction from a known problem in the bounded-error setting to establish the Ω(κ sqrt(s)) lower bound, applicable when the target error is constant. This contrasts with previous work focused on the Ω(κ log(1/ε)) bound, where ε represents the desired accuracy.

The team states this is not a new result, because a proof strategy was discussed in, highlighting the effort to solidify existing concepts with a rigorous proof. The study defines a quantum state |x⟩ as an approximation of the normalized state |x⟩ =, where An is an invertible matrix and |b⟩ is a quantum state, and the goal is to solve the linear system of equations Ax = b. The relevance of parameters like the condition number κ and sparsity s are central to understanding the complexity of QLS.

Researchers utilize the ℓ^2 -norm, denoted as |x| = sqrt(x· x), and spectral norm |A| = max_( |x| ≠ 0)|Ax|/|x| to analyze the matrix A. The team’s work is a crucial step towards the complete characterization of QLS complexity, and a joint lower bound encompassing all three parameters, κ, s, and ε, remains an open challenge.

Harrow and Kothari’s Unpublished Ω(κ log(1/ε)) Lower Bound

The pursuit of quantum advantage in solving linear systems has yielded algorithms demonstrating significant theoretical speedups, but a complete understanding of the fundamental limits remains elusive. Quantum linear system (QLS) solvers represent a cornerstone of many potential quantum applications, from materials science to machine learning, and their performance is typically assessed by query complexity, the number of times an input must be accessed. For years, the best-known query complexity for these algorithms stood at O(κ log(1/ε)), where κ represents the condition number of the linear system and ε is the desired accuracy.

Establishing a corresponding lower bound, a concrete limit on how slow any quantum algorithm must be, has proven surprisingly difficult. This work does not introduce new data creation or analysis; instead, it provides a rigorous mathematical proof of limitations, confirming a lower bound of Ω(κ log(1/ε)).

This confirmation is notable because the original proof of this bound is attributed to Harrow and Kothari, but has remained unpublished for nearly a decade. The team’s analysis extends beyond simply restating the known bound, also tackling the more complex question of how the “sparsity” of the linear system, the number of zero entries in the matrix, affects the computational cost.

While previous work suggested a lower bound of Ω( κ sqrt(s) log(1/ε)), where s denotes sparsity, this remained largely unproven. This detailed approach, the researchers argue, is crucial for a complete characterization of QLS complexity.

Researchers are currently refining the understanding of how the “sparsity” of a linear system impacts the complexity of solving it using quantum computers. This result clarifies that the complexity isn’t a fixed value, but rather dynamically adjusts based on the structure of the input data. The researchers emphasize that this is not simply a restatement of existing knowledge; their analysis extends beyond previously known bounds. A notable aspect of this study is its purely theoretical nature, with no new data created or analyzed.

Ω(κ sqrt(s)) Lower Bound Proof via Error Reduction

This finding defines a fundamental constraint, moving beyond simply showing quantum algorithms can be faster to specifying how much complexity remains inherent in the problem. The team’s approach centers on a “reduction of the bounded-error problem,” a technique used to establish lower bounds by transforming the problem into another well-understood computational challenge. This allows for a rigorous demonstration of the Ω(κ sqrt(s)) limit, particularly when dealing with constant error levels.

The significance of this result lies in its consideration of sparsity, as previous lower bounds, such as the Ω(κ log(1/ε)) bound attributed to Harrow and Kothari (though their proof remains unpublished), often overlooked the impact of a sparse matrix. The new analysis demonstrates that the complexity isn’t solely determined by the condition number and desired accuracy, but also scales with the square root of the matrix’s sparsity.

This is crucial because many real-world linear systems are inherently sparse, arising in fields like structural engineering and network analysis. The team acknowledges that while a formal proof of the Ω(κ log(1/ε)) lower bound was previously discussed in unpublished work, their analysis extends the understanding of QLS complexity.

The team believes their current result is an important step towards understanding the role of sparsity in the query complexity of the QLS problem, and they are now focused on extending this work to establish a comprehensive lower bound encompassing all three key parameters: condition number, sparsity, and error tolerance.

The assumption that quantum computers will effortlessly outperform classical algorithms on all fronts is increasingly nuanced. While theoretical speedups have been demonstrated for specific problems, establishing concrete limits to quantum computation is proving crucial.

This research centers on the query complexity of the quantum linear system (QLS) problem, which involves approximating the solution to an equation of the form Ax = b. Performance isn’t simply about the size of the system (N), but also the condition number (κ), a measure of how sensitive the solution is to changes in the input data, and the sparsity (s), representing the number of zero entries within the matrix A.

A higher condition number indicates a more challenging system to solve, demanding greater computational resources. The team’s approach begins by defining how a quantum algorithm accesses the input matrix, and no new data were created or analyzed in this study. Crucially, the researchers revisited a previously established lower bound of Ω(κ log(1/ε)), acknowledging that while known, a detailed proof was lacking.

They achieved this proof within the setting, meaning the algorithm isn’t required to guarantee a specific error rate, simplifying the mathematical analysis. This allowed them to focus on establishing the fundamental relationship between the condition number, desired precision, and computational cost, and this result serves as a crucial stepping stone, not an endpoint.