Why do you say that? Is it because 100-qubits roughly corresponds to attacking 100-bit keys? I am not sure if that intuition is correct. AFAIK, quantum computing is supposed to help with mathematical cryptanalysis like breaking Discrete Log and Factoring. I do not think it will have any effect on attacking symmetric primitives such as AES and SHA.

In symmetric primitives, Grover is the useful quantum algorithm. It reduces unordered (read: brute-force) searches from 2^n to 2^(n/2) operations, and requires n qubits. This is a big deal one the 64-128 bit range: it makes very costly or impossible searches possible. This is one of the reasons it is sensible to want 256-bit symmetric ciphers today.

But when it comes to public-key crypto, you need more. Shor's algorithm (applicable to integer factorization, but also to discrete logarithms and some other schemes) originally needed 2n qubits to factor an n-bit number. Later improvements put this somewhere over n qubits for an n-bit number. So RSA-1024 would need at least a 1024-qubit machine. Elliptic curves need a small multiple (6, last I checked) of the bitsize of the prime modulus, so the same 1024-qubit machine might be able to break a 160-bit elliptic curve.

Thanks for the info. I forgot about the Grover speedup. I think it would still be amazing to get 2^64 operations on a 128-qubit quantum computer to break current 128-bit schemes. It seems like quite a tall order.

Does using Shor to attack EC discrete log require us to work in the group of integers mod p? If it can work with the generic group then you might not need to go beyond 160-qubits. (But all of the above reasoning is based off the wiki article, so I might be mistaken.)

You work modulo p, yes, but the group is the set of points of the curve. The qubit bottleneck seems to be the Extended Euclidean Algorithm to perform modular divisions, which requires the greatest amount of space. Check [1, §6.2] for details.

[1] http://arxiv.org/abs/quantph/0301141