论文标题
使用量子$ \ MATHBB {Z} _2 $晶格计理论解决哈密顿周期问题
Solving Hamiltonian Cycle Problem using Quantum $\mathbb{Z}_2$ Lattice Gauge Theory
论文作者
论文摘要
图理论中的哈密顿周期（HC）问题是众所周知的NP完整问题。我们以$ \ mathbb {z} _2 $ lattice仪表理论（LGT）为晶格上定义的用图作为二元为二元表示的方法。当耦合参数$ g $小于临界值$ g_c $时，基态是所有配置的叠加，并以相同的单旋转状态进行封闭的旋转，可以通过使用时间复杂性$ o（\ frac {\ frac {g_c^2} {1} {g_c^2} {g_c^2} \ sq rt { \ frac {1} {\ varepsilon} n_e^{3/2}（n_v^3 + \ frac {n_e} {g_c}}））$，其中$ n_v $ and $ n_v $和$ n_e $分别是图形的顶点和evertices $。随后在这些封闭串中寻找HC的搜索解决了HC问题。对于一些小图的随机示例，我们证明了$ g_c $的平均值对$ \ sqrt {n_ {hc}} $，$ n_ {hc} $是HCS的数量，而平均值为$ \ frac {1} {g_c} $的平均值。因此，建议对于某些图，可以在多项式时间内解决HC问题。还讨论了使用$ g_c $来推断$ n_ {hc} $的可能的量子算法。
The Hamiltonian cycle (HC) problem in graph theory is a well-known NP-complete problem. We present an approach in terms of $\mathbb{Z}_2$ lattice gauge theory (LGT) defined on the lattice with the graph as its dual. When the coupling parameter $g$ is less than the critical value $g_c$, the ground state is a superposition of all configurations with closed strings of spins in a same single-spin state, which can be obtained by using an adiabatic quantum algorithm with time complexity $O(\frac{1}{g_c^2} \sqrt{ \frac{1}{\varepsilon} N_e^{3/2}(N_v^3 + \frac{N_e}{g_c}}))$, where $N_v$ and $N_e$ are the numbers of vertices and edges of the graph respectively. A subsequent search for a HC among those closed-strings solves the HC problem. For some random samples of small graphs, we demonstrate that the dependence of the average value of $g_c$ on $\sqrt{N_{hc}}$, $N_{hc}$ being the number of HCs, and that of the average value of $\frac{1}{g_c}$ on $N_e$ are both linear. It is thus suggested that for some graphs, the HC problem may be solved in polynomial time. A possible quantum algorithm using $g_c$ to infer $N_{hc}$ is also discussed.
