Solving independent set problems with photonic quantum circuits
| Autor: | Xu-Fei Yin, Xing-Can Yao, Biao Wu, Yue-Yang Fei, Yingqiu Mao, Rui Zhang, Li-Zheng Liu, Zhenduo Wang, Li Li, Nai-Le Liu, Frank Wilczek, Yu-Ao Chen, Jian-Wei Pan |
|---|---|
| Rok vydání: | 2023 |
| Předmět: | |
| Zdroj: | Proceedings of the National Academy of Sciences. 120 |
| ISSN: | 1091-6490 0027-8424 |
| DOI: | 10.1073/pnas.2212323120 |
| Popis: | 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 H IS G ( 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 H IS G ( V , E ) . Very recently, non-Abelian adiabatic mixing (NAAM) has been proposed to address this task, exploiting an emergent non-Abelian gauge symmetry of H IS G ( 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|