<p>An example would be the computation of ground state energy of the Ising model with transverse magnetic fields, as described by [<a href="http://arxiv.org/abs/1311.3161">Cubitt+Montenaro-2013</a>]. From the abstract:</p>

<blockquote>
  <p>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 <strong>P</strong>; <strong>NP</strong>-complete; polynomial-time equivalent to the Ising model with transverse magnetic fields; or <strong>QMA</strong>-complete. The third of these classes contains <strong>NP</strong> and is contained within <strong>StoqMA</strong>.</p>
</blockquote>

CC BY-SA 3.0
2014-07-25T15:59:15.240Z
2014-07-25T15:59:15.240Z
Niel de Beaudrap
<p>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?</p>

CC BY-SA 3.0
2014-07-25T14:50:28.630Z
And I suppose you want that the problem is not known to be in NP (or BQP, of course).
Alessandro Cosentino
CC BY-SA 3.0
2014-07-25T15:18:16.960Z
Yes, of course. Thanks for pointing that out.
Martin Schwarz
CC BY-SA 3.0
2014-07-26T03:52:43.700Z
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.)
Robin Kothari
CC BY-SA 3.0
2014-07-26T06:42:58.123Z
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.
Martin Schwarz
<quantum-computing><np-intermediate>
Is any QMA-intermediate problem known?
Martin Schwarz
# Is any QMA-intermediate problem known?

(Asked by: username_0 on 2014-07-25)

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?

**Tags:** quantum-computing, np-intermediate
> **Comments:**
> **username_1**: And I suppose you want that the problem is not known to be in NP (or BQP, of course).  
> **username_0**: Yes, of course. Thanks for pointing that out.  
> **username_2**: 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.)  
> **username_0**: 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.  

---

## 1 answers

### Answer by username_3 on 2014-07-25. Score: 10

An example would be the computation of ground state energy of the Ising model with transverse magnetic fields, as described by [[Cubitt+Montenaro-2013](http://arxiv.org/abs/1311.3161)]. 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**.


---

