Quantum walk on simplicial complexes for simplicial community detection

• URL: http://arxiv.org/abs/2401.00699v3
• Date: Fri, 26 Apr 2024 14:25:20 GMT
• Title: Quantum walk on simplicial complexes for simplicial community detection
• Authors: Euijun Song,
• Abstract summary: We present a quantum walk algorithm to detect higher-order community structures called simplicial communities. The potential of our quantum algorithm is tested on Zachary's karate club network.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quantum walks have emerged as a transformative paradigm in quantum information processing and can be applied to various graph problems. This study explores discrete-time quantum walks on simplicial complexes, a higher-order generalization of graph structures. Simplicial complexes, encoding higher-order interactions through simplices, offer a richer topological representation of complex systems. Since the conventional classical random walk cannot directly detect community structures, we present a quantum walk algorithm to detect higher-order community structures called simplicial communities. We utilize the Fourier coin to produce entangled translation states among adjacent simplices in a simplicial complex. The potential of our quantum algorithm is tested on Zachary's karate club network. This study may contribute to understanding complex systems at the intersection of algebraic topology and quantum walk algorithms.

Related papers

• Benchmarking quantum chaos from geometric complexity [0.23436632098950458]
  We consider a new method to study geometric complexity for interacting non-Gaussian quantum mechanical systems. Within some limitations, geometric complexity can indeed be a good indicator of quantum chaos.
  arXiv  Detail & Related papers  (2024-10-24T14:04:58Z)
• 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)
• Character Complexity: A Novel Measure for Quantum Circuit Analysis [0.0]
  This paper introduces Character Complexity, a novel measure that bridges Group-theoretic concepts with practical quantum computing concerns. I prove several key properties of character complexity and establish a surprising connection to the classical simulability of quantum circuits. I present innovative visualization methods for character complexity, providing intuitive insights into the structure of quantum circuits.
  arXiv  Detail & Related papers  (2024-08-19T01:58:54Z)
• Quantum Walks on Simplicial Complexes and Harmonic Homology: Application to Topological Data Analysis with Superpolynomial Speedups [9.538251541300028]
  We introduce a novel quantum walk that encodes the Laplacian, a key mathematical object whose spectral properties reflect the underlying simplicial complex. Our results achieve superpolynomial quantum speedup with quantum walks without relying on quantum oracles for large datasets.
  arXiv  Detail & Related papers  (2024-04-23T18:00:17Z)
• Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
  The anticipated applications of quantum computers span across science and industry. We present a survey of several potential application areas of quantum algorithms. We outline the challenges and opportunities in each area in an "end-to-end" fashion.
  arXiv  Detail & Related papers  (2023-10-04T17:53:55Z)
• Discovering Quantum Circuit Components with Program Synthesis [6.390357081534995]
  We show how a computer can incrementally learn concepts relevant for quantum circuit synthesis with experience. We show how, starting from a set of elementary gates, we can automatically discover a library of new useful composite gates.
  arXiv  Detail & Related papers  (2023-05-02T18:17:07Z)
• One-Way Ticket to Las Vegas and the Quantum Adversary [78.33558762484924]
  We show that quantum Las Vegas query complexity is exactly equal to the quantum adversary bound. This is achieved by transforming a feasible solution to the adversary inversion problem into a quantum query algorithm.
  arXiv  Detail & Related papers  (2023-01-05T11:05:22Z)
• How smooth is quantum complexity? [0.0]
  The "quantum complexity" of a unitary operator measures the difficulty of its construction from a set of elementary quantum gates. In this paper, we present a unified perspective on various notions of quantum complexity, viewed as functions on the space of unitary operators.
  arXiv  Detail & Related papers  (2021-06-15T17:58:08Z)
• Information Scrambling in Computationally Complex Quantum Circuits [56.22772134614514]
  We experimentally investigate the dynamics of quantum scrambling on a 53-qubit quantum processor. We show that while operator spreading is captured by an efficient classical model, operator entanglement requires exponentially scaled computational resources to simulate.
  arXiv  Detail & Related papers  (2021-01-21T22:18:49Z)
• Quantum walk processes in quantum devices [55.41644538483948]
  We study how to represent quantum walk on a graph as a quantum circuit. Our approach paves way for the efficient implementation of quantum walks algorithms on quantum computers.
  arXiv  Detail & Related papers  (2020-12-28T18:04:16Z)
• Quantum information spreading in a disordered quantum walk [50.591267188664666]
  We design a quantum probing protocol using Quantum Walks to investigate the Quantum Information spreading pattern. We focus on the coherent static and dynamic disorder to investigate anomalous and classical transport. Our results show that a Quantum Walk can be considered as a readout device of information about defects and perturbations occurring in complex networks.
  arXiv  Detail & Related papers  (2020-10-20T20:03:19Z)

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.