[gizmo686]

The (provably) best "general purpose" quantum algorithm is Grover's algorithm. The problem it solves is as follows:

Given an arbitrary function f(x), and a desired output k, find the unique input z such that f(z)=k.

We can see that using classical computers, this problem is O(n), where n is the size of the domain of f. However, Grover's algorithm can solve this problem in O(sqrt(n)). It has been shown that O(sqrt(n)) is the best possible solution to this problem on a quantum computer.

This means that quantum computers effectively halve the key-size for a brute force attack (and probably most other types), but doing any better than this would require exploiting some structure of the cryptosystem you are trying to break. To my knowledge, no such structure has been demonstrated for any major symmetric encryption algorithms.

[Others]

That's really interesting! I have only a passing education in quantum computers, which is why my comment is so devoid of detail... I really should learn more.

[marcosdumay]

Wait, it has been proved that QP != EXP?

That's great! Do you have any pointers?

EDIT: Wikipedia has pointers. It's not exactly what I thought at first. The paper: http://www.cs.berkeley.edu/~vazirani/pubs/bbbv.ps