[someotherone]

So it looks like QC is good for speeding up simulations, and with far less overhead for ECC and such than it needs for things like factoring. So is simulation the QC "killer app"?

Does it only do certain kinds of simulations well, i.e. simulations of quantum systems, or can that be generalized? Can it be applied to economic, environmental, traffic, etc as well?

[OscarCunningham]

>Can it be applied to economic, environmental, traffic, etc as well?

Our current understanding is that quantum computers won't offer a speedup for the simulation of nonquantum systems. The only simulations they'll be faster for are systems for which quantum effects are important.

Of course it's possible that someone will discover an algorithm that gives quantum computers an exponential speedup in the simulation of any system. But I think that's pretty unlikely because it would imply that quantum computers were exponentially faster than classical computers computers for every problem, because you could just use your quantum computer to simulate a classical one.

[nullc]

> Our current understanding is that quantum computers won't offer a speedup for the simulation of nonquantum systems.

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

To me that's one of the most interesting things about quantum computation: There is a very broad class of things where it offers a modest speedup (sqrt) and a narrow (but useful!) class of things where it offers an exponential speedup. But if you imagine almost any kind of 'superpowered quantum computation'-- something that is a little more powerful than the laws of physics as we know them allow-- you almost always get an exponential speedup for everything (or even more absurd results, like every problem being solvable in constant time). QC has this interesting property of being just strictly more powerful than classical computing, but without being magic-instant-computing.

[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.]

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

[sanxiyn]

There is no known useful application of current quantum computing (so-called NISQ, for Noisy Intermediate-Scale Quantum). It is an open question whether there is any, see https://arxiv.org/abs/1801.00862.