arXiv:2610.05806
Quantum Complexity of Solving Linear Equations on Higher-Order Networks
Caesnan M. G. Leditto
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.
AI Summary
The paper asks whether restricting quantum linear systems to simplicial Hodge Laplacians preserves the $\mathsf{BQP}$-hardness of general sparse linear systems. The task is to prepare the normalized minimum-norm solution $M^+|\eta\rangle/\|M^+\eta\|$, rather than output its coordinates classically. It establishes $\mathsf{BQP}$-hardness of solution-state preparation at prescribed inverse-polynomial accuracy for upper Hodge Laplacians in every fixed dimension $k\ge1$, and lower and full Hodge Laplacians for fixed $k\ge2$. Associated decision problems, defined by prescribed recovery and measurement of the solution, are $\mathsf{BQP}$-complete when access oracles are supplied as circuits. Hard instances use unweighted complexes, constant row and column sparsity, constant matrix-normalization factors, polynomial inverse spectral bounds, and constant-support right-hand sides. The reduction encodes a circuit of length $L$ in a Dirichlet propagation system with condition number $\Theta(L^2)$ and a weighted history-state solution. Bounded-occurrence difference–average equations enable a triangulated-surface construction adapted from classical reductions. Balancing surface copies preserves the minimum-norm solution isometrically, while local indexing and spectral estimates support efficient oracle access and recovery. Pseudoinverse identities produce Hodge systems, suspension raises dimension, and block encoding with QSVT establishes quantum membership under spectral and range-overlap promises. The classification is worst-case and input-model dependent, not an advantage result for practical network observables. It does not establish hardness for ordinary graph ranking, clique-complex-restricted applications, or oscillator norm thresholds. Full-Laplacian hardness initially uses a vanishing upper term; making both terms nonzero uses a disjoint component, leaving connected constructions open.
Most parts of the current draft were generated using GPT-6 Astra for technical presentation only.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.