[genewitch]

This is the first time in nearly 30 years I've ever heard the claim that you only need 18-20 qubits for something like a 256 bit key.

I've only ever seen the claims of 1:1 key bit to qubits. Aren't there existing claimed quantum computers with 20 qubits? Isn't Canada's machine an order of magnitude more qubits?

[red_admiral]

I think it matters not only how many qubits you have, but how they are "connected". As far as I know, it's a far easier problem to put N qubits in a chain with O(N) connections, than it is to have N qubits with O(N^2) connections to form a complete graph. And I believe the second example is what you need to do Shor's algorithm.

[ivlad]

I am sorry, I should’ve read it twice before posting. I meant, QC to attack longer keys should be bigger proportionally. Number of operations is logarithmic. Silly me.