Algoritmos quânticos para problemas fora do NP

O que se sabe sobre algoritmos de quatum para problemas fora do NP (por exemplo, problemas completos no NEXP), teoricamente como limites de velocidade superior e inferior e vários (im) resultados de possibilidade, bem como algoritmos concretos para problemas específicos?

A razão pela qual estou perguntando é que atualmente temos processorrs com baixos 10 de qubits. Problemas de NP acima de 10s de bits clássicos geralmente podem ser resolvidos em computadores clássicos. Com problemas que não são NP, podemos ter problemas que não são classicamente tratáveis, mesmo nessa faixa. Essa pode ser uma oportunidade para demonstrar vantagem quântica prática no hardware atual. Isso não requer necessariamente que o algoritmo quântico seja geralmente tratável, apenas que ele possa resolver problemas pequenos em tempo aceitável, onde algoritmos clássicos não podem.

A idéia é encontrar problemas que levam um tempo considerável em computadores clássicos, por exemplo, tamanhos que são representáveis ​​nos processadores quânticos atuais. Encontrar algoritmos quânticos mais rápidos nessas instâncias seria uma forma de vantagem quântica, mesmo que os algoritmos quânticos não fossem necessariamente superiores assintoticamente superiores.

$1$$\Omega(\sqrt N /\log N)$

$\mathsf{BQP}\subseteq\mathsf{PSPACE}$