Warum kann die diskrete Fouriertransformation effizient als Quantenschaltung implementiert werden?

17

Es ist ein bekanntes Ergebnis, dass die diskrete Fouriertransformation (DFT) von Zahlen Komplexität mit dem bekanntesten Algorithmus aufweist , während die Fouriertransformation der Amplituden eines Quantenzustands durchgeführt wird. benötigt beim klassischen QFT-Algorithmus nur Elementartore.N=2nÖ(n2n)Ö(n2)

Gibt es einen bekannten Grund dafür? Damit meine ich, ob es bekannte Eigenschaften der DFT gibt, die es ermöglichen, eine effiziente "Quantenversion" davon zu implementieren.

In der Tat kann eine DFT über dimensionale Vektoren als die lineare Operation N

y=DFTx,DFTjk1Nexp(2πichNjk).

Die "Quantenversion" dieses Problems ist die Aufgabe, bei gegebenem Quantenzustand |xk=1Nxk|k den Ausgangszustand |yk=1Nyk|k so, dass

|y=DFT|x=QFT|x.
  1. Eine erste Vereinfachung scheint darin zu liegen, dass wir uns aufgrund der Linearität des QM auf die Basiszustände |j,j=1,...,N mit der Entwicklung der allgemeinen Vektoren konzentrieren können |x dann kostenlos.
  2. Wenn N=2n , kann man |j in der Basis zwei ausdrücken , wobei |j=|j1,...,jn .
  3. Im Standard-QFT-Algorithmus wird dann ausgenutzt, dass die Transformation als
    |j1,...,jn2-n/2l=1n[|0+exp(2πich(0.jn-l+1jn))|1],
    das dann als Quantenschaltung der Form \ operatorname implementiert werden kann {QFT} | j_1, ..., j_n \ rangle = \ Big (\ prod_ {k = 1} ^ n \ mathcal U_k \ Big) | j_1, ..., j_n \ rangle,
    QFT|j1,...,jn=(k=1nUk)|j1,...,jn,
    wobei Uk mit implementiert ist Ö(n) Elementartore.

Angenommen, wir haben jetzt eine einheitliche Transformation und wollen eine Schaltung finden, die die äquivalente Quantentransformation effizient implementiert Die ersten beiden oben genannten Tricks können immer angewendet werden, aber es ist dann nicht trivial, wann und wie der andere Punkt verwendet werden kann, um Effizienzergebnisse zu erzielen, wie wir sie für die QFT haben.| y = A | x .EIN

|y=EIN|x.

Gibt es dafür bekannte Kriterien? Oder mit anderen Worten, ist es möglich, genau festzulegen, welche Eigenschaften der DFT es ermöglichen, die zugehörige Quantentransformation effizient umzusetzen?

glS
quelle
1
Die rekursive Struktur der QFT mit der Anzahl der Qubits scheint zu dieser Effizienz beizutragen.
AHusain

Antworten:

12

Einführung in die klassische diskrete Fouriertransformation:

Die DFT transformiert eine Folge von komplexen Zahlen in eine andere Folge komplexer Zahlen , definiert durch Wir können nach Bedarf mit geeigneten Normalisierungskonstanten multiplizieren. Darüber hinaus hängt es von der gewählten Konvention ab, ob wir in der Formel das Plus- oder das Minuszeichen verwenden.{ x n } : = x 0 , x 1 , x 2 , . . . , X N - 1 { X k } : = X 0 , X 1 , X 2 , . . . X k = N - 1 n = 0 × n . e ± 2 π i kN{xn}:=x0,x1,x2,...,xN1{Xk}: =X0,X1,X2,...

Xk=n=0N-1xn.e±2πichknN

Angenommen, es ist gegeben, dass und .x = ( 1 2 - i - i - 1 + 2 i )N=4x=(12-ich-ich-1+2ich)

Wir müssen den Spaltenvektor . Die allgemeine Methode wird bereits auf der Wikipedia-Seite angezeigt . Dafür werden wir aber eine Matrixnotation entwickeln. kann leicht durch Vormultiplizieren von mit der Matrix erhalten werden:X xXXx

M=1N(11111ww2w31w2w4w61w3w6w9)

wo ist . Jedes Element der Matrix ist grundsätzlich . ist einfach eine Normalisierungskonstante.e - 2 π iw wij1e-2πichNwichj1N

Schließlich ist : .1X12(2-2-2ich-2ich4+4ich)

Lehnen Sie sich jetzt zurück und beachten Sie einige wichtige Eigenschaften:

  • Alle Spalten der Matrix sind orthogonal zueinander.M
  • Alle Spalten von haben die Größe .1M1
  • Wenn Sie mit einem Spaltenvektor mit vielen Nullen multiplizieren (große Spreizung), erhalten Sie einen Spaltenvektor mit nur wenigen Nullen (schmale Spreizung). Das Gegenteil gilt auch. (Prüfen!)M

Es ist sehr einfach zu bemerken, dass die klassische DFT eine zeitliche Komplexität . Das ist , weil für jede Zeile des Erhaltens , - Operationen durchgeführt werden müssen. Und es gibt Zeilen in .X N N XÖ(N2)XNNX


Die schnelle Fouriertransformation:

Betrachten wir nun die Fast-Fourier-Transformation. Die schnelle Fourier-Transformation verwendet die Symmetrie der Fourier-Transformation, um die Rechenzeit zu reduzieren. Einfach ausgedrückt, schreiben wir die Fouriertransformation der Größe als zwei Fouriertransformationen der Größe - die ungeraden und die geraden Terme. Wir wiederholen dies dann immer und immer wieder, um die Zeit exponentiell zu verkürzen. Um zu sehen, wie dies im Detail funktioniert, wenden wir uns der Matrix der Fouriertransformation zu. Während wir dies durchgehen, kann es hilfreich sein, vor sich zu haben, um einen Blick darauf zu werfen. Beachten Sie, dass die Exponenten modulo , da .N / 2 DFT 8 8 w 8 = 1NN/2DFT88w8=1

Bildbeschreibung hier eingeben

Beachten Sie, dass Zeile Zeile sehr ähnlich ist . Beachten Sie auch, dass Spalte Spalte sehr ähnlich ist . Aus diesem Grund werden wir die Fourier-Transformation in gerade und ungerade Spalten aufteilen.j + 4 j j + 4jj+4jj+4

Bildbeschreibung hier eingeben

Im ersten Frame haben wir die gesamte Fourier-Transformationsmatrix durch Beschreiben der ten Zeile und der ten Spalte dargestellt: . Im nächsten Frame trennen wir die ungeraden und geraden Spalten und auf ähnliche Weise den Vektor, der transformiert werden soll. Sie sollten sich davon überzeugen, dass die erste Gleichheit wirklich eine Gleichheit ist. Im dritten Frame fügen wir eine kleine Symmetrie hinzu, indem wir feststellen, dass (da ).k w j k w j + N / 2 = - w j w n / 2 = - 1jkwjkwj+N/2=-wjwn/2=-1

Beachten Sie, dass sowohl die ungerade als auch die gerade Seite den Begriff . Aber wenn die primitive N-te Wurzel der Einheit ist, dann ist die primitive te Wurzel der Einheit. Daher sind die Matrizen, deren , ter Eintrag ist, wirklich nur ! Nun können wir auf eine neue Art schreiben : Nehmen wir an, wir berechnen die Fourier-Transformation der Funktion . Wir können die obigen Manipulationen als Gleichung schreiben, die den j-ten Term berechnet . w w 2 N / 2w2jkww2N/2k w 2 j k DFT ( N / 2 ) DFT N f ( x ) f ( j )jkw2jkDFT(N/2)DFTNf(x)f^(j)

Bildbeschreibung hier eingeben

Hinweis: QFT im Bild steht in diesem Zusammenhang nur für DFT. Außerdem bezieht sich M auf das, was wir N nennen.

Dies wandelt unsere Berechnung von in zwei Anwendungen von . Wir können dies in vier Anwendungen von usw. umwandeln. Solange für einige , können wir unsere Berechnung von in Berechnungen von . Dies vereinfacht unsere Berechnung erheblich.DFT ( N / 2 ) DFT ( N / 4 ) N = 2 n n DFT N N DFT 1 = 1DFTNDFT(N/2)DFT(N/4)N=2nnDFTNNDFT1=1

Bei der Fast-Fourier-Transformation reduziert sich die Zeitkomplexität auf (versuchen Sie dies selbst zu beweisen). Dies ist eine enorme Verbesserung gegenüber der klassischen DFT und so ziemlich dem neuesten Algorithmus, der in modernen Musiksystemen wie Ihrem iPod verwendet wird!Ö(NLog(N))


Die Quanten-Fourier-Transformation mit Quantentoren:

Die Stärke der FFT ist, dass wir die Symmetrie der diskreten Fourier-Transformation zu unserem Vorteil nutzen können. Die Schaltungsanwendung von QFT verwendet dasselbe Prinzip, jedoch ist QFT aufgrund der Überlagerungsleistung noch schneller.

Die QFT wird durch die FFT motiviert, so dass wir die gleichen Schritte ausführen, aber da dies ein Quantenalgorithmus ist, wird die Implementierung der Schritte unterschiedlich sein. Das heißt, wir nehmen zuerst die Fourier-Transformation der ungeraden und geraden Teile und multiplizieren dann die ungeraden Terme mit der Phase .wj

In einem Quantenalgorithmus ist der erste Schritt ziemlich einfach. Die ungeraden und geraden Terme überlagern sich: Die ungeraden Terme sind diejenigen, deren niedrigstwertiges Bit , und die geraden mit . Daher können wir sowohl auf die ungeraden als auch auf die geraden Terme zusammen anwenden . Wir tun dies, indem wir einfach auf die höchstwertigen Bits anwenden und die ungeraden und geraden entsprechend neu kombinieren, indem wir Hadamard auf das niedrigstwertige Bit anwenden.0 QFT ( N / 2 ) QFT ( N / 2 ) n - 110QFT(N/2)QFT(N/2)n-1

Um nun die Phasenmultiplikation durchzuführen, müssen wir jeden ungeraden Term mit der Phase multiplizieren . Denken Sie jedoch daran, dass eine ungerade Zahl in binären Zahlen mit einer endet, während eine gerade Zahl mit einer endet . Somit können wir die gesteuerte Phasenverschiebung, bei der das niedrigstwertige Bit die Steuerung ist, verwenden, um nur die ungeraden Terme mit der Phase zu multiplizieren, ohne die geraden Terme zu verändern. Es sei daran erinnert, dass die gesteuerte Phasenverschiebung dem CNOT-Gatter insofern ähnlich ist, als dass nur dann eine Phase auf das Ziel angewendet wird, wenn das Steuerbit eins ist.w j 1 0jwj10

Bildbeschreibung hier eingeben

Hinweis: In der Abbildung bezieht sich M auf das, was wir N nennen.

Die jeder gesteuerten Phasenverschiebung zugeordnete Phase sollte gleich wobei dem ten Bit durch . Wenden Sie daher die gesteuerte Phasenverschiebung auf jedes der ersten Qubits mit dem niedrigstwertigen Bit als Steuerung an. Mit der gesteuerten Phasenverschiebung und der Hadamard-Transformation wurde auf reduziert . j k j = 2 k n - 1 QFT N QFT ( N / 2 )wjjkj=2kn-1QFTNQFT(N/2)

Bildbeschreibung hier eingeben

Hinweis: In der Abbildung bezieht sich M auf das, was wir N nennen.

Beispiel:

Lässt konstruieren . Nach dem Algorithmus wir in und einige Quantentore um. Dann setzen wir diesen Weg fort und verwandeln in (das ist nur ein Hadamard-Tor) und ein paar weitere Tore. Kontrollierte Phasentore werden durch . Führen Sie dann eine weitere Iteration durch, um . Sie sollten nun in der Lage sein, die Schaltung für auf mehr Qubits leicht zu visualisieren . Außerdem können Sie sehen, dass die Anzahl der für die Ausführung von erforderlichen Gates genau istQFT 3 QFT 2 QFT 2 QFT 1 R φ QFT 2 QFT QFT N log ( N ) Σ i = 1 i = log ( N ) ( log ( N ) + 1 ) / 2 = O ( log 2 N )QFT3QFT3QFT2QFT2QFT1RϕQFT2QFTQFTN

ich=1Log(N)ich=Log(N)(Log(N)+1)/2=Ö(Log2N)

Quellen:

  1. https://en.wikipedia.org/wiki/Discrete_Fourier_transform

  2. https://en.wikipedia.org/wiki/Quantum_Fourier_transform

  3. Quantenmechanik und Quantenberechnung MOOC (UC BerkeleyX) - Skript: Kapitel 5

PS: Diese Antwort ist in der vorläufigen Version. Wie @DaftWillie in den Kommentaren erwähnt, geht es nicht viel um " irgendwelche Einsichten, die Hinweise in Bezug auf andere mögliche Algorithmen geben könnten ". Ich empfehle alternative Antworten auf die ursprüngliche Frage. Ich persönlich muss ein bisschen lesen und nach Ressourcen suchen, damit ich diesen Aspekt der Frage beantworten kann.

Sanchayan Dutta
quelle
Bezüglich der rekursiven Struktur: Man könnte das per Definition mehr oder weniger annehmen. Wenn Sie über die Skalierung eines Algorithmus sprechen möchten, benötigen Sie eine Schaltkreisfamilie für unterschiedlich große Eingänge. Die Art und Weise, wie dies normalerweise gemacht wird, besteht darin, die Schaltung für Größe n + 1 aus der Schaltung für Größe n aufzubauen behaupten, das ist eine einfache Sache zu tun)
DaftWullie
@DaftWullie "Was ich hier nicht wirklich sehe, ist eine Einsicht, die Hinweise auf andere mögliche Algorithmen geben könnte (nicht, dass ich behaupte, dass das eine einfache Sache ist)." Nun, ja! Ich habe auch darüber nachgedacht. Dies ist eher eine vorläufige Antwort. Ich werde mehr hinzufügen, wenn ich etwas mehr lerne (und wenn ich mehr Freizeit habe). Ich würde mich sehr über alternative Antworten auf diese Frage freuen. :-)
Sanchayan Dutta
Nur weil Sie eine Folge von Problemen haben, bedeutet nicht , dass man den Algorithmus für die nächste (geschweige denn einen guten) gibt. Es ist typisch, weil wir normalerweise an nette Funktionen denken. So einfach rekursiv zu sein, ist eine Eigenschaft einer Folge von Problemen. Hier ist, was ich meine , ist es eine Faktorisierung existiert . Mit dieser Frage zu diagnostizieren , ob eine Sequenz die gleichen efficency Eigenschaften hat. U Un=Un-1xU
AHusain
Hi, in QFT wird implizit angenommen, dass ein Eingangsvektor x_classical, beispielsweise 8 x 1, amplitudencodiert mit 3-Qubits ist? Dann werden die QFT-Operationen an den codierten Qubits durchgeführt. Können Sie auch näher erläutern, "... und die ungeraden und geraden Werte durch Anwenden des Hadamard auf das niedrigstwertige Bit entsprechend neu kombinieren"?
Abdullah Ash-Saki
10

F2n=12nk,x{0,1}nexp(ichQ.(k,x))|kx|,
Q.(z)=1jk2nθj,kzjzk2n
θj,k={π/22n-j-k,wenn 1jn<k2n-j+10,Andernfalls.
  1. Es gibt eine Funktion , so dass für jede (wobei im Fall der QFT);f:{1,2,,n}{n+1,n+2,,2n}θj,k=π1jnf(j)=2n-j+1
  2. Für jeden für die , haben wir .1h,jnθh,f(j)0θj,f(h)=0

Wir können uns die Indizes von als Eingangs- und Ausgangsleitungen einer Quantenschaltung vorstellen, wobei unsere Aufgabe darin besteht, zu zeigen, was die Schaltung in der Mitte ist Das zeigt, wie die Eingänge mit den Ausgängen verbunden sind. Die obige Funktion ermöglicht es uns, die Zuordnung von Ausgangsleitungen zu Eingangsleitungen zu sehen, dh, es gibt jeweils ein Hadamard-Gate, das die beiden Enden miteinander verbindet, und abgesehen von den Hadamards- (und SWAP-Gates, die die Umkehrung von in erklären In der Reihenfolge der Indizes zwischen und ) sind alle anderen Operationen Zwei-Qubit-gesteuerte Phasen Tore für relative Phasen von . Die zweite Bedingung zuz=(k,x){0,1}2nf(1,2,,n)(f(1),f(2),,f(n))exp(ichθj,k)f dient dazu, dass diese Phasenanschnittstore eine genau definierte zeitliche Reihenfolge erhalten können.

Es gibt allgemeinere Bedingungen, die man beschreiben könnte, wenn eine quadratische Formerweiterung eine realisierbare Schaltung in ähnlicher Weise hervorruft. Das Obige beschreibt einen der einfachsten Fälle, in denen es keine Indizes in der Summe gibt, mit Ausnahme derjenigen für die Standardbasis der Eingangs- und Ausgangszustände (in diesem Fall haben die Koeffizienten der zugeordneten Einheit alle die gleiche Größe).

Niel de Beaudrap
quelle
Ich bin mir nicht sicher, ob ich es richtig verstanden habe. Wollen Sie damit sagen, dass jede Evolution, die als quadratische Formerweiterung mit einer quadratischen Form dargestellt wird, die diese beiden Bedingungen erfüllt, effizient implementiert werden kann? Sehr interessant
glS
@gIS: Ja, und außerdem ist der Aufbau im Wesentlichen der gleiche wie bei der Coppersmith-QFT-Schaltung (oder vielmehr, die Tatsache, dass die QFT diese Form hat, ist der Grund, warum die Coppersmith-Schaltungsstruktur ausreicht, um die QFT zu realisieren).
Niel de Beaudrap
8

Dies weicht ein wenig von der ursprünglichen Frage ab, aber ich hoffe, es gibt ein wenig mehr Einsicht, die für andere Probleme relevant sein könnte.

Man könnte fragen: "Was ist mit der Ordnungsfindung, das sich für eine effiziente Implementierung auf einem Quantencomputer eignet?". Die Ordnungsfindung ist die Hauptkomponente der Faktorisierungsalgorithmen und schließt die Fourier-Transformation als Teil davon ein.

Das Interessante ist, dass Sie Dinge wie die Ordnungsfindung und das Problem von Simon in einen allgemeinen Kontext stellen können, der als "Hidden Subgroup Problem" bezeichnet wird .

Nehmen wir eine Gruppe mit Elementen, die durch indiziert sind , und eine Gruppenoperation ' '. Wir sind eine Oracle gegeben, die die Funktion auswertet , und wir sicher sein, dass es eine Untergruppe ist, , von mit den Elementen , so daß alle für und , . Es ist unsere Aufgabe, die Generatoren der Untergruppe aufzudecken . Im Fall von Simons Problem besteht die Gruppe beispielsweise nur aus Bit-Zahlen, und die Untergruppe besteht aus einem Paar von ElementenGGf(G)KGkGGkKf(G)=f(Gk)KGnK{0,s}. Die Gruppenoperation ist bitweise Addition.

Effiziente Lösungen (die als Polynom von skaliert werden ) existieren, wenn die Gruppe abelsch ist, dh wenn die Operation kommutativ ist, wobei die Fouriertransformation über die relevante Gruppe verwendet wird. Zwischen der Gruppenstruktur (z. B. ) und dem Problem, das effizient gelöst werden kann (z. B. Simons Problem), bestehen gut etablierte Verknüpfungen . Wenn wir zum Beispiel das Problem der versteckten Untergruppen für die symmetrische Gruppe lösen könnten, würde dies bei der Lösung des Graphisomorphismusproblems helfenLog|G|G{0,1}n,. In diesem speziellen Fall ist bekannt, wie die Fourier-Transformation durchzuführen ist, obwohl dies an sich nicht ausreicht, um einen Algorithmus zu erstellen, zum Teil, weil eine zusätzliche Nachbearbeitung erforderlich ist. Im Fall von Simons Problem benötigten wir beispielsweise mehrere Läufe, um genügend linear unabhängige Vektoren zu finden, um zu bestimmen . Beim Factoring mussten wir einen Algorithmus für fortgesetzte Brüche für die Ausgabe ausführen. Es gibt also immer noch eine klassische Nachbearbeitung, die effizient durchgeführt werden muss, auch wenn die entsprechende Fouriertransformation implementiert werden kann.s


Noch ein paar Details

Im Prinzip wird das Problem der versteckten Untergruppen für abelsche Gruppen wie folgt gelöst. Wir beginnen mit zwei Registern, , und bereiten das erste in einer einheitlichen Überlagerung aller Gruppenelemente vor, und führe die Funktionsbewertung wobei so definiert ist, dass durch Wenn Sie jedes Element nehmen und mit den Mitgliedern von kombinieren, erhalten Sie die gesamte Gruppe (dh, jedes Mitglied von erzeugt eine andere Nebenmenge, die unterschiedliche Werte von ergibt|0|0

1|G|GG|G|0,
1|G|G|G|f(G)=1|G|GKkK|Gk|f(G),
KKGKf(G)) und ist als orthogonale Untergruppe bekannt. Verfolgung des zweiten Registers, Nun führen wir die Fourier-Transformation über die Gruppe und geben den Ausgangszustand Jeder der Vektoren hat eine Wahrscheinlichkeit vongefunden zu werden, und alle anderen haben 0 Wahrscheinlichkeit. Sobald die Generatoren von bestimmt worden sind, können wir die Generatoren von über eine lineare Algebra herausfinden .G| K|
1|K|GKk,kK|GkGk|.
G| gK| K| /| G| KK
|K||G|GK|GG|.
|GK|K|/|G|KK
DaftWullie
quelle
3

Eine von vielen möglichen Konstruktionen, die zumindest für mich einen Einblick in diese Frage geben, ist die folgende. Mit der CSD (Cosinus-Sinus-Zerlegung) können Sie jeden einzelnen Operator zu einem Produkt effizienter Gatter V erweitern, die gut in ein binäres Baummuster passen. Im Fall der QFT kollabiert dieser Binärbaum zu einem einzelnen Zweig des Baums, alle V, die nicht in dem Zweig sind, sind 1.

Ref: Quantenschnelle Fourier-Transformation, die von mir als Spezialfall für die rekursive Anwendung der Cosinus-Sinus-Zerlegung angesehen wird .

rrtucci
quelle
interessant, danke. Könnten Sie der Antwort, wenn möglich, eine Skizze des Arguments hinzufügen?
glS
1
Was ich bereits vorgestellt habe, ist meine Version einer "Skizze". Wenn Sie sich eingehender mit Gleichungen und Bildern
befassen möchten