Fetching the paper…

Reading the bibliography…

2020

Quantum Algorithm for Approximating Maximum Independent Sets

Yu, Hongye, Wilczek, Frank, Wu, Biao

Original
PDF
Post on X

Understand

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 $\alpha(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-\epsilon)\alpha(G)$.
The best classical approximation algorithm can produce in polynomial time an independent set of size about half of $\alpha(G)$.

Quantum Algorithm for Approximating Maximum Independent Sets · Around

Built on

D. W. Matula, The largest clique size in a random graph (Department of Computer Science, Southern Methodist University, 1976)
1976
Earlier work this paper cites.
F. Wilczek and A. Zee, Phys. Rev. Lett. 52
1984
Earlier work this paper cites.
A. M. Frieze, Discrete Mathematics 81
1990
Earlier work this paper cites.
M. Jerrum, Random Structures & Algorithms 3
1992
Earlier work this paper cites.

Similar

E. Farhi and S. Gutmann, Phys. Rev. A 58
1998
Cited alongside, same era.
H. Johan, Acta Mathematica 182
1999
Cited alongside, same era.
E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser, arXiv:quant-ph/0001106v1 (2000)
2000
Cited alongside, same era.
A. Ambainis and O. Regev, arXiv:quant-ph/0411152 (2004)
2004
Cited alongside, same era.

Then

D. Zuckerman, in Proceedings of the thirty-eighth annual ACM symposium on Theory of computing (2006), pp. 681–690
2006
Later among the works it cites.
A. Coja-Oghlan and C. Efthymiou, Random Structures & Algorithms 47
2015
Later among the works it cites.
B. Wu, H. Yu, and F. Wilczek, Physical Review A 101
2020
Closest in time.
Yanglin Hu, Zhelun Zhang, Biao Wu, Chinese Physics B 30, 020308 (2021)
2021
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…