Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2610.05806

Quantum Complexity of Solving Linear Equations on Higher-Order Networks

Caesnan M. G. Leditto

quant-phSubmitted Oct 5, 2026• Announced Oct 6, 2026• 0 citations
arXivHTMLPDF

Abstract

Higher-order networks (HONs) represent interactions among groups of objects, supporting the study of collective behaviour that pairwise models can miss. In simplicial models of these networks, Hodge Laplacian linear systems provide a common mathematical framework for analysis, for example, for solving statistical ranking problems and investigating long-term stability in coupled oscillator systems. The large number of variables associated with edges, triangles, and higher-dimensional simplices can make these systems costly to solve. Recent quantum algorithms address this bottleneck. However, comparisons with particular classical algorithms do not decision output whether solving these linear system problems establishes a quantum complexity foundation for provable quantum advantage. We prove that preparing a quantum state encoding the normalized minimum-norm solution of Hodge Laplacian linear systems is $\mathsf{BQP}$-hard under the specified sparse oracle model and parameter promises. Our sequence of reductions maps an arbitrary polynomial-time bounded-error quantum computation to such linear systems. Each reduction allows efficient recovery of the normalized minimum-norm solution of the preceding linear system. Together with an efficient quantum algorithm for the associated decision problem from the approximate solution state, we show that this problem is $\mathsf{BQP}$-complete. These results provide a worst-case complexity foundation for evaluating quantum advantage in HON analysis and show that the $\mathsf{BQP}$-hardness of the quantum linear system problem (QLSP) persists even when the matrices are restricted to Hodge Laplacians.

Related papers

Solving Laplacian Systems in Logarithmic Space

François Le Gall

We investigate the space complexity of solving linear systems of equations. While all known deterministic or randomized algorithms solving a square system of $n$ linear equations in $n$ variables require $Ω(\log^2 n)$ space, Ta-Shma (STOC 2013) recently showed that on a quantum computer an approximate solution can be computed in logarithmic space, giving the first explicit computational task for which quantum computation seems to outperform classical computation with respect to space complexity. In this paper we show that for systems of linear equations in the Laplacian matrix of graphs, the same logarithmic space complexity can actually be achieved by a classical (i.e., non-quantum) algorithm. More precisely, given a system of linear equations $Lx=b$, where $L$ is the (normalized) Laplacian matrix of a graph on $n$ vertices and $b$ is a unit-norm vector, our algorithm outputs a vector $\tilde x$ such that $\left\lVert\tilde x -x\right\rVert\le 1/\mathrm{poly}(n)$ and uses only $O(\log n)$ space if the underlying graph has polynomially bounded weights. We also show how to estimate, again in logarithmic space, the smallest non-zero eigenvalue of $L$.

arXiv:1608.01426•Aug 4, 2016•0 citations

Efficient Quantum Algorithms for Higher-Order Coupled Oscillators

Caesnan M. G. Leditto, Angus Southwell, Muhammad Usman +1 more

Higher-order networks with multiway interactions can exhibit collective dynamical phenomena that are absent in traditional pairwise network models. However, analyzing such dynamics becomes computationally prohibitive as their state space grows combinatorially in the multiway interaction order. Here we develop quantum algorithms for two central tasks -- synchronization estimation and certification of the no-phase-locking regime -- in the simplicial Kuramoto model. This model is a higher-order generalization of the celebrated Kuramoto model for coupled oscillators on graph-based networks. Under explicit assumptions on data access and types, and simplicial structure, we derive end-to-end quantum gate complexities and identify regimes with polynomial quantum advantage for synchronization estimation and super-polynomial quantum advantage for no-phase-locking certification over classical methods. More broadly, these results extend quantum algorithms for higher-order networks from structural analysis to nonlinear dynamical diagnostics, easing a major computational bottleneck and opening a route to quantum methods for probing higher-order phenomena beyond the reach of direct classical approaches.

quant-pharXiv:2604.20108•Apr 23, 2026•0 citations

Quantum Communication Complexity of Linear Regression

Ashley Montanaro, Changpeng Shao

Quantum computers may achieve speedups over their classical counterparts for solving linear algebra problems. However, in some cases—such as for low-rank matrices—dequantized algorithms demonstrate that there cannot be an exponential quantum speedup. In this work, we show that quantum computers have provable polynomial and exponential speedups in terms of communication complexity for some fundamental linear algebra problems if there is no restriction on the rank. We mainly focus on solving linear regression and Hamiltonian simulation. In the quantum case, the task is to prepare the quantum state of the result. To allow for a fair comparison, in the classical case, the task is to sample from the result. We investigate these two problems in two-party and multiparty models, propose near-optimal quantum protocols, and prove quantum/classical lower bounds. In this process, we propose an efficient quantum protocol for quantum singular value transformation, which is a powerful technique for designing quantum algorithms. We feel this will be helpful in developing efficient quantum protocols for many other problems.

arXiv:2210.01601•ACM Transactions on Computation Theory•Sep 23, 2023•8 citations

An Optimal Quantum Linear Systems Algorithm

Carlos Bravo-Prieto, Aram W. Harrow, Robin Kothari

In the quantum linear systems problem (QLSP), we are given query access to a $d$-sparse $N\times N$ matrix $A$ with condition number $κ$, and the ability to prepare a quantum state proportional to a vector $\vec b$. The goal is to output an $ε$-approximation to the quantum state proportional to the solution $\vec x$ of $A\vec{x}=\vec{b}$. Following a long line of work, the best previously known quantum algorithms for the QLSP had query complexities $O(κd\log(1/ε))$ and $κ\sqrt d(κd/ε)^{o(1)}$, while the best known lower bounds were $Ω(κ\log(1/ε))$ and $Ω(κ\sqrt d)$. We improve these bounds and show that the complexity of the QLSP is $Θ(κ\sqrt d\log(1/ε))$. We also resolve an open problem of Berry and Childs by showing that any $N\times N$ unitary can be implemented with bounded error using $O(\sqrt N)$ queries to its matrix entries.

quant-pharXiv:2609.35660•Sep 29, 2026•0 citations

Faster quantum linear system solver beyond the condition number

Alexander M. Dalzell, Jianqiang Li, Yuan Su

The spectral condition number is a widely adopted measure of worst-case cost for quantum linear system solvers. Yet it can significantly overestimate the actual runtime for a typical problem instance. We present two quantum algorithms that produce the normalized solution $|x\rangle$ of linear system $Ax=| b \rangle$ to accuracy $ε$ with complexity independent of the condition number $κ=\lVert A^{-1}\rVert$. We focus on the standard input model where $A$ is accessed through a block encoding and $| b \rangle$ is prepared by a unitary. But we also introduce an affine dilation model that encodes $A$ and $| b \rangle$ jointly, allowing further refinements of the query complexity. Our truncation-based solver makes an optimal number of queries to $| b \rangle$ and $\operatorname{\mathbf{O}}\left(κ_{\mathrm{eff}}\operatorname{polylog}\left(\frac{κ_{\mathrm{eff}}}ε\right)\right)$ queries to $A$. We prove a family of upper bounds on the effective condition number, including $κ_{\mathrm{eff}}\leq\frac{\lVert(A^\dagger A)^{-t/2}|x\rangle\rVert^{1/t}}{ε^{1/t}}$ for positive even integer $t$ and $κ_{\mathrm{eff}}\leq\frac{\lVert A^{-1\dagger}(A^\dagger A)^{-(t-1)/2}|x\rangle\rVert^{1/t}}{ε^{1/t}}$ for positive odd $t$, overcoming the $κ$-barrier. Our filtering-based solver is extremely simple with a favorable runtime prefactor. In particular, the solver has query complexity $3\frac{\lVert A^{-1\dagger}|x\rangle\rVert}ε$ to leading order when the solution norm is known. We then present a similarly simple solution norm estimator with the same asymptotic cost up to logarithmic factors. Our quantum linear system solvers thus substantially improve a recent algorithm of Li, enabling faster quantum linear system solving beyond the condition number.

quant-pharXiv:2607.07691•Jul 9, 2026•0 citations

Solving Laplacian Systems in Logarithmic Space.

François Le Gall

We investigate the space complexity of solving linear systems of equations. While all known deterministic or randomized algorithms solving a square system of $n$ linear equations in $n$ variables require $\Omega(\log^2 n)$ space, Ta-Shma (STOC 2013) recently showed that on a quantum computer an approximate solution can be computed in logarithmic space, giving the first explicit computational task for which quantum computation seems to outperform classical computation with respect to space complexity. In this paper we show that for systems of linear equations in the Laplacian matrix of graphs, the same logarithmic space complexity can actually be achieved by a classical (i.e., non-quantum) algorithm. More precisely, given a system of linear equations $Lx=b$, where $L$ is the (normalized) Laplacian matrix of a graph on $n$ vertices and $b$ is a unit-norm vector, our algorithm outputs a vector $\tilde x$ such that $\left\lVert\tilde x -x\right\rVert\le 1/\mathrm{poly}(n)$ and uses only $O(\log n)$ space if the underlying graph has polynomially bounded weights. We also show how to estimate, again in logarithmic space, the smallest non-zero eigenvalue of $L$.

•Aug 4, 2016•1 citation
Higher-order networks (HONs) represent interactions among groups of objects, supporting the study of collective behaviour that pairwise models can miss. In simplicial models of these networks, Hodge Laplacian linear systems provide a common mathematical framework for analysis, for example, for solving statistical ranking problems and investigating long-term stability in coupled oscillator systems. The large number of variables associated with edges, triangles, and higher-dimensional simplices can make these systems costly to solve. Recent quantum algorithms address this bottleneck. However, comparisons with particular classical algorithms do not decision output whether solving these linear system problems establishes a quantum complexity foundation for provable quantum advantage. We prove that preparing a quantum state encoding the normalized minimum-norm solution of Hodge Laplacian linear systems is BQP\mathsf{BQP}BQP-hard under the specified sparse oracle model and parameter promises. Our sequence of reductions maps an arbitrary polynomial-time bounded-error quantum computation to such linear systems. Each reduction allows efficient recovery of the normalized minimum-norm solution of the preceding linear system. Together with an efficient quantum algorithm for the associated decision problem from the approximate solution state, we show that this problem is BQP\mathsf{BQP}BQP-complete. These results provide a worst-case complexity foundation for evaluating quantum advantage in HON analysis and show that the BQP\mathsf{BQP}BQP-hardness of the quantum linear system problem (QLSP) persists even when the matrices are restricted to Hodge Laplacians.
We investigate the space complexity of solving linear systems of equations. While all known deterministic or randomized algorithms solving a square system of nnn linear equations in nnn variables require Ω(log⁡2n)Ω(\log^2 n)Ω(log2n) space, Ta-Shma (STOC 2013) recently showed that on a quantum computer an approximate solution can be computed in logarithmic space, giving the first explicit computational task for which quantum computation seems to outperform classical computation with respect to space complexity. In this paper we show that for systems of linear equations in the Laplacian matrix of graphs, the same logarithmic space complexity can actually be achieved by a classical (i.e., non-quantum) algorithm. More precisely, given a system of linear equations Lx=bLx=bLx=b, where LLL is the (normalized) Laplacian matrix of a graph on nnn vertices and bbb is a unit-norm vector, our algorithm outputs a vector x~\tilde xx~ such that ∥x~−x∥≤1/poly(n)\left\lVert\tilde x -x\right\rVert\le 1/\mathrm{poly}(n)∥x~−x∥≤1/poly(n) and uses only O(log⁡n)O(\log n)O(logn) space if the underlying graph has polynomially bounded weights. We also show how to estimate, again in logarithmic space, the smallest non-zero eigenvalue of LLL.
Higher-order networks with multiway interactions can exhibit collective dynamical phenomena that are absent in traditional pairwise network models. However, analyzing such dynamics becomes computationally prohibitive as their state space grows combinatorially in the multiway interaction order. Here we develop quantum algorithms for two central tasks -- synchronization estimation and certification of the no-phase-locking regime -- in the simplicial Kuramoto model. This model is a higher-order generalization of the celebrated Kuramoto model for coupled oscillators on graph-based networks. Under explicit assumptions on data access and types, and simplicial structure, we derive end-to-end quantum gate complexities and identify regimes with polynomial quantum advantage for synchronization estimation and super-polynomial quantum advantage for no-phase-locking certification over classical methods. More broadly, these results extend quantum algorithms for higher-order networks from structural analysis to nonlinear dynamical diagnostics, easing a major computational bottleneck and opening a route to quantum methods for probing higher-order phenomena beyond the reach of direct classical approaches.
Quantum computers may achieve speedups over their classical counterparts for solving linear algebra problems. However, in some cases—such as for low-rank matrices—dequantized algorithms demonstrate that there cannot be an exponential quantum speedup. In this work, we show that quantum computers have provable polynomial and exponential speedups in terms of communication complexity for some fundamental linear algebra problems if there is no restriction on the rank. We mainly focus on solving linear regression and Hamiltonian simulation. In the quantum case, the task is to prepare the quantum state of the result. To allow for a fair comparison, in the classical case, the task is to sample from the result. We investigate these two problems in two-party and multiparty models, propose near-optimal quantum protocols, and prove quantum/classical lower bounds. In this process, we propose an efficient quantum protocol for quantum singular value transformation, which is a powerful technique for designing quantum algorithms. We feel this will be helpful in developing efficient quantum protocols for many other problems.
In the quantum linear systems problem (QLSP), we are given query access to a ddd-sparse N×NN\times NN×N matrix AAA with condition number κκκ, and the ability to prepare a quantum state proportional to a vector b⃗\vec bb. The goal is to output an εεε-approximation to the quantum state proportional to the solution x⃗\vec xx of Ax⃗=b⃗A\vec{x}=\vec{b}Ax=b. Following a long line of work, the best previously known quantum algorithms for the QLSP had query complexities O(κdlog⁡(1/ε))O(κd\log(1/ε))O(κdlog(1/ε)) and κd(κd/ε)o(1)κ\sqrt d(κd/ε)^{o(1)}κd​(κd/ε)o(1), while the best known lower bounds were Ω(κlog⁡(1/ε))Ω(κ\log(1/ε))Ω(κlog(1/ε)) and Ω(κd)Ω(κ\sqrt d)Ω(κd​). We improve these bounds and show that the complexity of the QLSP is Θ(κdlog⁡(1/ε))Θ(κ\sqrt d\log(1/ε))Θ(κd​log(1/ε)). We also resolve an open problem of Berry and Childs by showing that any N×NN\times NN×N unitary can be implemented with bounded error using O(N)O(\sqrt N)O(N​) queries to its matrix entries.
The spectral condition number is a widely adopted measure of worst-case cost for quantum linear system solvers. Yet it can significantly overestimate the actual runtime for a typical problem instance. We present two quantum algorithms that produce the normalized solution ∣x⟩|x\rangle∣x⟩ of linear system Ax=∣b⟩Ax=| b \rangleAx=∣b⟩ to accuracy εεε with complexity independent of the condition number κ=∥A−1∥κ=\lVert A^{-1}\rVertκ=∥A−1∥. We focus on the standard input model where AAA is accessed through a block encoding and ∣b⟩| b \rangle∣b⟩ is prepared by a unitary. But we also introduce an affine dilation model that encodes AAA and ∣b⟩| b \rangle∣b⟩ jointly, allowing further refinements of the query complexity. Our truncation-based solver makes an optimal number of queries to ∣b⟩| b \rangle∣b⟩ and O⁡(κeffpolylog⁡(κeffε))\operatorname{\mathbf{O}}\left(κ_{\mathrm{eff}}\operatorname{polylog}\left(\frac{κ_{\mathrm{eff}}}ε\right)\right)O(κeff​polylog(εκeff​​)) queries to AAA. We prove a family of upper bounds on the effective condition number, including κeff≤∥(A†A)−t/2∣x⟩∥1/tε1/tκ_{\mathrm{eff}}\leq\frac{\lVert(A^\dagger A)^{-t/2}|x\rangle\rVert^{1/t}}{ε^{1/t}}κeff​≤ε1/t∥(A†A)−t/2∣x⟩∥1/t​ for positive even integer ttt and κeff≤∥A−1†(A†A)−(t−1)/2∣x⟩∥1/tε1/tκ_{\mathrm{eff}}\leq\frac{\lVert A^{-1\dagger}(A^\dagger A)^{-(t-1)/2}|x\rangle\rVert^{1/t}}{ε^{1/t}}κeff​≤ε1/t∥A−1†(A†A)−(t−1)/2∣x⟩∥1/t​ for positive odd ttt, overcoming the κκκ-barrier. Our filtering-based solver is extremely simple with a favorable runtime prefactor. In particular, the solver has query complexity 3∥A−1†∣x⟩∥ε3\frac{\lVert A^{-1\dagger}|x\rangle\rVert}ε3ε∥A−1†∣x⟩∥​ to leading order when the solution norm is known. We then present a similarly simple solution norm estimator with the same asymptotic cost up to logarithmic factors. Our quantum linear system solvers thus substantially improve a recent algorithm of Li, enabling faster quantum linear system solving beyond the condition number.
We investigate the space complexity of solving linear systems of equations. While all known deterministic or randomized algorithms solving a square system of nnn linear equations in nnn variables require Ω(log⁡2n)\Omega(\log^2 n)Ω(log2n) space, Ta-Shma (STOC 2013) recently showed that on a quantum computer an approximate solution can be computed in logarithmic space, giving the first explicit computational task for which quantum computation seems to outperform classical computation with respect to space complexity. In this paper we show that for systems of linear equations in the Laplacian matrix of graphs, the same logarithmic space complexity can actually be achieved by a classical (i.e., non-quantum) algorithm. More precisely, given a system of linear equations Lx=bLx=bLx=b, where LLL is the (normalized) Laplacian matrix of a graph on nnn vertices and bbb is a unit-norm vector, our algorithm outputs a vector x~\tilde xx~ such that ∥x~−x∥≤1/poly(n)\left\lVert\tilde x -x\right\rVert\le 1/\mathrm{poly}(n)∥x~−x∥≤1/poly(n) and uses only O(log⁡n)O(\log n)O(logn) space if the underlying graph has polynomially bounded weights. We also show how to estimate, again in logarithmic space, the smallest non-zero eigenvalue of LLL.