Quantum Algorithms for Convolution

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.

• The paper ends stating "A final note: this result was inspired by a comment made by David Meyer, who obtained similar results independently." Did you check for a paper by Meyer? Aug 9 '18 at 18:33
• @NorbertSchuch I did, and was unable to find one making a similar claim.
– DPL
Aug 10 '18 at 20:16

I am highly suspicious of the result. If you look at Theorem 16, it claims that there is no operation that achieves the map $$\sum_{ij}\alpha_i\beta_j|ij\rangle\mapsto \sum_i\alpha_i\beta_i|i\rangle$$ up to normalisation. However, consider the measurement operator $$P=\sum_{i}|i\rangle\langle ii|.$$ This clearly implements the desired map (for that particular measurement outcome). Moreover, its implementation is quite straightforward. There is a unitary (effectively, a generalised controlled-not) that can map $$|ii\rangle\mapsto|i0\rangle,$$ so that you then measure the second spin and post-select on getting the 0 result. This would seem to invalidate the proof of the paper.

• Is it not required that the operation be unitary? Aug 8 '18 at 7:42
• @CraigGidney Theorem 16 is specifically talking about the combination of unitaries and measurement, and is claiming that there are no individual measurement results that can achieve that map. Aug 8 '18 at 8:06
• This seems like a good counterexample. Do you have a sense for any mistake in the author's logic in proving Lemma 14 (which he uses as a basis for proving Theorem 16?)
– DPL
Aug 8 '18 at 16:13
• @DPL I don’t think Lemma 14 is wrong (at least, I believe the result. I don’t know about the proof) There is however an odd argument in theorem 16 (it may be ok, I didn’t spend any time thinking about it, it just looks suspect) something about because something was true for unitaries it’s true for linear operators, and hence for measurements as well. Aug 8 '18 at 16:53
• @DPL more accurately, I believe Lemma 14 as it applies to unitaries. Aug 8 '18 at 17:00

You can actually perform convolution on a quantum computer (and exponentially faster for that matter), if your input signals have a certain structure. But for general inputs, this seems challenging and maybe even physically impossible, which is what the paper seems to argue.

Consider how you would compute the convolution of two discrete signals $f$ and $g$ classically. You can take the Fourier transform of both signals, do a point-wise multiplication of the resulting vectors, and then do an inverse Fourier transform:

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

Note that Fourier transform is a very cheap operation on a quantum computer. So this seems great. The problem is that the point-wise multiplication of two vectors is not so easy. Let's see what factors determine that.

Suppose we are lucky and the Fourier spectrum of $f$ turns out to be flat: $$F = \mathscr{F}(f) = \frac{1}{N}\sum_{i=0}^{N-1}{|i\rangle} = \sum_{i=1}^{N-1}F(i)$$

In that case, your quantum computer can do a diagonal matrix operation that gives you the point-wise multiplication: $$\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)$$

However, quantum algorithms that find the point-wise multiplication of two vectors may be physically impossible in the general case. This is because this operation is non-unitary in general. As a simple example, suppose that the Fourier transform of $f$ is a spiky function, with zeros in most places:

$$F = \mathscr{F}(f) = \frac{1}{2}(|0\rangle + |2\rangle + |5\rangle + |7\rangle)$$ The point-wise multiplication of this state with another state is non-reversible (because of the zeros), and thus not unitary.

There has been prior work to discover functions that result in a flat or near-flat Fourier spectrum, and are thus easy to convolute:

https://arxiv.org/abs/0811.3208

https://arxiv.org/abs/quant-ph/0211140