Do quantum computers have any affect on the ability to solve the non-linear AES s-box algebraic expression, or does solving it still fall under search algorithms (Grover's)? If quantum computer do help solve it, what affect does this have on AES given that finding the key is still a brute-force search?
Take a look at this chapter (Introduction to post-quantum cryptography by Daniel J. Bernstein). It gives an excellent overview of what is known. (Bottom line, Grover's is the best known today and so this can be thwarted by taking 256 bit keys.)