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?
$\begingroup$
$\endgroup$
4
-
3$\begingroup$ And I suppose you want that the problem is not known to be in NP (or BQP, of course). $\endgroup$– Alessandro CosentinoJul 25, 2014 at 14:50
-
$\begingroup$ Yes, of course. Thanks for pointing that out. $\endgroup$– Martin SchwarzJul 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$– Robin KothariJul 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$– Martin SchwarzJul 26, 2014 at 6:42
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
answered Jul 25, 2014 at 15:59