Quantum Complexity of Solving Linear Equations on Higher-Order Networks
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 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-complete. These results provide a worst-case complexity foundation for evaluating quantum advantage in HON analysis and show that the BQP-hardness of the quantum linear system problem (QLSP) persists even when the matrices are restricted to Hodge Laplacians.
Related
- Quantum-Classical Neural Networks for Solving Lindblad Master Equations
- Ghost tasking for parametrized Gaussian Processes solving linear differential equations
- Utilizing Neural Networks for Solving Functional Renormalization Group Flow Equations
- Gen-PINNs: Generative Adversarial Physics Informed Neural Networks for solving partial differential equations
- Quantum Frozen--Oseen homotopy analysis method with LCHS for solving nonlinear partial differential equations
BibTeX
@misc{leditto2026quantum,
title = {{Quantum Complexity of Solving Linear Equations on Higher-Order Networks}},
author = {Caesnan M. G. Leditto},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.05806},
eprint = {2610.05806},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.05806},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Quantum Complexity of Solving Linear Equations on Higher-Order Networks
AU - Caesnan M. G. Leditto
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2610.05806
UR - https://arxiv.org/abs/2610.05806
AB - 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-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-complete. These results provide a worst-case complexity foundation for evaluating quantum advantage in HON analysis and show that the BQP-hardness of the quantum linear system problem (QLSP) persists even when the matrices are restricted to Hodge Laplacians.
ER -