论文标题
用于封闭曲线中同源性检测的恒定时间量子算法
Constant-time Quantum Algorithm for Homology Detection in Closed Curves
论文作者
论文摘要
鉴于循环或更一般的1个周期$ r $大小l $ l $在封闭的二维歧管或表面上，以三角形网格表示，计算拓扑中的一个问题询问它是否与零同源。我们在量子设置中构架并解决此问题。鉴于人们可以用来查询封闭曲线上的边缘的oracle，因此我们为这种同源性检测的量子算法设计了一个持续的运行时间，相对于loop $ r $上的大小或边缘数量，只需要单个Oracle使用。相比之下，经典算法需要$ω（L）$ oracle使用，然后进行线性时间处理，并可以使用并行算法将其改进到对数。我们的量子算法可以扩展，以检查两个闭环是否属于同一个同源性类别。此外，可以将其应用于同质检测中的特定问题，即检查两条曲线是否为\ textit {not}在封闭的二维流形上同等等效。
Given a loop or more generally 1-cycle $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$, requiring only a single usage of oracle. In contrast, classical algorithm requires $Ω(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 \textit{not} homotopically equivalent on a closed two-dimensional manifold.
