⚛️ quantum physics

Sparsity-dependent Complexity Lower Bound of Quantum Linear System Solvers

This paper rigorously establishes a sparsity-dependent query complexity lower bound of $\Omega(\kappa\sqrt{s})$ for quantum linear system solvers with constant error, providing a crucial step toward fully characterizing the complexity of these algorithms.

Original authors: Hitomi Mori, Yuta Kikuchi, Marcello Benedetti, Matthias Rosenkranz

Published 2026-01-26

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Hitomi Mori, Yuta Kikuchi, Marcello Benedetti, Matthias Rosenkranz

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

Imagine you are trying to solve a massive, complex puzzle. In the world of quantum computing, this puzzle is called the Quantum Linear System (QLS). It's like trying to find the exact recipe (the solution) that turns a specific set of ingredients (the input) into a finished dish, but the recipe is hidden inside a giant, mysterious cookbook (the matrix).

For a long time, scientists knew how to solve this puzzle, but they weren't entirely sure how hard it actually was to do. They had a "best guess" for the difficulty, but it was based on an unpublished note from a famous researcher named Harrow. It was like everyone agreeing on a rule of thumb without ever seeing the official rulebook.

This paper, written by Hitomi Mori and her team, is the team finally opening that rulebook and writing down the proof. They wanted to answer two main questions:

How does the "messiness" of the puzzle (called the condition number) affect the difficulty?
How does the "sparse" nature of the puzzle (where most of the pages are blank, called sparsity) affect the difficulty?

Here is a breakdown of their findings using simple analogies:

1. The "Messiness" of the Puzzle (Condition Number)

Imagine trying to balance a stack of cards.

Low Condition Number: The cards are perfectly flat and stacked neatly. It's easy to find the bottom card.
High Condition Number: The cards are warped, slippery, and leaning precariously. It takes a lot of careful, repeated adjustments just to figure out where the bottom card is.

The paper confirms that the more "warped" or "messy" your puzzle is, the harder it is to solve. Specifically, the difficulty grows in direct proportion to this messiness. If the puzzle is twice as messy, it takes twice as many steps to solve it.

2. The "Blank Pages" (Sparsity)

Now, imagine your puzzle book has 1,000 pages.

Dense: Every single page has a clue written on it.
Sparse: Only 5 pages have clues; the other 995 are blank.

Intuitively, you might think a sparse puzzle is easier because there's less to read. However, the paper proves that the scattered nature of the clues actually adds a specific type of difficulty. It's like searching for a needle in a haystack where the needles are hidden in random, specific spots.

The team proved that the difficulty doesn't just grow with the number of clues, but with the square root of the number of potential spots where clues could be. If you double the number of "potential clue spots" (sparsity), the difficulty doesn't double; it increases by a factor of roughly 1.4 (the square root of 2).

The Big Discovery: The "Folklore" Proven

For years, researchers whispered a "folklore" rule: "The difficulty is proportional to the Messiness multiplied by the Square Root of the Sparsity."

But no one had written a rigorous mathematical proof for this. It was like a legend in the scientific community.

This paper is the proof.
The authors built a bridge between the quantum puzzle and a classic logic game called "Parity" (figuring out if a string of switches has an odd or even number of "on" positions).

They showed that if you could solve the quantum puzzle efficiently, you could also solve the logic game efficiently.
Since we already know exactly how hard the logic game is, they could work backward to prove exactly how hard the quantum puzzle must be.

What They Found

They established two "Lower Bounds" (the minimum amount of effort required):

For the messiness and precision: You need at least a certain amount of effort proportional to the messiness. This confirmed what was already suspected.
For the sparsity (The New Result): They proved that for a standard level of accuracy, you need at least Messiness × Square Root of Sparsity steps.

Why This Matters (Without Overpromising)

The paper doesn't claim this will immediately cure diseases or build faster AI. Instead, it does something more fundamental: It sets the speed limit.

Think of it like a race car engineer. Before, they knew the car couldn't go faster than 200 mph because of the engine (the condition number). Now, they have proven that the car also can't go faster than 200 mph because of the aerodynamics (the sparsity).

By proving this "speed limit," the authors have shown that the current best quantum algorithms are likely as good as they can possibly get regarding sparsity. You can't invent a new algorithm that magically ignores the square root of the sparsity; the laws of physics (in this case, quantum query complexity) say it's impossible.

The One Thing They Didn't Solve

The paper admits one piece of the puzzle is still missing. They proved the relationship for "messiness" and "sparsity" separately, but they couldn't yet prove a single formula that perfectly combines messiness, sparsity, and precision all at once. They left that as a challenge for future researchers to tackle.

In short: The authors took a widely accepted guess about how hard quantum math problems are, and they finally wrote down the mathematical proof that confirms the "sparsity" of the data makes the problem harder in a specific, predictable way.

Technical Summary: Sparsity-dependent Complexity Lower Bound of Quantum Linear System Solvers

Problem Statement
The paper addresses the Quantum Linear System (QLS) problem, which involves finding an approximation $|\tilde{x}\rangle$ of the normalized quantum state $|x\rangle = A^{-1}|b\rangle / \|A^{-1}|b\rangle\|$ such that $\||\tilde{x}\rangle - |x\rangle\| \le \epsilon$ . The complexity of solving this problem is governed by three primary parameters: the condition number $\kappa$ of the matrix $A$ , the sparsity $s$ (maximum non-zero entries per row/column), and the target error $\epsilon$ .

While the query complexity upper bound for QLS solvers is known to be $O(\kappa \log(1/\epsilon))$ , the rigorous lower bound incorporating the sparsity $s$ has remained an open problem. Although it is widely accepted in the community ("folklore") that the lower bound should scale as $\Omega(\kappa \sqrt{s} \log(1/\epsilon))$ , attributing this to unpublished work by Harrow and Kothari, a formal proof capturing the sparsity dependence has been lacking.

Methodology
The authors establish lower bounds by reducing known Boolean problems to the QLS problem. They utilize the sparse-matrix oracle access model, where a matrix $A$ is accessed via oracles specifying the positions and values of non-zero entries.

Re-derivation of $\kappa$ and $\epsilon$ dependence:
To re-establish the $\Omega(\kappa \log(1/\epsilon))$ bound, the authors reduce the unbounded-error PARITY problem to QLS. They construct a specific matrix $A$ dependent on the PARITY input bits. By analyzing the spectral properties of this matrix and the resulting quantum state after applying the QLS solver, they demonstrate that solving QLS with a specific error tolerance allows one to solve the PARITY problem. Since the unbounded-error query complexity of PARITY is $\Theta(n)$ , this yields the desired lower bound.
Derivation of Sparsity ( $s$ ) dependence:
To prove the sparsity-dependent bound, the authors reduce the bounded-error PARITY $\circ$ OR problem to QLS. This composite problem involves computing the parity of the results of $n$ independent OR functions, each acting on $m$ bits.
- They construct a matrix $A$ where the non-zero entries encode the inputs to the OR functions. The construction ensures the matrix has sparsity $s = \Theta(m)$ .
- The matrix is designed such that its inverse, when applied to a specific initial state, encodes the solution to the PARITY $\circ$ OR problem in the phase of the quantum state.
- The authors analyze the condition number $\kappa$ of this constructed matrix, showing $\kappa = \Theta(n)$ , and the sparsity $s = \Theta(m)$ .
- By leveraging the known bounded-error query complexity of PARITY $\circ$ OR, which is $\Theta(n\sqrt{m})$ , they map this complexity back to the QLS parameters.

Key Contributions and Results

Rigorous Proof of $\Omega(\kappa \log(1/\epsilon))$ : The paper provides a detailed, explicit derivation of the lower bound for QLS with constant sparsity, confirming the optimality of recent algorithms regarding $\kappa$ and $\epsilon$ . This proof relies on the unbounded-error PARITY reduction.
New Lower Bound $\Omega(\kappa \sqrt{s})$ : The primary contribution is the proof that any quantum algorithm solving QLS with constant error must have a query complexity of at least $\Omega(\kappa \sqrt{s})$ $Ω (κ s)$ . This is achieved by reducing the bounded-error PARITY $\circ$ $\circ$ OR problem to QLS.
- The proof demonstrates that for a fixed constant error, the query complexity scales with the square root of the sparsity.
- The result is derived under the assumption that the target error $\epsilon$ is constant ( $O(1)$ ), meaning the $\epsilon$ -dependence is not explicitly captured in this specific bound.

Significance and Limitations
The authors position this work as a crucial stepping stone toward the complete characterization of QLS complexity. By rigorously establishing the $\sqrt{s}$ dependence, they validate the folklore belief regarding the role of sparsity in query complexity.

However, the paper explicitly acknowledges that the joint lower bound capturing all three parameters simultaneously— $\Omega(\kappa \sqrt{s} \log(1/\epsilon))$ —remains an open problem.

The authors note that attempting to use the unbounded-error PARITY $\circ$ OR problem to capture all parameters fails because the unbounded OR problem can be solved with $O(1)$ queries, which collapses the sparsity dependence in the reduction.
They suggest that future work may require reducing QLS from different Boolean function compositions or utilizing polynomial approximation techniques (specifically finding the minimum degree of a polynomial that $\epsilon$ -approximates $1/x$ ), though the latter currently lacks known results regarding $\epsilon$ -dependence and does not naturally incorporate sparsity.

In summary, the paper provides the first rigorous proof that sparsity $s$ fundamentally impacts the query complexity of QLS solvers, establishing a lower bound of $\Omega(\kappa \sqrt{s})$ for constant error, while leaving the full multi-parameter bound as a subject for future investigation.