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: 
Speaking as a computer scientist without any physics background making contributions to quantum computing: yes, computer scientists without any physics background can make contributions to quantum computing. Though I think it was always that way; it has nothing to do with the field being "mature".

If you understand the postulates of quantum mechanics (operations are unitary matrices, states are unit vectors, measurement is a projection), and know how to apply those in the context of a computation, you can create quantum algorithms. The fact that these concepts were originally derived from physics is historically interesting, but not really relevant when optimizing a quantum circuit. As a concrete example: quantum physics is very heavy on calculus, but quantum computation isn't.

Quantum physics does become relevant if you are trying to design algorithms for simulating quantum systems. And some of the concepts you would learn in a quantum physics course should also appear in a quantum computation course. But overall [I agree with Scott Aaronson](https://www.scottaaronson.com/democritus/lec9.html):

> 
> [My] way to teach quantum mechanics [...] starts directly from the conceptual core -- namely, a certain generalization of probability theory to allow minus signs. Once you know what the theory is actually about, you can then sprinkle in physics to taste [...]
> 
> 
> [quantum mechanics is] not a physical theory in the same sense as electromagnetism or general relativity. [...] Basically, quantum mechanics is the operating system that other physical theories run on as application software [...]
> 
> 
> [...] [quantum mechanics is] about information and probabilities and observables, and how they relate to each other.
> 
> 
>
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.)