9

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.

Daniel Mahler
  • 331
  • 1
  • 5
  • 2
    Are you looking for something mimicing Complexity Zoo, but with a narrower focus for only those really hard problems? – AHusain Dec 05 '18 at 23:16
  • 3
    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 06 '18 at 06: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 06 '18 at 08:32
  • 5
    @DaftWullie Approximating the Jones polynomial at a certain set of points is BQP-complete, which makes it likely outside NP, see abstract of https://arxiv.org/abs/quant-ph/0511096 – Norbert Schuch Dec 06 '18 at 09:38
  • 1
    @DanielMahler Quantum computing can be simulated in PSPACE (more precisely, in PP). So NEXP is out of reach. In any case, low 10s (<~30) is still classically simulatable. – Norbert Schuch Dec 06 '18 at 09:40
  • @DanielMahler Basically, you are asking "Tell me everything which is known about BQP", which is really to broad. Can you narrow it down? – Norbert Schuch Dec 07 '18 at 22:44
  • 2
    @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 07 '18 at 23:38

1 Answers1

3

Forrelation might be such a problem. The question is "Is a first Boolean function highly correlated with the Fourier transform of a second Boolean function?" This is solved with $1$ quantum query but Aaronson and Ambainis showed that classically one needs $\Omega(\sqrt N /\log N)$ random queries.

See also the Quanta magazine article- by the work of Raz and Tal the problem is likely to be out of the polynomial hierarchy. Considering Norbert Schuch's comment about $\mathsf{BQP}\subseteq\mathsf{PSPACE}$, this may be about as good a separation as can be expected.

Mark Spinelli
  • 11,947
  • 2
  • 19
  • 65