What is known about quatum algorithms for problems outside NP (eg NEXP-complete problems), both theoretically like upper & lower speedup bounds and various (im)possibility results, as well as concrete algorithms fro specific problems?

The reason I am asking is that we currently have processorrs with low 10's of qubits. NP problems over low 10s of classical bits can generally solved on classical computers. With non-NP problems we could have problems which are not classically tractable even in that range. This could be an opportunity to demonstrate practical quantum advantage on current hardware. This does not necessarily require the quantum algorithm to be generally tractable, only that it can solve smallish problems in acceptable time where classical algorithms can not.

The idea is to find problems that take considerable time on classical computers for instance sizes that are representable on current quantum processors. Finding quantum algorithms that are faster on those instances would be a form of quantum advantage even if the quantum algorithms were not necessarily superior asymptotically.

  • Are you looking for something mimicing Complexity Zoo, but with a narrower focus for only those really hard problems? – AHusain Dec 5 at 23:16
  • 2
    If I remember correctly, the evaluation of the jones polynomial at particular points has an efficient quantum algorithm, but is not inside NP. – DaftWullie Dec 6 at 6:36
  • @DaftWullie sounds like something Kuperberg did. I don't recall either, but that might help find the paper with that sort of result. – AHusain Dec 6 at 8:32
  • 3
    @DaftWullie Approximating the Jones polynomial at a certain set of points is BQP-complete, which makes it likely outside NP, see abstract of arxiv.org/abs/quant-ph/0511096 – Norbert Schuch Dec 6 at 9:38
  • 1
    @NorbertSchuch Fair point. I guess I was thinking potentially even outside BQP. Asymptotically quantum intractable problems which are still soluble in reasonable time for N=~30 by quantum algorithms but not classical ones. This question is not a theoretically significant question since it is relative to the current state of both quantum & classical technologies. It could still be interesting to have a program that shows a compelling advantage even at limited problem sizes, but maybe not. That is partly what I am asking. – Daniel Mahler Dec 7 at 23:38

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.