TY - JOUR
T1 - Solving independent set problems with photonic quantum circuits
AU - Yin, Xu Fei
AU - Yao, Xing Can
AU - Wu, Biao
AU - Fei, Yue Yang
AU - Mao, Yingqiu
AU - Zhang, Rui
AU - Liu, Li Zheng
AU - Wang, Zhenduo
AU - Li, Li
AU - Liu, Nai Le
AU - Wilczek, Frank
AU - Chen, Yu Ao
AU - Pan, Jian Wei
N1 - Publisher Copyright:
Copyright © 2023 the Author(s). Published by PNAS.
PY - 2023/5/30
Y1 - 2023/5/30
N2 - An independent set (IS) is a set of vertices in a graph such that no edge connects any two vertices. In adiabatic quantum computation [E. Farhi, et al., Science 292, 472–475 (2001); A. Das, B. K. Chakrabarti, Rev. Mod. Phys. 80, 1061–1081 (2008)], a given graph G(V, E) can be naturally mapped onto a many-body Hamiltonian HGIS(V,E), with edges E being the two-body interactions between adjacent vertices V . Thus, solving the IS problem is equivalent to finding all the computational basis ground states of HGIS(V,E). Very recently, non-Abelian adiabatic mixing (NAAM) has been proposed to address this task, exploiting an emergent non-Abelian gauge symmetry of HISG(V,E) [B. Wu, H. Yu, F. Wilczek, Phys. Rev. A 101, 012318 (2020)]. Here, we solve a representative IS problem G(8, 7) by simulating the NAAM digitally using a linear optical quantum network, consisting of three C-Phase gates, four deterministic two-qubit gate arrays (DGA), and ten single rotation gates. The maximum IS has been successfully identified with sufficient Trotterization steps and a carefully chosen evolution path. Remarkably, we find IS with a total probability of 0.875(16), among which the nontrivial ones have a considerable weight of about 31.4%. Our experiment demonstrates the potential advantage of NAAM for solving IS-equivalent problems.
AB - An independent set (IS) is a set of vertices in a graph such that no edge connects any two vertices. In adiabatic quantum computation [E. Farhi, et al., Science 292, 472–475 (2001); A. Das, B. K. Chakrabarti, Rev. Mod. Phys. 80, 1061–1081 (2008)], a given graph G(V, E) can be naturally mapped onto a many-body Hamiltonian HGIS(V,E), with edges E being the two-body interactions between adjacent vertices V . Thus, solving the IS problem is equivalent to finding all the computational basis ground states of HGIS(V,E). Very recently, non-Abelian adiabatic mixing (NAAM) has been proposed to address this task, exploiting an emergent non-Abelian gauge symmetry of HISG(V,E) [B. Wu, H. Yu, F. Wilczek, Phys. Rev. A 101, 012318 (2020)]. Here, we solve a representative IS problem G(8, 7) by simulating the NAAM digitally using a linear optical quantum network, consisting of three C-Phase gates, four deterministic two-qubit gate arrays (DGA), and ten single rotation gates. The maximum IS has been successfully identified with sufficient Trotterization steps and a carefully chosen evolution path. Remarkably, we find IS with a total probability of 0.875(16), among which the nontrivial ones have a considerable weight of about 31.4%. Our experiment demonstrates the potential advantage of NAAM for solving IS-equivalent problems.
KW - adiabatic mixing
KW - independent sets
KW - photonic quantum computer
KW - quantum algorithm
UR - http://www.scopus.com/inward/record.url?scp=85159803819&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85159803819&partnerID=8YFLogxK
U2 - 10.1073/pnas.2212323120
DO - 10.1073/pnas.2212323120
M3 - Article
C2 - 37216545
AN - SCOPUS:85159803819
SN - 0027-8424
VL - 120
JO - Proceedings of the National Academy of Sciences of the United States of America
JF - Proceedings of the National Academy of Sciences of the United States of America
IS - 22
M1 - e2212323120
ER -