The problem to find the ground state energy of an Ising-type Hamiltonian is known to be NP-hard . Recently, there have been two proposals in the community of quantum computing to tackle this problem. One is Yamamoto et al.'s coherent computing  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 . In this talk, I will explain my proof  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., ). I will also discuss the possibility of error correction to mitigate the difficulty although this requires further investigations.
 F. Barahona, J. Phys. A: Math. Gen. 15, 3241-3253 (1982).
 Y. Yamamoto, K. Takata, and S. Utsunomiya, New Gen. Comput. 30, 327-355 (2012).
 N. G. Dickson et al., Nat. Comm. 4, 1903 (2013).
 A. SaiToh, arXiv:1305.4440.
 B. Derrida, Phys. Rev. Lett. 45, 79-82 (1980); Phys. Rev. B 24, 2613-2626 (1981).