Quantum Hamiltonian algorithms for maximum independent sets

Abstract

ABSTRACT We compare two quantum Hamiltonian algorithms that address the maximum independent set problem: one based on the emergent non-Abelian gauge matrix in adiabatic evolution of an energetically isolated manifold of states; the other based on designed application of single-qubit operations. We demonstrate that they are mathematically equivalent in the sense that one is the other’s interaction picture. Despite their mathematical equivalence, our numerical simulations show significant differences between them in performance, which is explained analytically. Intriguingly, this equivalence unveils that the PXP model, recently prominent in quantum dynamics research, can be viewed as quantum diffusion over the median graph of all independent sets governed by the non-Abelian gauge matrix.