Comment by amluto

I think you have an also have not disproven the existence of a magical gadget of this general style. The programs mentioned in the paper have a very restrictive form, and I think you’re right that a program of that sort cannot propagate information through the array faster than the naive algorithm. But the actual average-case-ish gadget mentioned later is not of that form - it also has additions and maybe other things going on.

Interestingly, the operations discussed in this part of the note are, I think, pretty much exactly the operations needed to operate on classical representations of an m-qubit quantum state, implementing single-qubit unitary quantum gates on each qubit.

I suspect that, if you had asked me fifteen years ago if I thought you could do the same exact operations like this on each of n different states (on a classical computer) faster than n times however long it would take to do it once, I would have said “sure, why not?” It probably helps that I worked with people who really liked matrix multiplication and similar problems :)

For fun, I have ChatGPT Pro chewing on the following prompt:

Suppose I have a m-qubit quantum state. I can do an operation U = U_1 \otimes ... \otimes U_m, which is just a unitary operation on each individual register.

I can also simulate this on a classical computer. Start with the state, written out classically as a complex amplitude for each state in the computational basis (i.e. 2^m complex numbers). U acts on this state in a linear manner to produce a new state. What's the classical time complexity of this? (Assume a model of computation with exact complex addition, multiplication, conjugation, etc taking unit time, but don't cheat by encoding absurd things into complex numbers. Assume data movement is free.)

Now suppose I want to apply the same U to n separate input states. Can I do better than n times however long it takes to do the operation once?