Solving independent set problems with photonic quantum circuits

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

doi:10.1073/pnas.2212323120

Solving independent set problems with photonic quantum circuits

Proc Natl Acad Sci U S A. 2023 May 30;120(22):e2212323120. doi: 10.1073/pnas.2212323120. Epub 2023 May 22.

Authors

Xu-Fei Yin^{1

2

3}, Xing-Can Yao^{1

2

3}, Biao Wu^{4

5}, Yue-Yang Fei^{1

2

3}, Yingqiu Mao^{1

2

3}, Rui Zhang^{1

2

3}, Li-Zheng Liu^{1

2

3}, Zhenduo Wang⁴, Li Li^{1

2

3}, Nai-Le Liu^{1

2

3}, Frank Wilczek^{5

6

7

8

9}, Yu-Ao Chen^{1

2

3}, Jian-Wei Pan^{1

2

3}

Affiliations

¹ Hefei National Research Center for Physical Sciences at the Microscale and School of Physical Sciences, University of Science and Technology of China, Hefei 230026, China.
² CAS Center for Excellence in Quantum Information and Quantum Physics, University of Science and Technology of China, Shanghai 201315, China.
³ Hefei National Laboratory, University of Science and Technology of China, Hefei 230088, China.
⁴ International Center for Quantum Materials, School of Physics, Peking University, Beijing 100871, China.
⁵ Wilczek Quantum Center, School of Physics and Astronomy, Shanghai Jiao Tong University, Shanghai 200240, China.
⁶ Center for Theoretical Physics, MIT, Cambridge, MA 02139.
⁷ T. D. Lee Institute, Shanghai Jiao Tong University, Shanghai 200240, China.
⁸ Department of Physics, Stockholm University, Stockholm SE-106 91, Sweden.
⁹ Department of Physics and Origins Project, Arizona State University, Tempe, AZ 25287.

Abstract

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 [Formula: see text], with edges [Formula: see text] being the two-body interactions between adjacent vertices [Formula: see text]. Thus, solving the IS problem is equivalent to finding all the computational basis ground states of [Formula: see text]. Very recently, non-Abelian adiabatic mixing (NAAM) has been proposed to address this task, exploiting an emergent non-Abelian gauge symmetry of [Formula: see text] [B. Wu, H. Yu, F. Wilczek, Phys. Rev. A 101, 012318 (2020)]. Here, we solve a representative IS problem [Formula: see text] 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.

Keywords: adiabatic mixing; independent sets; photonic quantum computer; quantum algorithm.

Grants and funding

742104/ERC_/European Research Council/International