(Note: an earlier version of this question had been asked on Phys.SE before)
It is known that finding the ground state of classical spin glasses is NP-hard: it will take (at least) an exponential amount of effort with respect to system size $N$. But not all kinds of exponentially hard are the same, of course.
Now, take the XY-model for example, which has both a quantum and a classical version. For the quantum version, the Hilbert size is $2^N$ (each site is described by 2x2 Pauli matrices) and because quantum mechanics is linear, the Hamiltonian can be exactly diagonalized to get the (in general, entangled) ground state.
For the classical XY this construction cannot be made: there is one continuous variable $\theta$. With discretisation, it has $M_\theta$ values to be considered at every size, yielding a complexity of $M_\theta^N$ when one wants to try out all the possibilities?
Does this mean that the classical XY model is more complex than the quantum one?
Of course, there are monte carlo techniques but they are probabilistic and rely on careful tuning of the temperature; which is much more clumsy than the exact diagonalization of the quantum case.