(英) |
When maximum independent set problem, which is known to be NP hard, is solved using quantum adiabatic optimization, it is suggested from purterbative arguments that the minimum energy gap between the ground state and the first excited state is expanded with increasing a non-uniform transverse magnetic field in reference to the true solution[1]. In this research, we investigated if the picture still holds for non-purterbative regime, using numerical exact diagonalization. While according to the PCP theorem the maximum independent set problem is always hard to approximate, the minimum vertex cover problem, which is the dual problem, allows O(N) approximation. We investigated how this difference in hardness of approximation affects the tolerance of error in constructing the non-uniform transverse field. |