My understanding of Quantum Computers is that the first country to successfully develop quantum computers at scale will experience dominance in cryptography until other nation-state actors can catch up. Isn't quantum technology a national security threat then?
Seems we should be investing a tremendous amount into quantum computing research publicly.
First, quantum computers don't scale as well as classical computers. You can take two 64-bit computers, connect them together and emulate a 128-bit computer, in classical computers. Or you could take one 64-bit computer and emulate 128-bits taking twice as long to compute it. But in classical computers, if you need 128 qubits for a computation, having even a 127-bit qubit computer leaves you dead in the water. In practical terms, Shor's algorithm requires O(n lg n) qubits, so you need thousands of qubits to try to break computer. You also can't parallelize Grover's algorithm by farming it out to N quantum computers.
Second, only a relatively small (but important) set of cryptography is actually affected by quantum computers. Symmetric ciphers generally only admit the quadratic speedup by Grover's algorithm, so breaking AES-128 requires 2^64 time on a quantum computer instead of 2^128 (and as mentioned above, having more computers doesn't help speed up the search). Where exponential speedup is available is mostly in public-key cryptography and key-exchange protocols. Forward secrecy (which is increasingly the norm in TLS connections) essentially means you have to crack each individual key exchange to read past conversations, not just the private keys.
Third, as others have mentioned, people are working on post-quantum cryptography. By the time that practical quantum computers for breaking RSA/ECC crypto come around, it's likely that the most useful things to break won't be breakable.
> In practical terms, Shor's algorithm requires O(n lg n) qubits
Wait, is that 'n' the number being factor or the number of bits?
If it is the number being factored, then quantum computing will effectively never be a threat; since you would need 200 million bits in order to factor a 32-bit number.
If it is the number of bits then why haven't we seen any new results? The current record is held by factoring 21, a 5 bit number. There are numerous claims that people have built quantum computers in the 49-qubit range. Why aren't we seeing successful factorings of 17-bit numbers as a matter of course?
I don't count here the extension of the 21 result to larger numbers that yield the same period-finding problem, but rather direct approaches using the quantum computers that exist now.
This is a very good point. Before seeing this point, my initial reaction was, "Nope, it's way too early to worry about quantum computing." But, the security cost / risk of being few years late can be so high for nations that they don't have a choice. They have to invest in it early.
I'd love to hear from crypto expert HNers about what the industry is doing to prepare for the possibility of quantum computing disrupting current crypto solutions and if there are any interesting (long-term) startup opportunities.
A _cheap_ fast large quantum computer lets you break modern hybrid cryptography in real time. That is, you can choose to eavesdrop conversations or you can MITM them seamlessly. You also break forward secrecy (you can read conversations recorded today even though their participants can no longer read them by that point).
If, as seems rather more likely, your quantum computer is expensive you can't afford this. You have to pick what to see. If it isn't fast you can't MITM (imagine you're trying to connect to Hacker News and the browser mysteriously stalls for ten minutes, you're going to retry, and either it stalls again or this time they don't MITM you) and you have to pick what to see now versus later. And of course if it isn't large it's altogether useless against modern cryptography.
The chance a foreign adversary goes from zero to fast, cheap and large overnight is tiny. Its like going from the electric lightbulb straight to the integrated circuit before anybody else even had the electronic valve.
Cryptography is not that big of a deal imho. Post quantum cryptography is already a hot research area https://en.wikipedia.org/wiki/Post-quantum_cryptography so we'd probably figure something out to keep the very important secrets secret. More important is the tremendous advantage quantum computers will give is in materials science, chemistry, and biology. Suddenly we'll be able to efficiently simulate large molecules and their interactions. This will speed up research in those areas a lot because you need fewer difficult experiments. As I see it, scalable quantum computers are the key to Drexler type nanotechnology based on proteins.
> More important is the tremendous advantage quantum computers will give is in materials science, chemistry, and biology. Suddenly we'll be able to efficiently simulate large molecules and their interactions.
Is that true? It seems to me that to simulate those sorts of bulk materials or biopolymers with a quantum computer would require as many qbits as exists in the material. at that point the most effective quantum computer for that molecule becomes the molecule itself.
jcranmer|7 years ago
First, quantum computers don't scale as well as classical computers. You can take two 64-bit computers, connect them together and emulate a 128-bit computer, in classical computers. Or you could take one 64-bit computer and emulate 128-bits taking twice as long to compute it. But in classical computers, if you need 128 qubits for a computation, having even a 127-bit qubit computer leaves you dead in the water. In practical terms, Shor's algorithm requires O(n lg n) qubits, so you need thousands of qubits to try to break computer. You also can't parallelize Grover's algorithm by farming it out to N quantum computers.
Second, only a relatively small (but important) set of cryptography is actually affected by quantum computers. Symmetric ciphers generally only admit the quadratic speedup by Grover's algorithm, so breaking AES-128 requires 2^64 time on a quantum computer instead of 2^128 (and as mentioned above, having more computers doesn't help speed up the search). Where exponential speedup is available is mostly in public-key cryptography and key-exchange protocols. Forward secrecy (which is increasingly the norm in TLS connections) essentially means you have to crack each individual key exchange to read past conversations, not just the private keys.
Third, as others have mentioned, people are working on post-quantum cryptography. By the time that practical quantum computers for breaking RSA/ECC crypto come around, it's likely that the most useful things to break won't be breakable.
andrewla|7 years ago
Wait, is that 'n' the number being factor or the number of bits?
If it is the number being factored, then quantum computing will effectively never be a threat; since you would need 200 million bits in order to factor a 32-bit number.
If it is the number of bits then why haven't we seen any new results? The current record is held by factoring 21, a 5 bit number. There are numerous claims that people have built quantum computers in the 49-qubit range. Why aren't we seeing successful factorings of 17-bit numbers as a matter of course?
I don't count here the extension of the 21 result to larger numbers that yield the same period-finding problem, but rather direct approaches using the quantum computers that exist now.
sinatra|7 years ago
I'd love to hear from crypto expert HNers about what the industry is doing to prepare for the possibility of quantum computing disrupting current crypto solutions and if there are any interesting (long-term) startup opportunities.
tialaramex|7 years ago
If, as seems rather more likely, your quantum computer is expensive you can't afford this. You have to pick what to see. If it isn't fast you can't MITM (imagine you're trying to connect to Hacker News and the browser mysteriously stalls for ten minutes, you're going to retry, and either it stalls again or this time they don't MITM you) and you have to pick what to see now versus later. And of course if it isn't large it's altogether useless against modern cryptography.
The chance a foreign adversary goes from zero to fast, cheap and large overnight is tiny. Its like going from the electric lightbulb straight to the integrated circuit before anybody else even had the electronic valve.
adrianN|7 years ago
dnautics|7 years ago
Is that true? It seems to me that to simulate those sorts of bulk materials or biopolymers with a quantum computer would require as many qbits as exists in the material. at that point the most effective quantum computer for that molecule becomes the molecule itself.