Sparsity-dependent Complexity Lower Bound of Quantum Linear System Solvers

• URL: http://arxiv.org/abs/2601.16697v1
• Date: Fri, 23 Jan 2026 12:27:08 GMT
• Title: Sparsity-dependent Complexity Lower Bound of Quantum Linear System Solvers
• Authors: Hitomi Mori, Yuta Kikuchi, Marcello Benedetti, Matthias Rosenkranz,
• Abstract summary: Quantum linear system (QLS) solvers are a fundamental class of quantum algorithms used in potential quantum computing applications.<n>Main parameters determining the complexity of QLS solvers are the condition number $$ and sparsity $s$ of the linear system.<n>We prove the lower bound of $(sqrts)$ for any quantum algorithm that solves QLS with constant error.
• Score: 1.1666234644810893
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quantum linear system (QLS) solvers are a fundamental class of quantum algorithms used in many potential quantum computing applications, including machine learning and solving differential equations. The performance of quantum algorithms is often measured by their query complexity, which quantifies the number of oracle calls required to access the input. The main parameters determining the complexity of QLS solvers are the condition number $κ$ and sparsity $s$ of the linear system, and the target error $ε$. To date, the best known query-complexity lower bound is $Ω(κ\log(1/ε))$, which establishes the optimality of the most recent QLS solvers. The original proof of this lower bound is attributed to Harrow and Kothari, but their result is unpublished. Furthermore, when discussing a more general lower bound including the sparsity $s$ of the linear system, it has become folklore that it should read as $Ω( κ\sqrt{s}\log(1/ε))$. In this work, we establish the rigorous lower bound capturing the sparsity dependence of QLS. We prove the lower bound of $Ω(κ\sqrt{s})$ for any quantum algorithm that solves QLS with constant error. While the dependence on all parameters $κ,s,ε$ remains an open problem, our result provides a crucial stepping stone toward the complete characterization of QLS complexity.

Related papers

• Beyond asymptotic scaling: Comparing functional quantum linear solvers [0.0]
  Many quantum linear solvers (QLS) have been developed, competing to achieve the best oracle worst-case complexity.<n>Most QLS assume fault-tolerant quantum computers, so they cannot yet be benchmarked on real hardware.<n>We consider four well-known QVT algorithms which directly implement an approximate matrix inversion function.
  arXiv  Detail & Related papers  (2025-03-27T12:09:52Z)
• An Empirical Analysis on the Effectiveness of the Variational Quantum Linear Solver [10.562108865927005]
  Variational Quantum Linear Solver (VQLS) addresses linear systems of the form $Ax=b$. Key advantage of VQLS is its use of amplitude encoding, which requires a number of qubits that scales logarithmically with the linear system size. In this study, we extend the application of VQLS to more general and larger problem instances, including problems where state preparation is non-trivial.
  arXiv  Detail & Related papers  (2024-09-10T08:50:18Z)
• Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
  We study the problem of estimating frequency response functions of systems of coupled, classical harmonic oscillators using a quantum computer.<n>Our proposed quantum algorithm operates in the standard $s-sparse, oracle-based query access model.<n>We show that a simple adaptation of our algorithm solves the random glued-trees problem in time.
  arXiv  Detail & Related papers  (2024-05-14T15:28:37Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  We study the power of unentangled quantum proofs with non-negative amplitudes, a class which we denote $textQMA+(2)$. In particular, we design global protocols for small set expansion, unique games, and PCP verification. We show that QMA(2) is equal to $textQMA+(2)$ provided the gap of the latter is a sufficiently large constant.
  arXiv  Detail & Related papers  (2024-02-29T01:35:46Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• Unifying (Quantum) Statistical and Parametrized (Quantum) Algorithms [65.268245109828]
  We take inspiration from Kearns' SQ oracle and Valiant's weak evaluation oracle. We introduce an extensive yet intuitive framework that yields unconditional lower bounds for learning from evaluation queries.
  arXiv  Detail & Related papers  (2023-10-26T18:23:21Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
  Quantum approximate optimization algorithms (QAOAs) utilize the power of quantum machines and inherit the spirit of adiabatic evolution. We propose QAOA-in-QAOA ($textQAOA2$) to solve arbitrary large-scale MaxCut problems using quantum machines. Our method can be seamlessly embedded into other advanced strategies to enhance the capability of QAOAs in large-scale optimization problems.
  arXiv  Detail & Related papers  (2022-05-24T03:49:10Z)
• The Parameterized Complexity of Quantum Verification [7.7155343772895275]
  We show that for the problem of quantum circuit satisfiability, there exists an algorithm solving the problem with a runtime scaling exponentially in the number of non-Clifford gates. We derive new lower bounds on the $T$-count of circuit satisfiability instances and the $$-count of the $W$-state.
  arXiv  Detail & Related papers  (2022-02-16T14:53:42Z)
• Resource Optimisation of Coherently Controlled Quantum Computations with the PBS-calculus [55.2480439325792]
  Coherent control of quantum computations can be used to improve some quantum protocols and algorithms. We refine the PBS-calculus, a graphical language for coherent control inspired by quantum optics.
  arXiv  Detail & Related papers  (2022-02-10T18:59:52Z)
• On solving classes of positive-definite quantum linear systems with quadratically improved runtime in the condition number [0.0]
  We show that solving a Quantum Linear System entails a runtime linear in $kappa$ when $A$ is positive definite. We present two new quantum algorithms featuring a quadratic speed-up in $kappa$.
  arXiv  Detail & Related papers  (2021-01-28T08:41:21Z)
• Variational Quantum Linear Solver [0.3774866290142281]
  We propose a hybrid quantum-classical algorithm for solving linear systems on near-term quantum computers. We numerically solve non-trivial problems of size up to $250times250$ using Rigetti's quantum computer.
  arXiv  Detail & Related papers  (2019-09-12T17:28:09Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.