Quantum Algorithms for Convolution

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. 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 1

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.

Answer 2

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