Math
Une question, posée une seule fois
Une boîte noire calcule f de n bits vers un bit, et on ne peut l'interroger que sur des entrées. Être certain que f est constante ou équilibrée coûte classiquement la moitié de la table plus un appel. Hadamard sur tout, UN appel dont la réponse est un signe, Hadamard de nouveau - et le résultat tout-à-zéro tranche. La table de vérité est cliquable ici, la promesse peut donc être brisée à la main : pour n'importe quelle table la réponse sort avec la probabilité (1 − 2k/N)². Et si la table se trouve être f(x) = s·x, le même appel unique rend s lui-même.
Ce qui se passe
Une boîte noire calcule une fonction f de n bits vers un bit. On promet qu'elle est soit constante soit équilibrée - la même réponse partout, ou une réponse sur exactement la moitié des entrées - et il faut dire laquelle. Classiquement il n'y a pas de raccourci : la moitié de la table peut s'accorder et l'entrée suivante tout gâcher, la certitude coûte donc N/2 + 1 appels. Neuf pour seize entrées, trente-trois pour soixante-quatre. Voici maintenant la version quantique, en trois lignes. Hadamard sur chaque qubit, pour que les N entrées soient posées d'un coup. Appelle l'oracle - qui ne répond pas par un bit mais par un SIGNE : un moins sur chaque entrée où f vaut un. Hadamard de nouveau sur chaque qubit. Mesure. Si tous les qubits lisent zéro, f était constante ; tout le reste veut dire équilibrée, et l'ensemble a coûté un appel. Ce module dépasse la démonstration parce que la table du haut est cliquable. Brise la promesse : retourne une case et f n'est ni constante ni équilibrée, et l'algorithme n'échoue pas - il se dégrade d'une quantité qu'on peut écrire. Pour N'IMPORTE quelle table, le résultat tout-à-zéro a la probabilité (1 − 2k/N)², où k compte les uns de la table. Constante, c'est k = 0 et cela donne un. Équilibrée, c'est k = N/2 et cela donne exactement zéro. Une case retournée à seize entrées donne 4/256, une exécution sur soixante-quatre, et le panneau annonce le nombre avant qu'on ne compte. Voilà ce que vaut une promesse dans un algorithme, en chiffres. Il y a une seconde chose cachée ici. Quand la table est linéaire - f(x) = s·x mod 2 pour une chaîne cachée s -, les mêmes trois étapes ne répondent pas seulement oui ou non : le résultat EST s, avec probabilité un, et tout autre résultat a exactement zéro. C'est Bernstein-Vazirani, et classiquement cela coûte n appels, un par bit. Demande une fois, lis toute la chaîne. Sous les deux faits, une formule : l'amplitude du résultat y est la transformée de Walsh-Hadamard de (−1)^f, et le module la recalcule directement depuis la table pour tenir les deux ensemble.
Équations du module
Équations les trois étapes : H sur chaque qubit ; un appel à l'oracle sous forme de signe, |x> -> (−1)^f(x) |x> ; H de nouveau sur chaque qubit amplitude du résultat y : (1/N) somme sur x de (−1)^(f(x) + x·y) - la transformée de Walsh-Hadamard de (−1)^f P(que des zéros) = (1 − 2k/N)² où k est le nombre de uns que contient la table de vérité - EXACTEMENT, pour n'importe quelle table constante (k = 0 ou N) : 1 ; équilibrée (k = N/2) : 0 ; une case d'une table équilibrée inversée : 4/N² = 1/64 pour N = 16 coût classique pour être CERTAIN : N/2 + 1 appels (3, 5, 9, 17, 33 pour n = 2…6) contre 1 table linéaire f(x) = s·x mod 2 (Bernstein-Vazirani) : le résultat EST s, probabilité 1, tout autre résultat exactement 0 ; coût classique n appels, un par bit f = 1 partout donne exactement les mêmes probabilités que f = 0 partout - la différence est un signe global, et un signe global n'est pas mesurable compté, 2000 exécutions à n = 4 : constante, 2000 sur 2000 sur la sortie de zéros ; s = 11 caché, 2000 sur 2000 sur 11 ; équilibrée, 0 sur la sortie de zéros ; une case inversée, 30 (exact 31.25)
