Y a-t-il des algorithmes quantiques améliorés par rapport au SAT classique?

29

Les algorithmes classiques peuvent résoudre le 3-SAT en temps (randomisé) ou 1,3303 n temps (déterministe). (Référence: Best Upper Bounds on SAT )1.3071n1.3303n

À titre de comparaison, l'utilisation de l'algorithme de Grover sur un ordinateur quantique rechercherait et fournirait une solution en , randomisée. (Cela peut encore nécessiter une certaine connaissance du nombre de solutions possibles ou non, je ne suis pas sûr de la nécessité de ces limites.) C'est clairement nettement pire. Existe-t-il des algorithmes quantiques qui font mieux que les meilleurs algorithmes classiques (ou du moins - presque aussi bons?)1.414n

Bien sûr, les algorithmes classiques pourraient être utilisés sur un ordinateur quantique en supposant un espace de travail suffisant; Je m'interroge sur les algorithmes intrinsèquement quantiques.

Alex Meiburg
la source

Réponses:

21

Je pense que l'on peut obtenir une limite supérieure non triviale de l'informatique quantique en accélérant les algorithmes randomisés de Schöning pour 3-SAT. L'algorithme de Schöning fonctionne en temps et en utilisant des techniques d'amplification d'amplitude standards , on peut obtenir un algorithme quantique qui fonctionne dans le temps ( 2 / (4/3)nce qui est nettement plus rapide que l'algorithme classique.(2/3)n=1.15n

wwjohnsmith1
la source
1.32065n1.1492n
Vous pourriez également aimer cet article: digitalcommons.utep.edu/cgi/…
Martin Schwarz
30

En effet, comme l'a dit wwjohnsmith1, vous pouvez obtenir une accélération de racine carrée sur l'algorithme de Schöning pour 3-SAT, mais aussi plus généralement pour l'algorithme de Schöning pour k-SAT. En fait, de nombreux algorithmes randomisés pour k-SAT peuvent être implémentés quadratiques plus rapidement sur un ordinateur quantique.

O(T(n)poly(n))T(n)n1/T(n)O(T(n))O(T(n)poly(n))

O(T(n))1/TO(T)O(T(n)poly(n))

Robin Kothari
la source