# How to tell if the ground states of two Hamiltonians are solutions of the same optimization problem?

Let's say, that we have an optimization problem in the form:

$$\min_x f(x) \\ g_i(x) \leq 0, i = 1, ..., m \\ h_j(x) = 0, j = 1, ..., p,$$

where $$f(x)$$ is an objective function, $$g_i(x)$$ are inequality constraints and $$h_j(x)$$ are equality constraints.

In adiabatic quantum computing the solution of this problem can be expressed as the ground state of some Hamiltonian. But I think, that it is possible to construct two or more Hamiltonians, whose ground states are solutions to the same problem.

Summarizing, how to tell, if two Hamiltonians represent the same optimization problem (or rather their ground states are solutions to the same problem)?

• I'm not positive on this but I'd assume this is a very hard thing to do in general. It may also be ill defined as there is a decoding step to go from the ground state to the solution. – bRost03 Jun 10 '19 at 3:40

Short Answer: It is potentially hard (as bRost03 indicates in the comments). To be precise, coNP-hard.

We can reduce any such CSP to a boolean formula. So what we're looking at in the case of asking whether the satisfying set of two CSPs are the same is whether a boolean formula of the form $$\varphi_1(x) \iff \varphi_2(x)$$ is a tautology, which is to say, whether that biconditional is true for all $$x$$, for some boolean formulae $$\varphi_1$$ and $$\varphi_2$$ provided as input. This makes it a special case of " TAUTOLOGY ", the decision problem of whether a logical formula is a tautology.
The problem TAUTOLOGY is in coNP — in fact, it is coNP complete, because it is in effect the complementary problem to the NP compete problem SATISFIABILITY. This shows that the special case of determining whether the satisfying solution sets of two CSPs are equivalent is no harder than coNP. But because we can test whether $$\varphi_1$$ is itself a tautology by setting $$\varphi_2$$ to the boolean formula 'TRUE', this special case is as hard as TAUTOLOGY is itself, so it is coNP hard.
• By saying "If the CSP is perfectly solvable, the ground-space is spanned by (standard basis states which encode) the assignments which satisfy the constraints" do you mean a basis e.g. in a form $|0\rangle = (1, 0)^T, |1\rangle = (0, 1)^T$, and some variables standing in front of them? It is extremely simple example for simplicity. If so, could you provide some simple example? – brzepkowski Jun 14 '19 at 10:05
• A simple (and also easy) example: $H(t) =- (1\! - \! t) (X_1 \! +\! X_2\! + \! X_3) - t(Z_1 Z_2 \! + \! Z_1 Z_3 \! +\! Z_2 Z_3)$, so that $H(1) = - Z_1 Z_2 - Z_1 Z_3 - Z_2 Z_3$, with ground-space spanned by $\lvert 000 \rangle$ and $\lvert 111\rangle$. – Niel de Beaudrap Jun 14 '19 at 20:50