Math
Eine Frage, einmal gestellt
Eine Blackbox berechnet f von n Bits auf ein Bit, und fragen darf man sie nur nach Eingaben. Sicher zu wissen, ob f konstant oder balanciert ist, kostet klassisch die halbe Tabelle plus einen Aufruf. Hadamard auf alles, EIN Aufruf mit der Antwort als Vorzeichen, wieder Hadamard - und der Nur-Nullen-Ausgang entscheidet. Die Wahrheitstabelle hier ist anklickbar, das Versprechen lässt sich also von Hand brechen: für jede Tabelle kommt die Antwort mit Wahrscheinlichkeit (1 − 2k/N)². Und ist die Tabelle f(x) = s·x, liefert derselbe eine Aufruf s selbst.
Was passiert
Eine Blackbox berechnet irgendeine Funktion f von n Bits auf ein Bit. Versprochen ist, dass sie entweder konstant oder balanciert ist - überall dieselbe Antwort, oder eine Antwort auf genau der Hälfte der Eingaben -, und man soll sagen, welches. Klassisch gibt es keine Abkürzung: die halbe Tabelle kann übereinstimmen und der nächste Eintrag es doch verderben, Sicherheit kostet also N/2 + 1 Aufrufe. Neun bei sechzehn Eingaben, dreiunddreißig bei vierundsechzig. Nun die Quantenfassung, und sie hat drei Zeilen. Hadamard auf jedes Qubit, damit alle N Eingaben auf einmal gefragt sind. Ruf das Orakel - das nicht mit einem Bit antwortet, sondern mit einem VORZEICHEN: ein Minus auf jede Eingabe, wo f eins ist. Hadamard auf jedes Qubit. Messen. Lesen alle Qubits null, war f konstant; alles andere heißt balanciert, und das Ganze kostete einen Aufruf. Mehr als eine Vorführung wird dieses Modul dadurch, dass die Tabelle oben anklickbar ist. Brich das Versprechen: dreh eine Zelle um, und f ist weder konstant noch balanciert - der Algorithmus versagt nicht, er verschlechtert sich um einen Betrag, den man hinschreiben kann. Für JEDE Tabelle hat der Nur-Nullen-Ausgang die Wahrscheinlichkeit (1 − 2k/N)², wobei k zählt, wie viele Einsen die Tabelle hat. Konstant ist k = 0 und gibt eins. Balanciert ist k = N/2 und gibt exakt null. Eine umgedrehte Zelle bei sechzehn Eingaben gibt 4/256, ein Lauf von vierundsechzig, und die Tafel nennt die Zahl, bevor man zählt. So viel ist ein Versprechen in einem Algorithmus wert, in Ziffern. Hier versteckt sich noch etwas. Ist die Tabelle linear - f(x) = s·x mod 2 für eine verborgene Zeichenkette s -, dann antworten dieselben drei Schritte nicht bloß ja oder nein: der Ausgang IST s, mit Wahrscheinlichkeit eins, und jeder andere Ausgang hat exakt null. Das ist Bernstein-Vazirani, und klassisch kostet es n Aufrufe, einen je Bit. Einmal fragen, die ganze Kette lesen. Unter beidem liegt eine Formel: die Amplitude des Ausgangs y ist die Walsh-Hadamard-Transformierte von (−1)^f, und das Modul rechnet sie ein zweites Mal direkt aus der Tabelle, damit sich die beiden halten lassen.
Gleichungen des Moduls
Gleichungen die drei Schritte: H auf jedes Qubit; ein Orakelaufruf als Vorzeichen, |x> -> (−1)^f(x) |x>; H wieder auf jedes Qubit Amplitude des Ergebnisses y: (1/N) Summe über x von (−1)^(f(x) + x·y) - die Walsh-Hadamard-Transformation von (−1)^f P(alle Nullen) = (1 − 2k/N)² wobei k die Anzahl der Einsen in der Wahrheitstabelle ist - EXAKT, für jede beliebige Tabelle konstant (k = 0 oder N): 1; balanciert (k = N/2): 0; eine Zelle einer balancierten Tabelle umgekehrt: 4/N² = 1/64 bei N = 16 klassischer Aufwand, um SICHER zu sein: N/2 + 1 Aufrufe (3, 5, 9, 17, 33 für n = 2…6) gegenüber 1 lineare Tabelle f(x) = s·x mod 2 (Bernstein-Vazirani): das Ergebnis IST s, Wahrscheinlichkeit 1, jedes andere Ergebnis genau 0; klassischer Aufwand n Aufrufe, einer pro Bit f = 1 überall liefert genau dieselben Wahrscheinlichkeiten wie f = 0 überall - der Unterschied ist ein globales Vorzeichen, und ein globales Vorzeichen ist nicht messbar gezählt, 2000 Läufe bei n = 4: konstant 2000 von 2000 bei lauter Nullen; verborgenes s = 11, 2000 von 2000 bei 11; balanciert 0 bei lauter Nullen; eine Zelle umgekehrt 30 (exakt 31.25)
