Abstract

The problem to find the ground state energy of an Ising-type Hamiltonian is known to be NP-hard [1]. Recently, there have been two proposals in the community of quantum computing to tackle this problem. One is Yamamoto et al.'s coherent computing [2] that uses an injection-locked laser network; the other is the annealing machine using the commercial flux-qubit array cells produced by D-Wave System Inc [3]. In this talk, I will explain my proof [4] of the existence of hard instances of the problem on the physical systems, which is based on known statistical properties of the problem (e.g., [5]). I will also discuss the possibility of error correction to mitigate the difficulty although this requires further investigations.