Quels types d'algorithmes sont plus rapides avec un ordinateur quantique?

Je suis un étudiant CS débutant et j'apprends des algorithmes. J'ai entendu dire que même avec des ordinateurs quantiques, les algorithmes de tri généraux ne peuvent jamais avoir un temps meilleur que . Cependant, je sais également que les algorithmes de factorisation seraient beaucoup plus rapides. En termes généraux, quel type d'algorithmes deviendrait sensiblement plus rapide avec les ordinateurs quantiques? $n\log n$

algorithms quantum-computing hgund
la source

Je vous suggère de reformuler votre question. Vous demandez vraiment quels problèmes peuvent être résolus plus rapidement avec les ordinateurs quantiques.

Yuval Filmus

Scott Aaronson (le gourou de l'informatique quantique) a (deux versions de a) parler exactement de ce sujet, intitulé * Quand exactement les ordinateurs quantiques fournissent-ils une accélération? ". Vous pouvez le trouver (ou plutôt eux) ici: scottaaronson.com/ parle .

Yuval Filmus

Pour autant que je sache, aucun . Nous avons besoin de nouveaux algorithmes. (cf premier commentaire de Yuval.)

Raphael

il n'est pas réellement prouvé que l'affacturage est plus rapide, seulement conjecturé, etc., c'est une question ouverte P? = BQP etc

vzn

Étroitement liés: Pourquoi et comment est un ordinateur quantique plus rapide qu'un ordinateur ordinaire?

Gilles 'SO- arrête d'être méchant'

Réponses:

$k$ $a^{k} = b$ $a$ $b$
L'algorithme de Grover donne une accélération quadratique dans la recherche de listes non triées (qui peuvent être utilisées comme accélération pour de nombreux algorithmes).
La simulation de systèmes quantiques est également en BQP, mais exponentiellement plus lente sur une MT classique.
La résolution de l'équation de Pell (pas vraiment une équation) est en BQP, une autre accélération exponentielle.
Il y a aussi un certain nombre d'autres problèmes, plus obscurs, qui sont dans BQP, mais ne semblent pas être dans P. Wocjan et Zhang donnent un bon point de départ pour les déterrer.

Luke Mathieson
la source