Problèmes sans avantage quantique connu

Je me demandais quelle est la liste des problèmes informatiques naturels actuels pour lesquels il n'y a aucun avantage de complexité connu à utiliser un ordinateur quantique.

Pour commencer, je pense que le calcul de la distance d'édition est celui pour lequel l'algorithme quantique connu le plus rapide semble être l'algorithme classique le plus rapide connu. Plus provisoirement, je suggérerais également le tri comme un autre problème pour lequel il n'y a pas d'accélération quantique connue (par rapport à l'algorithme de RAM de mots à coût unitaire connu le plus rapide).

Bien que je ne veuille pas fixer de restriction stricte, je suis particulièrement intéressé par les problèmes de NP et / ou les problèmes sans solution classique efficace connue.

Suite à une suggestion de Juan Bermejo Vega, voici quelques précisions supplémentaires. Je m'intéresse aux problèmes de NP pour lesquels il n'existe actuellement aucun avantage connu en termes de complexité du temps si vous utilisez un ordinateur quantique. $O$

Je ne me concentre pas sur les cas où nous pouvons prouver qu'il ne peut y avoir d'avantage, ni sur les accélérations exponentielles (c'est-à-dire que le polynôme conviendrait également). Jusqu'à présent, il semble que les deux seuls exemples soient ceux de ma question qui semblent très surprenants si c'est vraiment vrai.

ds.algorithms quantum-computing big-list Lembik
la source

Avantage de complexité car pas d'accélération dans le temps de fonctionnement global, ou que la classe de langue est fermée sous l'opération?

Ryan

@Ryan, je voulais dire pas d'accélération dans le temps de fonctionnement global. Merci pour la question.

Lembik

Tout ce qui est déjà polynomial. :-)

kasterma

@kasterma Je ne pense pas que ce soit correct. Il existe de nombreux problèmes de temps poly pour lesquels il existe actuellement une accélération quantique.

Lembik

Je suggérerais d'affiner cette question en précisant si (a) il s'agit «d'aucun avantage quantique prouvable » par rapport à «aucun avantage quantique connu »; si (b) la question concerne les accélérations exponentielles ou polynomiales (en ce qui concerne les problèmes non liés à P ou BPP); et si (c) d'autres types d'accélérations (par exemple, des accélérations logarithmiques sur des problèmes dans P ou BPP) sont autorisées.

Juan Bermejo Vega

Réponses:

Ce n'est pas dans NP, mais dans le tri basé sur la comparaison. La borne inférieure est une théorie de l'information. $\Omega(n \log n)$

Tyson Williams
la source

La théorie de l'information liée à l'être ne montre pas que les algorithmes quantiques ne peuvent pas la battre.

$\:$ (Considérez l'algorithme de Grover .)

$\;\;\;\;$

@RickyDemer Je ne sais pas trop ce que vous pensez. Les arguments théoriques de l'information ne tiennent aucun compte du modèle de calcul. Pour la recherche non structurée, l'entrée est un tableau

A

$A$

éléments et un élément cible

, et la sortie est un index

n

$n$

x

$x$

i

$i$ tel que

(qui, je suppose, existe pour la simplicité). Puisqu'un bit est appris avec chaque requête, la théorie de l'information dit que tout algorithme doit faire

requêtes

. Algorithme de Grover, à

A [i] = x

$A[i] = x$

\log n

$\log n$

requêtes, est loin d'être serrée à cette limite, encore moins qu'elle.

Θ (\sqrt{n})

$\Theta(\sqrt{n})$

Tyson Williams

Pour autant que je comprends, les arguments basés sur l'entropie / le comptage ne valent pas immédiatement pour les algorithmes quantiques, car ils concernent les distributions de probabilité et non les superpositions d'états quantiques. le

borne inférieure de recherche ordonnée

par exemple, était un article FOCS d'Ambainis, et la borne inférieure de tri semble également nécessiter du travailarxiv.org/abs/quant-ph/0102078. Il semble donc que votre affirmation soit correcte, mais pas aussi immédiate que vous le suggérez.

Ω (\log n)

$\Omega(\log n)$

Sasho Nikolov

@SashoNikolov Le problème de recherche non structurée, tel que je l'ai défini pour Ricky, n'a pas permis d'échouer. L'argument que j'ai avancé tient à ce problème. La borne inférieure donnée par Ambainis au FOCS (que je n'ai pas pu trouver) est probablement pour le problème plus général qui ne nécessite qu'un seul pour réussir avec une faible probabilité. Il en va de même pour le problème du tri et du papier arXiv auquel vous vous connectez.

Tyson Williams

@SashoNikolov: Je suis d'accord avec ce que vous avez écrit. Les limites théoriques de l'information de la forme Tyson décrivent où «un bit est appris avec une requête» ne vaut pas nécessairement pour le quantum. Considérons le problème de Bernstein-Vazirani, où la sortie du problème est

n

$n$ bits, et donc une machine classique doit faire

requêtes pour des raisons théoriques de l'information, mais un ordinateur quantique peut le faire avec 1 requête.

n

$n$

Robin Kothari

Récemment, cet article dans SODA 2018 montre un algorithme d'approximation à facteur constant pour éditer la distance dans des ordinateurs quantiques avec un temps sub-quadratique. Notez qu'aucun algorithme d'approximation à facteur constant pour la distance d'édition dans les ordinateurs classiques à temps sub-quadratique n'est encore connu. De plus, on pense qu'aucun tel algorithme n'existe dans les ordinateurs classiques.

Mohemnist
la source

Je ne pense pas que la dernière phrase soit correcte. Il n'y a pas de conséquences de complexité à une solution classique avec la même complexité.

Lembik

@Lembik Vous aviez raison. L' article a en quelque sorte dé-quantifié l'article précédent et a trouvé un algorithme d'approximation à facteur constant pour éditer la distance dans la complexité temporelle sous-quadratique. Voir cet article de blog pour plus d'informations.

Mohemnist