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?

  • 3
    $\begingroup$ And I suppose you want that the problem is not known to be in NP (or BQP, of course). $\endgroup$ – Alessandro Cosentino Jul 25 '14 at 14:50
  • $\begingroup$ Yes, of course. Thanks for pointing that out. $\endgroup$ – Martin Schwarz Jul 25 '14 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$ – Robin Kothari Jul 26 '14 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$ – Martin Schwarz Jul 26 '14 at 6:42

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.


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.