[tialaramex]

Grover's Algorithm gets you effectively a square root difficulty improvement. So, AES 256 is "only" as strong as a 128-bit symmetric encryption if you have equivalently cheap quantum computers.

Even ignoring that we don't currently have any usable quantum computers and there's no reason to believe they would be affordable, let alone cheap, this mean AES-256 is fine.

[less_less]

Grover's algorithm is not quite as powerful as popularly described. In particular, it (roughly) divides the number of times you need to run AES by the number of times you run it sequentially. So it effectively square-roots the time requirement rather than the difficulty, and those are very different if the attack is parallel.

Eg if you were planning on breaking AES-128 by running 2^30 cores for 2^98 AES calls, it now only takes about 2^49 calls per core (2^79 total effort) plus the overhead of Grover's algorithm itself. There are also huge overheads from running everything on a quantum computer, some of which are theoretically avoidable (100x cost for error correction; gates take one clock cycle) and some of which are probably not (you must rewrite AES so that all computations are reversible). So breaking AES-128 might eventually be feasible, but AES-192 probably would not be.

There is a theoretical barrier against efficiently parallelizing Grover: all generic quantum brute-force algorithms (the kind that would work against a random function in a black box) require Omega(searchspace / depth) queries, at least for some model that may not quite match reality. (Edit: Omega and not O, since it's a lower bound)

Of course, AES isn't a random function in a black box, so there may be better attacks against it, but I'm not aware of any.