Question: 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](https://arxiv.org/abs/quant-ph/0309070). 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.

Answer: 
It has pretty much always been like that. You can study the book by Nielsen & Chuang without knowing about physics. There is the [introduction by Mermin](https://arxiv.org/abs/quant-ph/0207118) aimed at computer scientists. There are probably lots of other resources (I'm pretty sure e.g. that Aaronson's book -- based on a [CS lecture](https://www.scottaaronson.com/democritus/) -- is perfectly suited for people without a physics background.) Overall, the physics formalism needed to understand quantum information and computation is pretty low-key, as compared to other fields of (quantum) physics. (This doesn't mean though that studying the phenomena in quantum information and computation is low-key.)
Quantum computing is totally understandable without physics background for several reasons:

1. Quantum computing is sufficiently written in abstract mathematical language (Linear Algebra).
2. Quantum computing does not include dynamical equations such as Schrodinger equations. Moreover, all operations can be understood as logical gates instead of physical entities.
3. Quantum mechanics itself made a bridge between physics and information in a such way that information scientist can understand it from his/her perspective.

However, quantum mechanics and quantum computing includes new concepts that are hard to accept by everyone including physicists. So don't worry.