Journal
PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA
Volume 120, Issue 22, Pages -Publisher
NATL ACAD SCIENCES
DOI: 10.1073/pnas.2212323120
Keywords
quantum algorithm; independent sets; adiabatic mixing; photonic quantum computer
Categories
Ask authors/readers for more resources
This study employs non-Abelian adiabatic mixing to tackle the independent set problem and successfully identifies the maximum independent set by simulating a linear optical quantum network. The experiment showcases the high probability of finding nontrivial independent sets, thereby demonstrating the potential advantage of non-Abelian adiabatic mixing for solving equivalent problems.
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 RG(V,E) IS , 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 RG(V,E) IS. Very recently, non-Abelian adiabatic mixing (NAAM) has been proposed to address this task, exploiting an emergent non-Abelian gauge symmetry of RG(V,E) IS [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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available