Will quantum computers render AES obsolete?

Quantum computing will change the encryption game, but it is not yet clear how much it will change. It's not clear because we are not yet certain what sorts of problems quantum computers can solve. As mentioned, RSA is dramatically weakened by quantum computing because the factoring of primes can be done in polynomial time using Shor's Algorithm. However, not all cryptographic routines are known to be as weak vs. quantum computing.

You may have heard of P (polynomial time), NP (nondeterministic polynomial time -- problems that given the right answer can be checked in polynomial time), and NP-Complete (the hardest NP problems). Prime factorization of large composite numbers is known to be an NP problem and is thought by many to not be P problem. That means a conventional computer would most likely¹ need super-polynomial time (at best sub-exponential time like GNFS) to do the factorization and RSA encryption depends on this. NP-complete is a slightly more demanding class of problem. Any instance of an NP problem can be reduced to an instance of an NP-complete problem. (This is true even if the NP problem is another NP-complete problem.) This means if you ever found a polynomial time solution for an NP-complete problem, you would have a polynomial time solution for every NP problem. If you did so using a classical computer, you would have proven P = NP.

Quantum computers have their own complexity class. BQP is the class of problems that can be [statistically] solved by a quantum computer in polynomial time. It is known that factorization is in BQP, because we have Shor's algorithm. What is yet unknown is whether BQP contains NP-complete or not. It is currently theorized that it does not, meaning there are NP-complete problems that still take exponential time, even with a quantum computer, but the mathematicians are still crunching away at that theory.

Integer factorization sits in an interesting middle ground. We know it is part of BQP (because we found Shor's algorithm). We also know that it is a problem within NP (it is NP because the factorization can be proven in polynomial time just by multiplying the numbers back together). What we don't yet know is whether it is P, NP-but-not-P, or NP-complete. Nobody has been able to prove it one way or another. It could actually be a P problem, solvable with a classical computer in polynomial time, making it very weak for encryption purposes. It could be a NP-complete problem, which given that we know it is in BQP, would imply that quantum computers can solve any NP problem in polynomial time, which would be a major blow to cryptography in general.

Many upcoming encryption algorithms are starting to use other problems besides prime factorization as their root. In particular, a set of problems based on lattices are thought to be particularly hard to break using quantum computers. If all NP problems are part of BQP, this won't help any, but we're still figuring that detail out to this day.

As it turns out, AES is not affected by Shor's algorithm. Grover's algorithm allows brute-forcing an n-bit key in O(2^n/2) time instead of the O(2ⁿ) time required by classical computers. Therefore, an 128-bit AES key could be brute forced in O(2⁶⁴) time by a sufficiently powerful quantum computer that can do Grover's algorithm with 128+ qubits for 2^64 time.

¹ The wise and challenging commenters below are picking away at the imprecision in my wording. Technically it is not known whether NP problems requires exponential time or not. It is possible that the NP class of problems and the P class of problems are the same. However, most mathematicians believe it is much more likely that P != NP, simply because so far it doesn't look like it. If we want to talk in betting terms, just look at how much you could make answering the question. if you prove P and NP are distinct, you can earn the Clay prize of a million dollars, and maybe get a cushy job offer for being so smart. If you prove they are the same, I would expect the NSA to be willing to pay quite a lot more for you to be silent about your discovery, and instead hand over your papers to their mathematicians.

If you are very interested in the topic of quantum computing and encryption, I highly recommend reading up on the different complexity classes such as P and NP. They're worth your time.

It's not impossible to crack any of those algorithms. The problem is not whether you can brute force AES or not, it's about how much time it would take and whether if it is feasible or not.

If you want to crack AES with brute force using normal computers, it would take you to search 2^128 keys which will require minimum 2^128 operations.

On the other hand, using quantum computer and search algorithm such as Grover's algorithm you will be able to go through the same number of keys in (2^128)^0.5 operations.