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.