Quantenalgorithmen für die Faltung

Ich habe mich mit Anwendungen von Quantum Computing für maschinelles Lernen befasst und bin auf den folgenden Vordruck aus dem Jahr 2003 gestoßen. Quantenfaltungs- und Korrelationsalgorithmen sind physikalisch unmöglich . Der Artikel scheint in keiner Zeitschrift veröffentlicht worden zu sein, wurde aber einige Dutzend Mal zitiert.

Der Artikelautor macht geltend, dass es unmöglich ist, eine diskrete Faltung über Quantenzustände zu berechnen. Intuitiv erscheint mir dies falsch, da ich weiß, dass wir eine Quantenmatrixmultiplikation durchführen können, und ich weiß, dass diskrete Faltung einfach als Multiplikation mit einer Toeplitz- (oder zirkulierenden) Matrix dargestellt werden kann.

Der Kern seines Arguments scheint zu sein, dass es keine realisierbare Zusammensetzung einheitlicher Operatoren für das elementweise (Hadamard) Produkt zweier Vektoren gibt.

Wo ist meine Trennung? Gibt es einen Grund, warum wir im Allgemeinen keine Toeplitz-Matrix für die diskrete Faltung in einem Quantencomputer konstruieren können?

Oder ist der Artikel einfach falsch? Ich habe den Widerspruch durchgearbeitet, den der Autor in seinem Beweis von Lemma 14 vorlegt, und er scheint mir sinnvoll zu sein.

Sie können tatsächlich eine Faltung auf einem Quantencomputer durchführen (und diesbezüglich exponentiell schneller), wenn Ihre Eingangssignale eine bestimmte Struktur haben. Aber für allgemeine Eingaben scheint dies herausfordernd und vielleicht sogar physikalisch unmöglich zu sein, was das Papier zu argumentieren scheint.

$f$$g$

$$\mathscr{F}^{-1} (\mathscr{F}(f) . \mathscr{F}(g))$$

Beachten Sie, dass die Fourier-Transformation eine sehr billige Operation auf einem Quantencomputer ist. Das scheint also großartig zu sein. Das Problem ist, dass die punktweise Multiplikation zweier Vektoren nicht so einfach ist. Mal sehen, welche Faktoren das bestimmen.

$f$

$$F = \mathscr{F}(f) = \frac{1}{N}\sum_{i=0}^{N-1}{|i\rangle} = \sum_{i=1}^{N-1}F(i)$$

$$\mathscr{F}(f) . \mathscr{F}(g) = F.G = \left(\begin{array}{cccc} F(0) & & & \\ & F(1) & & \\ & & . & \\ & & & F(N-1) \end{array}\right) \left(\begin{array}{c} G(0) \\ G(1) \\ . \\ G(N-1) \end{array}\right)$$

$f$

$$F = \mathscr{F}(f) = \frac{1}{2}(|0\rangle + |2\rangle + |5\rangle + |7\rangle)$$

Es wurden bereits Arbeiten durchgeführt, um Funktionen zu entdecken, die zu einem flachen oder nahezu flachen Fourier-Spektrum führen und daher leicht zu falten sind:

https://arxiv.org/abs/0811.3208

https://arxiv.org/abs/quant-ph/0211140

$$\sum_{ij}\alpha_i\beta_j|ij\rangle\mapsto \sum_i\alpha_i\beta_i|i\rangle$$ $$P=\sum_{i}|i\rangle\langle ii|.$$ $$|ii\rangle\mapsto|i0\rangle,$$