Topological Signal Processing on Quantum Computers for Higher-Order Network Analysis
arXiv:2312.07672 · doi:10.1103/PhysRevApplied.23.054054
Abstract
Predicting and analyzing global behaviour of complex systems is challenging due to the intricate nature of their component interactions. Recent work has started modelling complex systems using networks endowed with multiway interactions among nodes, known as higher-order networks. Simplicial complexes are a class of higher-order networks that have received significant attention due to their topological structure and connections to Hodge theory. Topological signal processing (TSP) utilizes these connections to analyze and manipulate signals defined on non-Euclidean domains such as simplicial complexes. In this work, we present a general quantum algorithm for implementing filtering processes in TSP and describe its application to extracting network data based on the Hodge decomposition. We leverage pre-existing tools introduced in recent quantum algorithms for topological data analysis and combine them with spectral filtering techniques using the quantum singular value transformation framework. While this paper serves as a proof-of-concept, we obtain a super-polynomial improvement over the best known classical algorithms for TSP filtering processes, modulo some important caveats about encoding and retrieving the data from a quantum state. The proposed algorithm generalizes the applicability of tools from quantum topological data analysis to novel applications in analyzing high-dimensional complex systems.
References in corpus (36)
- Quantum algorithm for solving linear systems of equations
- Quantum support vector machine for big data classification
- Networks beyond pairwise interactions: structure and dynamics
- Discrete Signal Processing on Graphs
- Quantum principal component analysis
- The physics of higher-order interactions in complex systems
- Hamiltonian Simulation by Qubitization
- Optimal Hamiltonian Simulation by Quantum Signal Processing
- Simulating Hamiltonian dynamics with a truncated Taylor series
- Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
- Dynamics on higher-order networks: A review
- What are higher-order networks?
- Explosive higher-order Kuramoto dynamics on simplicial complexes
- Multi-parameter estimation in networked quantum sensors
- Topological Data Analysis of Financial Time Series: Landscapes of Crashes
- Topological Signal Processing over Simplicial Complexes
- Graph Frequency Analysis of Brain Signals
- Multiorder Laplacian for synchronization in higher-order networks
- Quantum State Preparation with Optimal Circuit Depth: Implementations and Applications
- Signal Processing on Higher-Order Networks: Livin' on the Edge ... and Beyond
- Efficient phase-factor evaluation in quantum signal processing
- Focus beyond quadratic speedups for error-corrected quantum advantage
- Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization
- Weighted simplicial complexes and their representation power of higher-order network data and topology
- Quantum Spectral Clustering
- Quantum sensing networks for the estimation of linear functions
- Towards quantum advantage via topological data analysis
- Analyzing Prospects for Quantum Advantage in Topological Data Analysis
- Simplicial Convolutional Filters
- Spectral Detection of Simplicial Communities via Hodge Laplacians
- Multivariable quantum signal processing (M-QSP): prophecies of the two-headed oracle
- Protocols for estimating multiple functions with quantum sensor networks: geometry and performance
- Finding Small and Large k-Clique Instances on a Quantum Computer
- Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis
- Complexity of Supersymmetric Systems and the Cohomology Problem
- Representation of the Fermionic Boundary Operator