(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.


1 Answer 1


No, the quantum version is not simpler

There are many ways to find the ground state of an arbitrary quantum system. Quantum Monte Carlo (QMC), Density Matrix Renormalization Group (DMRG), et. al., but if you want an exact solution, you need either some very clever analytical approach (only available for special cases), or you need to do exact diagonalization.

I'll write my answer in terms of the quantum $S=\frac{1}{2}$ Heisenberg model because I have more experience with that. Each site is a two-state quantum system, so the total Hilbert space is of size $2^N$. However, this is a quantum system, not an Ising model, so the ground state is a complex vector of size $2^N$. (There are some simplifications that probably reduce this number for the XY model, but it will still be exponential in $N$).

If you need the full solution then you have to diagonalize the $2^N \times 2^N$ Hamiltonian. That has computational cost proportional to $(2^N)^3$. In addition to being very computationally intensive to evaluate, even for very modest systems (such as a spin chain of length 20), even constructing these matrices becomes incredicbly computationally expensive, and it can be a challenge to even store them in memory. (A double-precision complex number takes up 8 bytes of memory, so the Hamiltonian for a L=16 chain would require 34 GB of memory).

Save time with symmetries

Most Hamiltonians have some obvious symmetries that can exploited to reduce the size of the matrix that must be diagonalized, such as total magnetization, translational symmetry, spin-inversion symmetry, reflection symmetry, etc. Implementing these can allow larger systems to be studied. These procedures are described in detail in Sandvik arXiv:1101.3281

Save time with Lanczos diagonalization

Lanczos diagonalization is an iterative technique to get the ground state and first few excited states from a Hamiltonian that is much faster and less memory intensive than full diagonalization. In practice, the ground state energy and eigenstate can usually be calculated to numerical precision (effectively exact), but it can't easily tell degenerate ground states apart. See Sandvik arXiv:1101.3281

  • 1
    $\begingroup$ While I appreciate your answer, I don't think it answers my question on how to solve generic classical spin models more easily than the quantum ones. $\endgroup$
    – Wouter
    Apr 14, 2021 at 11:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .