Quantum Walks on Simplicial Complexes and Harmonic Homology: Application to Topological Data Analysis with Superpolynomial Speedups

• URL: http://arxiv.org/abs/2404.15407v1
• Date: Tue, 23 Apr 2024 18:00:17 GMT
• Title: Quantum Walks on Simplicial Complexes and Harmonic Homology: Application to Topological Data Analysis with Superpolynomial Speedups
• Authors: Ryu Hayakawa, Kuo-Chin Chen, Min-Hsiu Hsieh,
• Abstract summary: 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.
• Score: 9.538251541300028
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Incorporating higher-order interactions in information processing enables us to build more accurate models, gain deeper insights into complex systems, and address real-world challenges more effectively. However, existing methods, such as random walks on oriented simplices and homology, which capture these interactions, are not known to be efficient. This work investigates whether quantum walks on simplicial complexes exhibit quantum advantages. We introduce a novel quantum walk that encodes the combinatorial Laplacian, a key mathematical object whose spectral properties reflect the topology of the underlying simplicial complex. Furthermore, we construct a unitary encoding that projects onto the kernel of the Laplacian, representing the space of harmonic cycles in the complex's homology. Combined with the efficient construction of quantum walk unitaries for clique complexes that we present, this paves the way for utilizing quantum walks to explore higher-order interactions within topological structures. Our results achieve superpolynomial quantum speedup with quantum walks without relying on quantum oracles for large datasets. Crucially, the walk operates on a state space encompassing both positively and negatively oriented simplices, effectively doubling its size compared to unoriented approaches. Through coherent interference of these paired simplices, we are able to successfully encode the combinatorial Laplacian, which would otherwise be impossible. This observation constitutes our major technical contribution. We also extend the framework by constructing variant quantum walks. These variants enable us to: (1) estimate the normalized persistent Betti numbers, capturing topological information throughout a deformation process, and (2) verify a specific QMA$_1$-hard problem, showcasing potential applications in computational complexity theory.

Related papers

• Complex-Phase Extensions of Szegedy Quantum Walk on Graphs [0.0]
  This work introduces a graph-phased Szegedy's quantum walk, which incorporates link phases and local arbitrary phase rotations (APR) We demonstrate how to adapt quantum circuits to these advancements, allowing phase patterns that ensure computational practicality. Our findings illuminate the path towards more versatile and powerful quantum computing paradigms.
  arXiv  Detail & Related papers  (2024-10-29T12:57:31Z)
• Complexity of Quantum-Mechanical Evolutions from Probability Amplitudes [0.0]
  We study the complexity of both time-optimal and time sub-optimal quantum Hamiltonian evolutions connecting arbitrary source and a target states on the Bloch sphere equipped with the Fubini-Study metric.
  arXiv  Detail & Related papers  (2024-08-26T12:54:51Z)
• 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)
• Quantum walk on simplicial complexes for simplicial community detection [0.0]
  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.
  arXiv  Detail & Related papers  (2024-01-01T08:43:43Z)
• 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)
• Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
  We develop new and efficient quantum algorithms for fidelity estimation with provable performance guarantees. Our algorithms use advanced quantum linear algebra techniques, such as the quantum singular value transformation. We prove that fidelity estimation to any non-trivial constant additive accuracy is hard in general.
  arXiv  Detail & Related papers  (2022-03-30T02:02:16Z)
• Tweezer-programmable 2D quantum walks in a Hubbard-regime lattice [1.286202369590401]
  We study continuous-time quantum walks of single atoms on a 2D square lattice. We perform proof-of-principle demonstrations of spatial search using these walks. When scaled to more particles, the capabilities demonstrated here can be extended to study a variety of problems in quantum information science.
  arXiv  Detail & Related papers  (2022-02-02T18:56:11Z)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems. By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
  arXiv  Detail & Related papers  (2021-08-03T17:49:09Z)
• Learning quantum phases via single-qubit disentanglement [4.266508670102269]
  We present a novel and efficient quantum phase transition, utilizing disentanglement with reinforcement learning-optimized variational quantum circuits. Our approach not only identifies phase transitions based on the performance of the disentangling circuits but also exhibits impressive scalability, facilitating its application in larger and more complex quantum systems.
  arXiv  Detail & Related papers  (2021-07-08T00:15:31Z)
• Quantum communication complexity beyond Bell nonlocality [87.70068711362255]
  Efficient distributed computing offers a scalable strategy for solving resource-demanding tasks. Quantum resources are well-suited to this task, offering clear strategies that can outperform classical counterparts. We prove that a new class of communication complexity tasks can be associated to Bell-like inequalities.
  arXiv  Detail & Related papers  (2021-06-11T18:00:09Z)
• 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)

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.