Quantenalgorithmen, die auf anderen Transformationen als Fouriertransformationen basieren

In Quantum Computation und Quantum Information von Nielsen und Chuang heißt es, dass viele der Algorithmen, die auf Quanten-Fourier-Transformationen basieren, auf der Coset-Invarianz-Eigenschaft von Fourier-Transformationen beruhen, und dass Invarianzeigenschaften anderer Transformationen möglicherweise zu neuen Algorithmen führen.

Hat es fruchtbare Forschungen zu anderen Transformationen gegeben?

quantum-computing quantum-information Sam Burville
quelle

Ja. Yi-Kai Liu, Shelby Kimmel und andere haben Quantenalgorithmen entwickelt, die auf Wavelet-Transformationen basieren, und Stephen Jordan hat Quantenalgorithmen entwickelt, die auf der Clebsch-Gordan-Transformation basieren. Sie können auf Google nach Referenzen suchen, oder andere Personen stellen möglicherweise einige zur Verfügung. Natürlich sind die Probleme, die durch diese Algorithmen gelöst werden, nicht so auffällig wie Factoring und diskretes Log (sonst hätten Sie schon davon gehört).

Scott Aaronson

@ ScottAaronson Kommentar -> Antwort

Alessandro Cosentino

@ScottAaronson Großartig, ich werde sie untersuchen. Vielen Dank!

Sam Burville

Hamilton-Orakel?

VZN

Yi-Kai Liu hat mithilfe der Curvelet-Transformation Quantenalgorithmen entwickelt (siehe die Vollversion auf arXiv oder die Kurzversion von FOCS).

Māris Ozols,

Antworten:

Ich möchte noch einige Verweise auf Scotts Kommentar hinzufügen:

In der Tat sind Clebsch-Gordan-Transformationen (die man sich als Mehrregister-Quanten-Fourier-Transformationen vorstellen kann) ein nützliches Werkzeug für den Entwurf von Quantenalgorithmen für nicht-abelsche Hidden Subgroup Problems (HSPs).

Greg Kuperberg und Oded Regev verwendeten Clebsch-Gordan-Transformationen , um das diedrische HSP in subexponentieller (aber superpolynomieller) Zeit zu lösen. Diese Quantenalgorithmen sind nicht effizient, aber sie haben eine bessere Abfragekomplexität als klassische Algorithmen.
in Polynomzeit. Ich kann dieses Papier empfehlen, weil es ziemlich klar ist. $\mathbb{Z}_p^2\rtimes \mathbb{Z}_p$

Ich schreibe auch, um hinzuzufügen, dass wir nicht vergessen sollten, dass sowohl Quanten-Fourier-Transformationen als auch Clebsch-Gordan-Transformationen nicht immer unverzichtbar sind, auch wenn sie sehr nützlich sein können.

In Shors Algorithmus (oder sogar in der Quantenphasenschätzung) können die Fouriertransformationen durch Hadamard-Tests ersetzt werden , daher werden nur Hadamard-Gatter anstelle von Fouriertransformationen verwendet. Dieser Trick ist Kitaev zu verdanken und kann hier nachgelesen werden .
Es gibt noch einen weiteren effizienten Algorithmus für die HSP über von Bacon, Childs, Van Dam, der keine Clebsch-Gordan-Transformationen verwendet. Stattdessen verwendet der Algorithmus eine bestimmte Art von leistungsfähigem POVM, die als Pretty Good Measurement bezeichnet wird. $\mathbb{Z}_p^2\rtimes \mathbb{Z}_p$

Natürlich ist diese Liste wahrscheinlich unvollständig. Ich hoffe, jemand wird auf andere Ergebnisse hinweisen, die noch nicht erwähnt wurden.

Juan Bermejo Vega
quelle

HSP = verstecktes Untergruppenproblem

vzn

Vielen Dank für den Hinweis. Ich habe das Akronym in der letzten Ausgabe erklärt.

Juan Bermejo Vega

Ich bin mir nicht sicher, ob dies direkt mit Ihrer Frage zusammenhängt, aber als ich sie las, dachte ich an einen Artikel von Peter Høyer, den ich vor einigen Jahren gelesen hatte. Darin zeigt er, wie die populärsten Quantenalgorithmen wie Grovers oder Shors dem gleichen Muster folgen, das er "konjugierte Operatoren" nennt, und er baut neue Algorithmen, die ebenfalls auf demselben Muster basieren.

Wie gesagt, es ist ein paar Jahre her, seit ich es gelesen habe, daher ist meine Beschreibung etwas schlampig, aber hier ist der Link, falls Sie es überprüfen möchten.

http://journals.aps.org/pra/abstract/10.1103/PhysRevA.59.3280

Philippe Lamontagne
quelle