Algoritmos Cuánticos para Convolución

Estaba buscando aplicaciones de computación cuántica para el aprendizaje automático y encontré la siguiente preimpresión de 2003. Los algoritmos de convolución cuántica y correlación son físicamente imposibles . El artículo no parece haber sido publicado en ninguna revista, pero ha sido citado algunas docenas de veces.

El autor del artículo afirma que es imposible calcular la convolución discreta sobre los estados cuánticos. Intuitivamente, esto me parece incorrecto, ya que sé que podemos realizar una multiplicación de matriz cuántica, y sé que la convolución discreta puede enmarcarse simplemente como una multiplicación con una matriz de Toeplitz (o circulante).

El quid de su argumento parece ser que no existe una composición realizable de operadores unitarios para el producto elementwise (Hadamard) de dos vectores.

¿Dónde está mi desconexión? ¿Hay alguna razón por la que, en general, no podamos construir una matriz de Toeplitz para una convolución discreta en una computadora cuántica?

¿O es el artículo simplemente incorrecto? He trabajado a través de la contradicción que el autor presenta en su prueba de Lema 14, y parece tener sentido para mí.

En realidad, puede realizar convolución en una computadora cuántica (y exponencialmente más rápido), si sus señales de entrada tienen una determinada estructura. Pero para los aportes generales, esto parece desafiante e incluso físicamente imposible, que es lo que parece argumentar el artículo.

Considere cómo calcularía la convolución de dos señales discretas y clásicamente. Puede tomar la transformada de Fourier de ambas señales, hacer una multiplicación puntual de los vectores resultantes y luego hacer una transformada inversa de Fourier:$f$$g$

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

Tenga en cuenta que la transformación de Fourier es una operación muy barata en una computadora cuántica. Entonces esto parece genial. El problema es que la multiplicación puntual de dos vectores no es tan fácil. Veamos qué factores determinan eso.

Supongamos que tenemos suerte y el espectro de Fourier de resulta ser plano: F = F ( f ) = 1$f$

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

En ese caso, su computadora cuántica puede hacer una operación de matriz diagonal que le da la multiplicación por puntos:

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

Sin embargo, los algoritmos cuánticos que encuentran la multiplicación puntual de dos vectores pueden ser físicamente imposibles en el caso general. Esto se debe a que esta operación no es unitaria en general. Como ejemplo simple, suponga que la transformada de Fourier de es una función puntiaguda, con ceros en la mayoría de los lugares:$f$

La multiplicación de punto racional de este estado con otro estado no reversible (debido a los ceros), y por lo tanto no unitario.

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

Ha habido trabajo previo para descubrir funciones que dan como resultado un espectro de Fourier plano o casi plano, y por lo tanto son fáciles de convolucionar:

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