If your ssh key relies on RSA, then yes, you're relying on the difficulty of factoring numbers; which Shor's algorithm can perform efficiently. But only if the

If your ssh key relies on RSA, then yes, you're relying on the difficulty of factoring numbers; which Shor's algorithm can perform efficiently. But only if the quantum computer has enough qubits. The needed number of qubits needed to factor is a multiple of the rsa key length. Unlike a regular computer, where you can finagle two computers with 2 gigs of memory to work like a single machine wiht 4 gigabytes of memory, so you can't just merge two 1024 qubit computers to get a 2048 qubit computer. And we're a long way off to having anything close to that. The simplest solution is simply to increase the size of the key beyond that of the most advanced quantum computer (which is essentially today's approach ;) ). Also, you just need to exchange a symmetric key; Shor's algorithm is a special case, you don't get the exponential -> polynomial speedup[1] to encryption algorithms in general. So once you deliver the symmetric key in a secure way, using a quantum resistant algorithm, you can resume business as usual. [1] Though in brute force searches, you can reduce the effective key length by 2. https://en.wikipedia.org/wiki/Grover%27s_algorithm https://en.wikipedia.org/wiki/Grover%27s_algorithm