Algorithmes quantiques pour la convolution

Je cherchais des applications de l'informatique quantique pour l'apprentissage automatique et j'ai rencontré la préimpression suivante de 2003. Les algorithmes de convolution et de corrélation quantiques sont physiquement impossibles . L'article ne semble avoir été publié dans aucune revue, mais il a été cité plusieurs dizaines de fois.

L'auteur de l'article démontre qu'il est impossible de calculer une convolution discrète sur des états quantiques. Intuitivement, cela me semble incorrect, car je sais que nous pouvons effectuer une multiplication matricielle quantique, et je sais que la convolution discrète peut être définie simplement comme une multiplication avec une matrice Toeplitz (ou circulante).

Le nœud de son argument semble être qu'il n'y a pas de composition réalisable d'opérateurs unitaires pour le produit élément par élément (Hadamard) de deux vecteurs.

Où est ma déconnexion? Y a-t-il une raison pour laquelle nous ne pouvons pas en général construire une matrice de Toeplitz pour la convolution discrète dans un ordinateur quantique?

Ou l'article est-il simplement incorrect? J'ai travaillé sur la contradiction que l'auteur présente dans sa preuve du lemme 14, et cela me semble logique.

Vous pouvez réellement effectuer une convolution sur un ordinateur quantique (et exponentiellement plus rapide d'ailleurs), si vos signaux d'entrée ont une certaine structure. Mais pour les contributions générales, cela semble difficile et peut-être même physiquement impossible, ce que le papier semble argumenter.

Considérez comment vous calculeriez la convolution de deux signaux discrets et g de façon classique. Vous pouvez prendre la transformée de Fourier des deux signaux, faire une multiplication point par point des vecteurs résultants, puis faire une transformée de Fourier inverse:$f$$g$

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

Notez que la transformée de Fourier est une opération très bon marché sur un ordinateur quantique. Cela semble donc super. Le problème est que la multiplication ponctuelle de deux vecteurs n'est pas si facile. Voyons quels facteurs déterminent cela.

$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)$$

Il y a eu des travaux antérieurs pour découvrir des fonctions qui aboutissent à un spectre de Fourier plat ou presque plat, et sont donc faciles à alerter:

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,$$