论文标题
用于近似最大独立集的量子算法
Quantum Algorithm for Approximating Maximum Independent Sets
论文作者
论文摘要
我们提出了一种量子算法，用于近似于基于归化基态的亚山地空间中的量子非亚伯绝热混合的图形的最大独立集，从而在次级汉密尔顿中产生量子退火。对于稀疏图和密集图，我们的量子算法平均可以找到一组非常接近$α（g）$的独立尺寸，这是给定图形$ g $的最大独立集的大小。数值结果表明，$ O（n^2）$时间复杂度量子算法足以找到一组独立的尺寸$ $（1-ε）α（g）$。最佳的经典近似算法可以在多项式时间内产生一组$α（g）$的一半的独立大小。
We present a quantum algorithm for approximating maximum independent sets of a graph based on quantum non-Abelian adiabatic mixing in the sub-Hilbert space of degenerate ground states, which generates quantum annealing in a secondary Hamiltonian. For both sparse and dense graphs, our quantum algorithm on average can find an independent set of size very close to $α(G)$, which is the size of the maximum independent set of a given graph $G$. Numerical results indicate that an $O(n^2)$ time complexity quantum algorithm is sufficient for finding an independent set of size $(1-ε)α(G)$. The best classical approximation algorithm can produce in polynomial time an independent set of size about half of $α(G)$.
