On the approximability of the `ground-state' problem for Ising spin glasses by quantum devices
A Bertoni, Gianpiero Cattaneo, D Oggioni · Journal of Physics A Mathematical and General · 1997
A lower bound result about the approximability of the energy function of Ising spin glasses in the quantum context is determined. The ground-state problem for the three-dimensional Ising spin glasses represented on two-level grids such that the vertical interactions are at most (where n is the number of spins set on the grid), is considered. We prove that, unless , there is a constant such that every quantum approximate polynomial-time algorithm finds a solution with absolute error greater than , with high probability, infinitely often.