Solving independent set problems with photonic quantum circuits

Yin, Xu-Fei (author)

Yao, Xing-Can (author)

Wu, Biao (author)

Fei, Yue-Yang (author)

Mao, Yingqiu (author)

Zhang, Rui (author)

Liu, Li-Zheng (author)

Wang, Zhenduo (author)

Li, Li (author)

Liu, Nai-Le (author)

Wilczek, Frank, 1951- (author): Stockholms universitet,Fysikum,Shanghai Jiao Tong University, China; MIT, USA; Arizona State University, USA

Chen, Yu-Ao (author)

Pan, Jian-Wei (author)

(creator_code:org_t)

2023
2023
English.
In: Proceedings of the National Academy of Sciences of the United States of America. - 0027-8424 .- 1091-6490. ; 120:22

Related links:: https://doi.org/10.1...; show more...; https://urn.kb.se/re...; https://doi.org/10.1...; show less...

Abstract Subject headings

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

By the author/editor: Yin, Xu-Fei; Yao, Xing-Can; Wu, Biao; Fei, Yue-Yang; Mao, Yingqiu; Zhang, Rui; show more...; Liu, Li-Zheng; Wang, Zhenduo; Li, Li; Liu, Nai-Le; Wilczek, Frank, ...; Chen, Yu-Ao; Pan, Jian-Wei; show less...

About the subject

NATURAL SCIENCES: NATURAL SCIENCES; and Computer and Inf ...; and Computer Science ...

Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.