Algoritmos Quânticos para Convolução

Eu estava estudando aplicações da Computação Quântica para aprendizado de máquina e encontrei a seguinte pré-impressão de 2003. Os algoritmos de convolução e correlação quântica são fisicamente impossíveis . O artigo não parece ter sido publicado em nenhum periódico, mas foi citado algumas dezenas de vezes.

O autor do artigo defende que é impossível calcular convolução discreta sobre estados quânticos. Intuitivamente, isso me parece incorreto, pois sei que podemos realizar a multiplicação da matriz quântica e sei que convolução discreta pode ser enquadrada simplesmente como multiplicação com uma matriz Toeplitz (ou circulante).

O ponto crucial de seu argumento parece ser que não há composição realizável de operadores unitários para o produto elementwise (Hadamard) de dois vetores.

Onde está minha desconexão? Existe alguma razão para que em geral não possamos construir uma matriz de Toeplitz para convolução discreta em um computador quântico?

Ou o artigo está simplesmente incorreto? Eu trabalhei com a contradição que o autor apresenta em sua prova do Lema 14, e isso parece fazer sentido para mim.

Você pode realmente realizar a convolução em um computador quântico (e exponencialmente mais rápido), se os sinais de entrada tiverem uma certa estrutura. Mas, para informações gerais, isso parece desafiador e talvez até fisicamente impossível, que é o que o artigo parece argumentar.

Considere como você calcularia a convolução de dois sinais discretos e g classicamente. Você pode pegar a transformação de Fourier de ambos os sinais, fazer uma multiplicação por pontos dos vetores resultantes e, em seguida, fazer uma transformação de Fourier inversa:$f$$g$

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

Observe que a transformação de Fourier é uma operação muito barata em um computador quântico. Então isso parece ótimo. O problema é que a multiplicação pontual de dois vetores não é tão fácil. Vamos ver quais fatores determinam isso.

Suponha que tenhamos sorte e que o espectro de Fourier de seja plano: F = F ( f ) = $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)$$

Houve trabalhos anteriores para descobrir funções que resultam em um espectro de Fourier plano ou quase plano e, portanto, são fáceis de envolver:

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