Combining classical attacks and quantum cryptanalysis I'm regularly reading that AES-256 is secure against quantum computers because Grover's algorithm will only halve the key strength (i.e. "only" require $\sqrt{2^l} = 2^{l/2}$ operations instead of the full $2^{l-1}$ operations required to brute force the key).

However, would it be possible that classical attacks on symmetric ciphers such as AES could be sped up using quantum computing based algorithms? Is it possible / likely that the security of a block cipher is degraded more severely (e.g. by more than an additional 2 bits strength) if or when capable quantum computers become available?
The short answer is: Of course! Why not! 

It is pretty easy to build an artificial secret key encryption scheme that is based on RSA and breaks if the adversary has a quantum computer*. Of course no one would want to build a symmetric primitive out of number theoretic assumptions as that would defeat the main purpose of being far more efficient than asymmetric crypto (the usual exceptions left aside...VSH...). However, symmetric primitives might provide exploitable structure that we just did not find yet. Indeed, in a far stronger security model where the adversary gets quantum access to honest parties (i.e., the CPA oracle) one can actually break several secret key encryption schemes as they are vulnerable to period finding algorithms. Therefore, the conventional effort of cryptanalyzing symmetric primitives has to be enhanced by the study of quantum algorithms.

[*] capable of running Shor's algorithm, which breaks RSA.