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 $\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.

arXiv:2610.05806 [quant-ph]

(or arXiv:2610.05806v1 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2610.05806 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.