{c}
{wiki}

This is the most interesting class of problems for <BQP> as we haven't proven that they are neither:
* <P (complexity)>: would be boring on quantum computer
* <NP-complete>: would likely be impossible on a quantum computer

Big list: https://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/460#460


NP-intermediate

{c}
{wiki}

<P (complexity)> for <quantum computing>!

Heck, we know nothing about this class yet related to non quantum classes!
* conjectured not to intersect with <NP-complete>, because if it were, all NP-complete problems could be solved efficiently on quantum computers, and none has been found so far as of 2020.
* conjectured to be larger than <P (complexity)>, but we don't have a single algorithm provenly there:
  * it is believed that the NP complete ones can't be solved
  * if they were neither NP-complete nor P, it would imply <p versus NP problem>[P != NP]
* we just don't know if it is even contained inside <NP (complexity)>!


Ciro Santilli @cirosantilli 37

 Incoming links: BQP