9
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ Are you looking for something mimicing Complexity Zoo, but with a narrower focus for only those really hard problems? $\endgroup$
    – AHusain
    Dec 5, 2018 at 23:16
  • 3
    $\begingroup$ If I remember correctly, the evaluation of the jones polynomial at particular points has an efficient quantum algorithm, but is not inside NP. $\endgroup$
    – DaftWullie
    Dec 6, 2018 at 6:36
  • 4
    $\begingroup$ @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 $\endgroup$
    – Norbert Schuch
    Dec 6, 2018 at 9:38
  • 1
    $\begingroup$ @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. $\endgroup$
    – Norbert Schuch
    Dec 6, 2018 at 9:40
  • 1
    $\begingroup$ @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. $\endgroup$
    – Daniel Mahler
    Dec 7, 2018 at 23:38

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.