Topological Signal Processing on Quantum Computers for Higher-Order Network Analysis

• URL: http://arxiv.org/abs/2312.07672v3
• Date: Mon, 28 Oct 2024 23:57:06 GMT
• Title: Topological Signal Processing on Quantum Computers for Higher-Order Network Analysis
• Authors: Caesnan M. G. Leditto, Angus Southwell, Behnam Tonekaboni, Gregory A. L. White, Muhammad Usman, Kavan Modi,
• Abstract summary: We present a general quantum algorithm for implementing filtering processes in Topological signal processing. We describe its application to extracting network data based on the Hodge decomposition. The proposed algorithm generalizes the applicability of tools from quantum topological data analysis to novel applications in analyzing high-dimensional complex systems.
• Score: 0.5181797490530444
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Hybrid quantum-classical framework for Betti number estimation with applications to topological data analysis [0.7997838571956237]
  Topological data analysis (TDA) is a rapidly growing area that applies techniques from algebraic topology to extract robust features from large-scale data.<n>A key task in TDA is the estimation of (normalized) Betti numbers, which capture essential topological invariants.<n>We explore an alternative direction: combining classical and quantum resources to estimate the Betti numbers of a simplicial complex more efficiently.
  arXiv  Detail & Related papers  (2025-08-02T23:19:11Z)
• Topological network analysis using a programmable photonic quantum processor [3.0018652145221614]
  We develop a universal programmable quantum processor that enables the encoding of arbitrary complex-weight networks.<n>We show how this quantum approach can identify weighted $k$-cliques and estimate Betti numbers.<n>These findings showcase how photonic quantum computing can be applied to analyse the topological characteristics of real-world networks.
  arXiv  Detail & Related papers  (2025-07-10T20:33:52Z)
• Quantum Graph Convolutional Networks Based on Spectral Methods [10.250921033123152]
  Graph Convolutional Networks (GCNs) are specialized neural networks for feature extraction from graph-structured data. This paper introduces an enhancement to GCNs based on spectral methods by integrating quantum computing techniques.
  arXiv  Detail & Related papers  (2025-03-09T05:08:15Z)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
  Given a quantum circuit containing d tunable RZ gates and G-d Clifford gates, can a learner perform purely classical inference to efficiently predict its linear properties? We prove that the sample complexity scaling linearly in d is necessary and sufficient to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d. We devise a kernel-based learning model capable of trading off prediction error and computational complexity, transitioning from exponential to scaling in many practical settings.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• Defining Neural Network Architecture through Polytope Structures of Dataset [53.512432492636236]
  This paper defines upper and lower bounds for neural network widths, which are informed by the polytope structure of the dataset in question. We develop an algorithm to investigate a converse situation where the polytope structure of a dataset can be inferred from its corresponding trained neural networks. It is established that popular datasets such as MNIST, Fashion-MNIST, and CIFAR10 can be efficiently encapsulated using no more than two polytopes with a small number of faces.
  arXiv  Detail & Related papers  (2024-02-04T08:57:42Z)
• Quantum topological data analysis via the estimation of the density of states [17.857341127079305]
  We develop a quantum topological data analysis protocol based on the estimation of the density of states (DOS) of the Laplacian. We test our protocol on noiseless and noisy quantum simulators and run examples on IBM quantum processors.
  arXiv  Detail & Related papers  (2023-12-12T09:43:04Z)
• Higher-order topological kernels via quantum computation [68.8204255655161]
  Topological data analysis (TDA) has emerged as a powerful tool for extracting meaningful insights from complex data. We propose a quantum approach to defining Betti kernels, which is based on constructing Betti curves with increasing order.
  arXiv  Detail & Related papers  (2023-07-14T14:48:52Z)
• Understanding the Mapping of Encode Data Through An Implementation of Quantum Topological Analysis [0.7106986689736827]
  We show the difference in encoding techniques can be visualized by investigating the topology of the data embedded in complex Hilbert space. Our results suggest the encoding method needs to be considered carefully within different quantum machine learning models.
  arXiv  Detail & Related papers  (2022-09-21T18:46:08Z)
• Deep Architecture Connectivity Matters for Its Convergence: A Fine-Grained Analysis [94.64007376939735]
  We theoretically characterize the impact of connectivity patterns on the convergence of deep neural networks (DNNs) under gradient descent training. We show that by a simple filtration on "unpromising" connectivity patterns, we can trim down the number of models to evaluate.
  arXiv  Detail & Related papers  (2022-05-11T17:43:54Z)
• Dist2Cycle: A Simplicial Neural Network for Homology Localization [66.15805004725809]
  Simplicial complexes can be viewed as high dimensional generalizations of graphs that explicitly encode multi-way ordered relations. We propose a graph convolutional model for learning functions parametrized by the $k$-homological features of simplicial complexes.
  arXiv  Detail & Related papers  (2021-10-28T14:59:41Z)
• Detailed Account of Complexity for Implementation of Some Gate-Based Quantum Algorithms [55.41644538483948]
  In particular, some steps of the implementation, as state preparation and readout processes, can surpass the complexity aspects of the algorithm itself. We present the complexity involved in the full implementation of quantum algorithms for solving linear systems of equations and linear system of differential equations.
  arXiv  Detail & Related papers  (2021-06-23T16:33:33Z)
• Signal processing on simplicial complexes [19.035399031968502]
  We focus on a closely related, but distinct third perspective: how can we use higher-order relationships to process signals and data supported on higher-order network structures. In particular, we survey how ideas from signal processing of data supported on regular domains, such as time series or images, can be extended to graphs and simplicial complexes.
  arXiv  Detail & Related papers  (2021-06-14T14:56:51Z)
• Autoregressive Transformer Neural Network for Simulating Open Quantum Systems via a Probabilistic Formulation [5.668795025564699]
  We present an approach for tackling open quantum system dynamics. We compactly represent quantum states with autoregressive transformer neural networks. Efficient algorithms have been developed to simulate the dynamics of the Liouvillian superoperator.
  arXiv  Detail & Related papers  (2020-09-11T18:00:00Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.