I was looking into applications of Quantum Computing for machine learning and encountered the following pre-print from 2003. Quantum Convolution and Correlation Algorithms are Physically Impossible. The article doesn't appear to have been published in any journals, but it has been cited a few dozen times.
The article author makes the case that it is impossible to compute discrete convolution over quantum states. Intuitively this seems incorrect to me, since I know we can perform quantum matrix multiplication, and I know that discrete convolution can be framed simply as multiplication with a Toeplitz (or circulant) matrix.
The crux of his argument seems to be that there is no realizable composition of unitary operators for the elementwise (Hadamard) product of two vectors.
Where is my disconnect? Is there any reason we cannot in general construct a Toeplitz matrix for discrete convolution in a quantum computer?
Or is the article simply incorrect? I have worked through the contradiction that the author presents in his proof of Lemma 14, and it seems to make sense to me.