| GENERAL |
|
|
|
|
Quantum Algorithm for Approximating Maximum Independent Sets |
| Hongye Yu1, Frank Wilczek2,3,4,5,6, and Biao Wu7,4,8* |
1Department of Physics and Astronomy, Stony Brook University, Stony Brook, NY 11794, USA
2Center for Theoretical Physics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA
3D. Lee Institute, Shanghai Jiao Tong University, Shanghai 200240, China
4Wilczek Quantum Center, School of Physics and Astronomy, Shanghai Jiao Tong University, Shanghai 200240, China
5Department of Physics, Stockholm University, Stockholm SE-106 91, Sweden
6Department of Physics and Origins Project, Arizona State University, Tempe AZ 25287, USA
7International Center for Quantum Materials, School of Physics, Peking University, Beijing 100871, China
8Collaborative Innovation Center of Quantum Matter, Beijing 100871, China
|
|
| Cite this article: |
|
Hongye Yu, Frank Wilczek, and Biao Wu 2021 Chin. Phys. Lett. 38 030304 |
|
|
|
|
Abstract 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 random graphs $G$, numerical simulation suggests that our algorithm on average finds an independent set of size close to the maximum size $\alpha(G)$ in low polynomial time. The best classical algorithms, by contrast, produce independent sets of size about half of $\alpha(G)$ in polynomial time.
|
|
Received: 25 January 2021
Published: 26 February 2021
|
|
| PACS: |
03.67.Ac
|
(Quantum algorithms, protocols, and simulations)
|
| |
03.67.Lx
|
(Quantum computation architectures and implementations)
|
| |
89.70.Eg
|
(Computational complexity)
|
|
|
| Fund: F. Wilczek is supported in part by the U.S. Department of Energy (Grant No. DE-SC0012567), the European Research Council (Grant No. 742104), and the Swedish Research Council (Grant No. 335–2014-7424). B. Wu is supported by the National Key R&D Program of China (Grant Nos. 2017YFA0303302 and 2018YFA0305602), the National Natural Science Foundation of China (Grant No. 11921005), and Shanghai Municipal Science and Technology Major Project (Grant No. 2019SHZDZX01). |
|
|
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
