SciPost Submission Page
Constant-time Quantum Algorithm for Homology Detection in Closed Curves
by Nhat A. Nghiem Vu, Xianfeng David Gu, Tzu-Chieh Wei
This Submission thread is now published as
Submission summary
| Submission information |
| Preprint Link: |
scipost_202302_00042v2
(pdf)
|
| Date accepted: |
2023-05-22 |
| Date submitted: |
2023-03-24 19:18 |
| Submitted by: |
Nghiem Vu, Nhat A. |
| Submitted to: |
SciPost Physics |
| Ontological classification |
| Academic field: |
Physics |
| Specialties: |
|
| Approach: |
Theoretical |
Abstract
Given a loop or more generally 1-cycle $r$ on a closed two-dimensional
manifold or surface, represented by a triangulated mesh, a question in
computational topology asks whether or not it is homologous to zero. We frame
and tackle this problem in the quantum setting. Given an oracle that one can
use to query the inclusion of edges on a closed curve, we design a quantum
algorithm for such a homology detection with a constant running time, with
respect to the size or the number of edges on the loop $r$. In contrast,
classical algorithms take a linear time. Our quantum algorithm can be extended
to check whether two closed loops belong to the same homology class.
Furthermore, it can be applied to a specific problem in the homotopy detection,
namely, checking whether two curves are not homotopically equivalent on a
closed two-dimensional manifold.
Published as
SciPost Phys. 15, 049 (2023)
