[OscarCunningham]

> The speedup from grover's algorithm is essentially universal it's just not an exponential speedup. So for example in your non-quantum simulation task, you want to search for an input to a cellular automata that makes it spell your name after 5000 timestemps. You can use grover's algorithm to find that input with a sqrt() the number of simulation runs that a classical machine would need (and perhaps fewer, since there are likely multiple solutions).

I'd view this as using fewer simulations, rather than doing the simulations faster.

Incidentally, I happen to be the author of some software for finding CA predecessors: https://github.com/OscarCunningham/logic-life-search/. Good luck getting it to do 5000 or even sqrt(5000) generations though! It's SAT solver based, so as soon as someone does invent a quantum SAT solver it'll plug right in.

> [Which is also why many of the common incorrect descriptions of quantum computing are sad, stuff like "testing all values in paralle"-- if it worked like that description it would be magic instant computing.]

To be fair, many quantum algorithms do begin by preparing a superposition of all possible intputs and then applying the unitary corresponding to some classical function. The difficulty arises when you have to extract information from the resulting output superposition.