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)?

  • 1
    $\begingroup$ 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. $\endgroup$ – bRost03 Jun 10 '19 at 3:40

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

Longer Answer:

In adiabatic quantum computation, the ground-space of the final Hamiltonian is typically determined by the optimum solution to some constraint satisfaction problem (CSP). If the CSP is perfectly solvable, the ground-space is spanned by (standard basis states which encode) the assignments which satisfy the constraints. If the CSP is not perfectly satisfiable, the ground-space is spanned by all assignments which are closest to being satisfying. In this case, your question amounts just to a question of finding out when the set of satisfying assignments — or the set of optimal assignments — of a CSP are the same.

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.

The more general problem of equivalence of optimal solutions contains this problem as a subcase, so it is also coNP hard.

| improve this answer | |
  • $\begingroup$ 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? $\endgroup$ – brzepkowski Jun 14 '19 at 10:05
  • $\begingroup$ 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$. $\endgroup$ – Niel de Beaudrap Jun 14 '19 at 20:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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