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.

[1] F. Barahona, J. Phys. A: Math. Gen. 15, 3241-3253 (1982).
[2] Y. Yamamoto, K. Takata, and S. Utsunomiya, New Gen. Comput. 30, 327-355 (2012).
[3] N. G. Dickson et al., Nat. Comm. 4, 1903 (2013).
[4] A. SaiToh, arXiv:1305.4440.
[5] B. Derrida, Phys. Rev. Lett. 45, 79-82 (1980); Phys. Rev. B 24, 2613-2626 (1981).