Modèles de calcul strictement entre classique et quantique en termes de complexité de requête

Il est bien connu que les ordinateurs quantiques sont strictement plus puissants que leurs homologues classiques en termes de complexité des requêtes .

Existe-t-il d'autres modèles (naturels ou artificiels) qui se situent strictement entre le quantique et le classique en termes de complexité des requêtes?

La séparation peut être activée

• problèmes spécifiques: le modèle X calcule la fonction avec strictement plus de requêtes que quantique, mais moins de requêtes que la borne inférieure en classique, ou$f$
• différents problèmes: le modèle X calcule la fonction avec strictement plus de requêtes que quantique, mais calcule la fonction f 2 avec moins de requêtes que la classique.$f_1$$f_2$

Dans les deux cas, nous voulons que chaque fonction ait Q 2 ( f ) ≤ X ( f ) ≤ R 2 ( f ) pour éviter les exemples difficiles à comparer au quantum (comme la complexité du certificat des requêtes non déterministes). Ici , Q 2 ( f ) (et R 2 ( f ) ) est le double face une / 3 quantum -error (et classique à répartition aléatoire) la complexité de la requête et les inégalités sont à des facteurs constants.$f$$Q_2(f) \leq X(f) \leq R_2(f)$$Q_2(f)$$R_2(f)$$1/3$

Un moyen facile de trouver un tel modèle est de créer d'abord un modèle restreint de calcul quantique qui peut encore faire quelque chose de non classique, puis de lui donner gratuitement le calcul classique.

Un exemple de cette stratégie est le modèle de qubit propre (avec une machine BPP). Quelques références: sur la puissance d'un bit d'information quantique , le calcul avec des unitaires et un polynôme Pure Qubit et l' estimation de Jones est un problème complet pour un qubit propre .

Un autre exemple serait d'avoir un circuit quantique de profondeur logarithmique (ou profondeur polylog) avec accès à un ordinateur classique. Cela donnera quelque chose comme .$BPP^{BQNC}$

$X(f)\leq D(f)$$R_2(f)$

Peut-être l'exemple le plus clair de ce type de modèles informatiques est DQC1 expliqué par @RobinKothari dans sa réponse. Voir les références dans sa réponse pour une bonne introduction au modèle.

Aussi, assez récemment, il y avait un bel article dans le magazine Nature sur Quantum Discord. Quantum Discord est une mesure théorique de l'information des corrélations non classiques, généralisant l'intrication. Voici le lien . Vous verrez là qu'il existe des exemples de calculs où l'intrication ne joue pas un rôle fondamental, c'est-à-dire que d'autres corrélations non classiques sont celles qui prennent en charge l'accélération du calcul. Cela se produit dans DQC1 pour calculer la trace d'une matrice (voir l'article de Datta, Shaji et Caves ). Ce qui est intéressant dans cet article, c'est qu'il ouvre la question sur les «algorithmes basés sur Discord quantique», c'est-à-dire les algorithmes où vous n'avez pas besoin d'enchevêtrement pour l'accélération quantique. C'est quelque chose entre le calcul quantique complet et le classique.

Un autre modèle qui tombe peut-être dans cette catégorie (entre le plein quantique et le classique) est le modèle optique linéaire d'Arkhipov et Aaronson. Voir cette question pour une belle explication.

Je ne sais pas où ces modèles se situent en termes de complexité des requêtes, mais cela pourrait être un bon point de départ.