14
$\begingroup$

It is well known that finding ground states for spin-glass systems (Ising, XY...) is NP-hard (at least as hard as the hardest NP-problems) so that they can be efficiently used to solve other NP problems like the Traveling Salesman Problem.

My question is: is the problem NP-complete? This seems to be what is claimed here. To my understanding, this would mean that apart from NP-hard, the problem is NP itself. But I don't know an obvious algorithm to check if a given solution is the true ground state in polynomial time? And actually, I think that a similar argument can be made for the traveling salesman problem.

Improve this question
$\endgroup$
1
  • 3
    $\begingroup$ I suggest to add the tag "spin-glasses" btw, as I think that it would be useful for future reference (but lack the reputation) $\endgroup$
    – Wouter
    Commented Apr 7, 2021 at 5:23

3 Answers 3

Reset to default
15
$\begingroup$

Background

Computational problems come in a variety of types, for example:

  • decision problem: given input $x$, output "YES" if $x$ belongs to a fixed set $L$ and output "NO" otherwise,
  • function problem: given input $x$, output a $y$ such that $(x, y)$ belongs to a fixed relation $R$,
  • optimization problem: given objective $f$ and constraints $g$, output $x$ that maximizes $f$ while satisfying $g$,
  • sampling problem: given a probability distribution $P$, output a sample $x\sim P$.

Together with the computational model and resource bounds, the type of relevant problems is a key ingredient in a definition of a computational complexity class.

Traveling Salesman Problem

The class NP is defined as a class of decision problems. The Traveling Salesman Problem formulated as the task of finding the shortest loop traversing all nodes in a graph exactly once is a function problem and thus - as you suspected in your question - does not belong to NP. However, TSP has a decision version which for a given graph and a threshold length $w$ asks whether there is a loop traversing all nodes in the graph exactly once and whose total length is less than $w$. This problem belongs to NP. The certificate is the path and it is easy to see that it can be checked in polynomial time on a deterministic Turing machine.

Spin glasses

Similarly, the problem of finding the ground state of a spin glass system is a function problem and hence not in NP. The problem has a decision variant which for a given spin glass system and an energy threshold $E$ asks whether there is an energy eigenstate with energy below $E$. Under certain assumptions about the Hamiltonian, this problem belongs to NP.

For example, in the absence of a transversal field, the Ising model is diagonal in a product basis and thus has a product eigenstate for every eigenvalue. Each product state admits a description of size polynomial in the number of sites. We can use such a state as a certificate that can be checked in polynomial time to prove that the model has a state with energy below the threshold $E$.

Terminology

The expression "TSP is NP-complete" is an imprecise shortcut for "the decision version of TSP is NP-complete". Leaving "decision version" implicit is generally acceptable because only decision problems may be meaningfully declared to be NP-complete.

That said, note that it does make sense to say that a computational problem $P$ which is not a decision problem is NP-hard. See Wikipedia for an explanation.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ Thank you! Is it still true that the optimization version of the spin glass problem gives the optimization of traveling salesman with only polynomial overhead if none of them are NP? $\endgroup$
    – Wouter
    Commented Apr 7, 2021 at 7:49
  • 1
    $\begingroup$ Another question: isn't the notion also meaningful for function problems? (e.g. prime factorization, permanents) $\endgroup$
    – Wouter
    Commented Apr 7, 2021 at 8:24
  • 1
    $\begingroup$ Re 1: Yes. The distinction of decision and function problems does not affect our ability to efficiently map from graph problems (such as TSP and Max-Cut) to the Ising model. Re 2: Yes, it is meaningful (even though imprecise) to talk about NP-completeness of such problems, because it is easy to convert them into corresponding decision problems when greater precision is needed. This happens e.g. when we begin to wonder what a suitable certificate looks like (as you did in your question). You may also be interested in the FNP complexity class. $\endgroup$
    – Adam Zalcman
    Commented Apr 7, 2021 at 17:01
  • $\begingroup$ Thank you! Why are you referring to the standard versions of the problems as ´function problems´ rather than ´opnimization problems´? To me, a function problem would be something like: "Given a fixed loop of the TSP, how long is it?" or, "What's the energy of this fixed state in the spin-glass?" which are not hard at all $\endgroup$
    – Wouter
    Commented Apr 8, 2021 at 1:23
  • 1
    $\begingroup$ Usual formulations of the TSP and ground state problems are indeed optimization problems. However, optimization problems can be thought of as function problems with extra structure. I called them "function problems" since I didn't need to involve any of the special structure that optimization problems have. Your other examples are also function problems. $\endgroup$
    – Adam Zalcman
    Commented Apr 8, 2021 at 2:09
3
$\begingroup$

Adam gave an excellent answer explaining that the "decision version" of the Ising model could be considered NP-complete, but the term doesn't make sense without that extra context.

I'll answer some of the other parts which I think were not yet addressed:

"But I don't know an obvious algorithm to check if a given solution is the true ground state in polynomial time?"

If you are given a solution to an arbitrary Ising model, for example: 001100110...01101 where 0 means spin-up and 1 means spin-down, there is no way in general to know that it is the true ground state, without checking all $2^n$ possible solutions, which means it can't be done in polynomial time with respect to the number of spins $n$. If you have a very specific Ising model, for example the one where there's no linear terms and all couplings between the spins are negative in strength, then you can find the ground state in polynomial time, but there's no way to verify that a solution is the true ground state in polynomial time in general.

Finally, since you talked about spin-glass systems in general (not just the Ising model, as you specifically mentioned the XY model which unlike the Ising model is not diagonal), I'll mention that the 2-local Hamiltonian problem is QMA-complete, which is the analog of NP-completeness, for when you have access to a quantum computer. Any Hamiltonian can be decomposed into a sum of products of spin-matrices, which describes a k-local spin-glass. It was proven that finding the ground state energy of the k-local Hamiltonian accurately is QMA-complete long before the more strong result in that paper I linked earlier, which shows that 2-local Hamiltonians are enough (you don't even need k-local interactions).

In fact, the 2D Ising model with transverse fields is universal, which was proved in this Science paper 5 years ago.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thanks for your answer. To be sure I understand you correctly: finding ground states cannot be verified in polynomial time on a quantum computer (as opposed to modeling time-evolution for the system) as I read once before. But you're saying that verification on a quantum computer (of the optimization version of the spin glass problem) can be done polynomially? $\endgroup$
    – Wouter
    Commented Apr 8, 2021 at 3:24
  • $\begingroup$ And this is irrespective of if the spin model is quantum or classical in nature? I think that the classical ones can be harder sometimes... maybe you would be interested also in taking a look at my question here physics.stackexchange.com/questions/621460/… $\endgroup$
    – Wouter
    Commented Apr 8, 2021 at 3:24
  • $\begingroup$ @Wouter I can't find where I said that anything can be done polynomially except for the submodular Ising problem which is a very specific example. $\endgroup$
    – user1271772 No more free time
    Commented Apr 8, 2021 at 3:36
  • $\begingroup$ I see that in the first sentence of my first comment, I wrote ´verified´when I meant ´computed´. But you were saying that all quadratic Hamiltonians become NP-like (QMA) problems (can be checked in polynomial time) on a quantum computer ? $\endgroup$
    – Wouter
    Commented Apr 8, 2021 at 3:45
  • $\begingroup$ "the 2-local Hamiltonian problem is QMA-complete, which is the analog of NP-completeness, for when you have access to a quantum computer" $\endgroup$
    – Wouter
    Commented Apr 8, 2021 at 3:49
0
$\begingroup$

I've found this Venn Diagram to be incredibly helpful in understanding the differences between P, NP, NP-Complete, and NP-Hard.

Venn Diagram

You're right that Traveling Salesman would not be considered NP-Complete. It's NP-Hard, but not in NP. The only way to verify a solution to Traveling Salesman (that we know of today) is to compare it to the optimal solution... and to get that optimal solution, you'd need to solve the problem. There are a whole bunch of NP-Hard problems that are too hard to be NP, including spin-glass.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ I think you've taken a non-standard definition of the TSP. We don't ask whether the tour is optimal, only whether the tour is of length less than some number. The decision version of the TSP asks whether there's a tour of all $n$ cities total length less than $k$, were $k$ is of order, say, $n^2$. The witness to the TSP is the tour itself, which only requires the ordered list of the $n$ cities. Because the witness is polynomial in $n$, the decision version of the TSP is in NP. Indeed you can do a binary search on $k$ to get better and better bounds on the optimal tour. $\endgroup$
    – Mark Spinelli
    Commented Sep 3, 2021 at 15:01

Not the answer you're looking for? Browse other questions tagged or ask your own question.