EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Constant-time quantum algorithm for homology detection in closed curves

Nhat Anh Nghiem Vu, Xianfeng David Gu, Tzu-Chieh Wei

SciPost Physics · 04.08.2023 · 15 (2)

DOI: 10.21468/scipostphys.15.2.049 ↗

Kurz gefasst

Fachartikel in der Zeitschrift SciPost Physics, online erschienen am 04.08.2023. Verfasst von Nhat Anh Nghiem Vu und 2 weiteren Autor:innen. Die Arbeit wurde bisher 2-mal zitiert (Crossref) und nennt 39 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: National Institutes of Health, National Science Foundation.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Given a loop or more generally 1-cycle r r of size L 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 r , requiring only a single usage of oracle. In contrast, classical algorithm requires \Omega(L) Ω ( L ) oracle usage, followed by a linear time processing and can be improved to logarithmic by using a parallel algorithm. 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.

Förderung

  • National Institutes of Health
  • National Science Foundation

Zitieren

APA

Vu, N. A. N., Gu, X. D., & Wei, T. (2023). Constant-time quantum algorithm for homology detection in closed curves. SciPost Physics, 15(2). https://doi.org/10.21468/scipostphys.15.2.049

Vancouver

Vu NAN, Gu XD, Wei T. Constant-time quantum algorithm for homology detection in closed curves. SciPost Physics. 2023;15(2). doi:10.21468/scipostphys.15.2.049

BibTeX
@article{Vu2023,
  author = {Vu, Nhat Anh Nghiem and Gu, Xianfeng David and Wei, Tzu-Chieh},
  title = {Constant-time quantum algorithm for homology detection in closed curves},
  journal = {SciPost Physics},
  year = {2023},
  volume = {15},
  number = {2},
  doi = {10.21468/scipostphys.15.2.049}
}
Kostenlos starten →