CPS Journals
中国物理学会期刊网 物理 物理学报 Chinese Physics B Chinese Physics Letters
Submit Manuscript Peer Review Get e-Alerts
Express Letter

Quantum Algorithm for Approximating Maximum Independent Sets

  • 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

    • Show all affliationsShow less
Funds: 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).
More Information   | 
PDF View FullText Get Citation
  • Received Date: January 24, 2021
  • Published Date: February 28, 2021
    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 α(G) in low polynomial time. The best classical algorithms, by contrast, produce independent sets of size about half of α(G) in polynomial time.
    • FullText(HTML)
  • View FullText
    • References (12)
  • [1]
    Johån H 1999 Acta Math. 182 105 doi: 10.1007/BF02392825

    CrossRef Google Scholar

    [2]
    Zuckerman D 2006 Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing New York: Association for Computing Machinery p 681 doi: 10.1145/1132516.1132612

    CrossRef Google Scholar

    [3]
    Matula D W 1976 The Largest Clique Size in a Random Graph, Technical Report CS 7608 Department of Computer Science, Southern Methodist University, Dallas, Texas 75275

    Google Scholar

    [4]
    Coja-Oghlan A and Efthymiou C 2015 Random Struct. & Algorithms 47 436 doi: 10.1002/rsa.20550

    CrossRef Google Scholar

    [5]
    Frieze A M 1990 Discrete Math. 81 171 doi: 10.1016/0012-365X9090149-C

    CrossRef Google Scholar

    [6]
    Wu B, Yu H and Wilczek F 2020 Phys. Rev. A 101 012318 doi: 10.1103/PhysRevA.101.012318

    CrossRef Google Scholar

    [7]
    Hu Y, Zhang Z and Wu B 2021 Chin. Phys. B 30 020308 doi: 10.1088/1674-1056/abd741

    CrossRef Google Scholar

    [8]
    Wilczek F and Zee A 1984 Phys. Rev. Lett. 52 2111 doi: 10.1103/PhysRevLett.52.2111

    CrossRef Google Scholar

    [9]
    Farhi E, Goldstone J, Gutmann S and Sipser M 2000 arXiv:quant-ph/0001106v1

    Google Scholar

    [10]
    Jerrum M 1992 Random Struct. & Algorithms 3 347 doi: 10.1002/rsa.3240030402

    CrossRef Google Scholar

    [11]
    Ambainis A and Regev O 2004 arXiv:quant-ph/0411152

    Google Scholar

    [12]
    Farhi E and Gutmann S 1998 Phys. Rev. A 58 915 doi: 10.1103/PhysRevA.58.915

    CrossRef Google Scholar

    • Related Articles

  • Related Articles

    [1]Hong-ming Ding, Yue-wen Yin, Song-di Ni, Yan-jing Sheng, Yu-qiang Ma. Accurate Evaluation on the Interactions of SARS-CoV-2 with Its Receptor ACE2 and Antibodies CR3022/CB6 [J]. Chin. Phys. Lett., 2021, 38(1): 018701. doi: 10.1088/0256-307X/38/1/018701
    [2]HE Li-Ping, DAI Jun, SUN Yue, WANG Jing-Yi, LÜ Hui-Bin, WANG Shu-Fang, JIN Kui-Juan, ZHOU Yue-Liang, YANG Guo-Zhen. Label-Free and Real-Time Detection of Antigen-Antibody Capture Processes Using the Oblique-Incidence Reflectivity Difference Technique [J]. Chin. Phys. Lett., 2012, 29(7): 070702. doi: 10.1088/0256-307X/29/7/070702
    [3]JIA Er-Wei, PANG Hou-Rong. KKN and KKN Molecular States with I=1/2, 3/2 and JP=1/2+ Studied with Three-Body Faddeev Calculations [J]. Chin. Phys. Lett., 2011, 28(6): 061401. doi: 10.1088/0256-307X/28/6/061401
    [4]LI Wei, GAO Zong-Mao, GU Jiao. Effects of Variant Rates and Noise on Epidemic Spreading [J]. Chin. Phys. Lett., 2011, 28(5): 058903. doi: 10.1088/0256-307X/28/5/058903
    [5]ZHANG Ping, WANG Hai-Jun. Monte Carlo Simulation on Growth of Antibody-Antigen Complexes: the Role of Unequal Reactivity [J]. Chin. Phys. Lett., 2010, 27(3): 038701. doi: 10.1088/0256-307X/27/3/038701
    [6]XIA Tian, ZHOU Shu-Yu, CHEN Peng, LI Lin, HONG Tao, WANG Yu-Zhu. Continuous Imaging of a Single Neutral Atom in a Variant Magneto-Optical Trap\hyperlinks* [J]. Chin. Phys. Lett., 2010, 27(2): 023701. doi: 10.1088/0256-307X/27/2/023701
    [7]ZHOU Lin-xiang, J.R. Hardy, XU Xin. Molecular Dynamics Simulation of Binary Fluorozirconate Glass ZrF4.BaF2 [J]. Chin. Phys. Lett., 1998, 15(5): 326-328.
    [8]ZHAO Meishan (Meishan ZHAO). Variational Versus Nonvariational Calculations for H2Br Molecular Scattering [J]. Chin. Phys. Lett., 1994, 11(1): 16-19.
    [9]SHAO Jun. Structural Change of SiO2 Glass Under High Pressure -- a Molecular Dynamics Study [J]. Chin. Phys. Lett., 1993, 10(11): 669-672.
    [10]ZHENG Youfeng, WANG Wenhua, LIN Jingu, SHE Yongbo, FIU Kejian. Time-Resolved Infrared Detection of Molecular Nitrogen and Hydrogen Complexes of (η6-C6H6)Cr(CO)2 in Gas Phase [J]. Chin. Phys. Lett., 1992, 9(6): 329-332.
    • Supplements (1)

  • Other Related Supplements

  • Cited by

    Periodical cited type(4)

    1. Chen, Y.-Q., Xu, Y., Ma, Y.-Q. et al. Improving performance of screening MM/PBSA in protein-ligand interactions via machine learning. Chinese Physics B, 2025, 34(1): 018701. DOI:10.1088/1674-1056/ad8ecb
    2. Lan, P.D., Nissley, D.A., O’Brien, E.P. et al. Deciphering the free energy landscapes of SARS-CoV-2 wild type and Omicron variant interacting with human ACE2. Journal of Chemical Physics, 2024, 160(5): 055101. DOI:10.1063/5.0188053
    3. Xu, Y., Huang, S.-W., Ding, H.-M. et al. Molecular dynamics simulations on the interactions between nucleic acids and a phospholipid bilayer. Chinese Physics B, 2024, 33(2): 028701. DOI:10.1088/1674-1056/ad1178
    4. Zhou, Y., Lin, X. Binding kinetics of ten small-molecule drug candidates on SARS-CoV-2 3CLpro revealed by biomolecular simulations. Medicine in Novel Technology and Devices, 2023. DOI:10.1016/j.medntd.2023.100257

    Other cited types(0)

Catalog

    Article views (979) PDF downloads (1211) Cited by(4)
    Turn off MathJax
    Article Contents
    Abstract
    Article Text
    References
    Related Articles
    Authors
  • Guideline for Authors
  • Submit and Track a Manuscript
  • Update Your Information
  • Copyright Agreement
  • Ethical Policy
    • Referees
  • Guideline for Referees
  • Submit a Report
  • Volunteer to be a Reviewer
  • Update Your Information
  • Review Policy
    • Browse
  • Accepted
  • In Press
  • Current Issue
  • All Issues
  • Browse by Field
    • About
  • About CPL
  • Editorial Board
  • Editorial Board of Young Scientists
  • Editorial Office

    • Copyright © Chinese Physics Letters

    Address: Institute of Physics, Chinese Academy of Sciences, P.O.Box 603, Beijing 100190 China

    Tel: (86-10) 82649490 or 82649378Fax: 86-10-82649604E-mail: cpl@aphy.iphy.ac.cn

    Supported by: Beijing Renhe Information Technology Co., Ltd. 

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return