7
$\begingroup$

Similar to the class of classical NP-intermediate problems (e.g. Graph Isomorphism), is there any "QMA-intermediate" problem known, that is in QMA but not known to be QMA-complete? Has this been studied systematically before?

$\endgroup$
4
  • 3
    $\begingroup$ And I suppose you want that the problem is not known to be in NP (or BQP, of course). $\endgroup$ Jul 25, 2014 at 14:50
  • $\begingroup$ Yes, of course. Thanks for pointing that out. $\endgroup$ Jul 25, 2014 at 15:18
  • 2
    $\begingroup$ Everything in QMA${}_1$, UniqueQMA, QCMA, etc. Pretty much any problem in any subclass of QMA. Perhaps you could be more specific about which subclasses of QMA you wish to exclude? (Such as BQP and NP.) $\endgroup$ Jul 26, 2014 at 3:52
  • 1
    $\begingroup$ Indeed! I should have thought of these well known restrictions on QMA immediately! Somehow I was thinking more in terms of concrete problems, but of course you're right. You may want to put this as an answer. $\endgroup$ Jul 26, 2014 at 6:42

1 Answer 1

9
$\begingroup$

An example would be the computation of ground state energy of the Ising model with transverse magnetic fields, as described by [Cubitt+Montenaro-2013]. From the abstract:

In this work we characterise the complexity of [the calculation of ground-state energies of 2-body Hamiltonians on qubits with terms restricted to some fixed set S]. Depending on the subset S, the problem falls into one of the following categories: in P; NP-complete; polynomial-time equivalent to the Ising model with transverse magnetic fields; or QMA-complete. The third of these classes contains NP and is contained within StoqMA.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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