Vereinfachte Erklärung der Shor / QFT-Transformation als Reißzwecke

9

Als Nicht-Mathematiker / Software-Programmierer versuche ich zu verstehen, wie QFT (Quantum Fourier Transformation) funktioniert.

Folgen Sie diesem YouTube-Video: https://www.youtube.com/watch?v=wUwZZaI5u0c

Und dieser Blogpost: https://www.scottaaronson.com/blog/?p=208

Ich habe ein grundlegendes Verständnis dafür, wie Sie die Periode mithilfe von Interferenzen berechnen / konstruieren können. Aber als ich versuchte, dies einem Kollegen zu erklären, stieß ich auf ein Problem. Ich habe die folgenden Beispiele verwendet, N = 15, a = 7, also ist der Zeitraum, den ich finden muss, r = 4.

Das Muster ist: 7, 4, 13, 1, 7, 4, 13, 1, 7, 4, 13, 1 (etc)

Wenn ich mir das Rad (wie im YouTube-Video) oder eine Uhr (wie den Blogpost) vorstelle, kann ich sehen, dass der Kreis mit 4 Punkten / Uhr mit 4 Stunden ein konstruktives Muster erzeugt und die anderen nicht.

Aber was passiert mit einem Kreis mit 2 Punkten oder einer Uhr mit 2 Stunden, die das gleiche Größen- / Konstruktionsmuster wie 4 haben? Es schleift doppelt so schnell, aber ansonsten das gleiche Ergebnis?

Wie geht die QFT damit um?

(Bonus: Können Sie es ohne zu komplizierte Mathematik in Laienbegriffen erklären?)

Roy van Rijn
quelle

Antworten:

7

Lassen Sie mich versuchen, diese Frage eher unkonventionell zu beantworten:

As a non-mathematician/software programmer I'm trying to grasp
how QFT (Quantum Fourier Transformation) works.

Angenommen, wir haben einen Quantencomputer, der Qubits manipulieren kann . Der Quantenzustand eines solchen Quantencomputers beschreibt genau den aktuellen Zustand dieses Quantencomputers. Es ist ziemlich bekannt, dass wir diesen Quantenzustand als einen Vektor von 2 n komplexen Zahlen ausdrücken können. Versuchen wir, diese komplexen Zahlen kompakt zu visualisieren.n2n

2n|0|2n- -1

Geben Sie hier die Bildbeschreibung ein

12n

Geben Sie hier die Bildbeschreibung ein

nn×11

Geben Sie hier die Bildbeschreibung ein

×

33

3|01|0

Geben Sie hier die Bildbeschreibung ein

Die Frage ist nun, was mit dem Quantenzustand passiert, wenn wir die Quanten-Fourier-Transformation anwenden. Es stellt sich heraus, dass, wenn die Quanten-Fourier-Transformation auf den oben gezeigten Zustand angewendet wird, der resultierende Zustand des Quantensystems wird:

Geben Sie hier die Bildbeschreibung ein

1/.8

|1

Geben Sie hier die Bildbeschreibung ein

Wenn wir nun die Quanten-Fourier-Transformation anwenden, wird der resultierende Zustand:

Geben Sie hier die Bildbeschreibung ein

Wir können sehen, dass der resultierende Zustand eine Art Helixform wird. Beachten Sie außerdem, dass die Helix genau eine Umdrehung ausführen würde, wenn wir rechts vom Zustand ganz rechts einen zusätzlichen Kreis hinzufügen würden.

|jj|3

Geben Sie hier die Bildbeschreibung ein

3

j|j

Es ist diese Idee, die die entscheidende Komponente in Shors Algortihm ist. Die zentrale Idee besteht darin, die von Ihnen beschriebene Zahlenfolge zu verwenden:

7, 4, 13, 1, 7, 4, 13, 1, 7, 4, 13, 1 (etc)

|4

ANMERKUNG 1: Es gibt viele Details, die ich im letzten Absatz übersprungen habe. Diese Antwort enthält jedoch bereits viele Informationen, die meiner Meinung nach erst berücksichtigt werden müssen, bevor man versuchen kann, diese Details zum Bild hinzuzufügen. Wenn jemand möchte, dass ich diese Details hinzufüge, kann ich dies zu einem späteren Zeitpunkt tun.

2n

arriopolis
quelle
Vielen Dank für die Antwort. Ich verstehe, was Sie sagen. Dies stimmt mit dem überein, was ich über Fourier-Transformationen (und die Umkehrung) wusste. Ich denke, die Geschichten über Uhren und Magnutiden haben mich mehr verwirrt, als es hätte sein sollen. Ich werde diesen anderen Ansatz wählen, um Shor zu erklären!
Roy van Rijn
2

In Ihrem Beispiel wird das Muster durch eine modulare Multiplikationsfunktion oder Schaltung f (x) = ax (mod N) erstellt. Diese Quantenschaltung und dieses Quantenmuster sind auch im IBM Q-Handbuch der IBM Q Experience angegeben .

Geben Sie hier die Bildbeschreibung ein

Also in einer Schleife mit Starteingang x = 1

x = 1 f (x) = 7 · 1 (mod 15) = 7

x = 7 f (x) = 7 · 7 (mod 15) = 4

x = 4 => 13

x = 13 => 1

Das Muster 1 7 4 13 1 wird jedes 4. Mal wiederholt. Die Schaltung ist also für ein gegebenes a und mod 15 fest und gibt immer r = 4 zurück. Wenn Sie r = 2 wollen, benötigen Sie eine andere Multiplikatorfunktion

Bram
quelle