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.
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.
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.
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.
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.
You have to implement quantum error correction on these 49 physical qubits to avoid errors, which leaves you with a lot fewer logical qubits. Also you have to take into account the constants.
So how many "effective" qbits are there in these systems that I see hyped up? Intel's press release for its 49-bit system [1] does not mention anything about "logical qubits". IBM's 50-qubit system [2] similarly does not hedge here.
I see a question on stack overflow [3] that has some information, and actually claims an O(n) bound on the number of qubits, which is much tighter than the O(nlogn) number, but that just makes my question about why the record for Shor's algorithm has not yet been broken.
I mean, forget about "quantum supremacy" -- where quantum anything?
It's actually a reasonable way to play around with simulations of quantum algorithms, much nicer than multiplying huge matrices which is typically what you'd otherwise do when learning. But it is a little silly that we have a quantum IDE before a usable quantum computer has been built.
I think that the idea is that if these machines will be ever built then there would be at least some work force that has at least some idea what to do with them.
Also Microsoft will have some advandage. This is probably the main motivation here.
This of course does not guarantee that the interface of an actual QC would be anything like this.
Ada Lovelace is said to have written the first computer algorithm for the Analytical Engine even though it wasn't built, though I did some googling and wasn't able to find the text itself.
Forget about quantum computing at scale: has anyone actually developed a functional quantum device that unequivocally proves that it's both viable and that it solves a problem faster than conventional physics can explain? To the best of my knowledge, the answer is no. It's premature to invest heavily in something this speculative. I'm all for investing in research and science for the sake of science, but we didn't invest billions in going to the moon before we knew that rockets worked.
We have demonstrated systems with a handful of quantum bits that worked as expected. There is a tremendous amount of work left before anything practical can be build, afaik.
We're really close. Actually Intel announced a 49-qubit quantum computer which would have beaten existing classical platforms, but just after that, another team at IBM [edit: not Intel] made an algorithmic breakthrough and simulated 56 qubits on a classical supercomputer. https://en.wikipedia.org/wiki/Quantum_supremacy
Can this 56 qubit computer break DES faster than conventional computers? Could it break an arbitrary 56 bit block cipher faster than conventional computers? Or is it limited in a way which limits it to specific problems? I suspect the answer is the latter.
No, 56 qubits is still much too small to break any useful encryption. And your second point is true too - these are not general purpose quantum computers and can't run arbitrary quantum algorithms.
I'm not expecting quantum computers to actually do anything faster than conventional computers for many years, and that's fine; making things incrementally better is usually much easier than making them work in the first place.
People have been simulating quantum circuits as proof-of-concept for quantum algorithms, and D-Wave has a "quantum annealing" machine (although a preliminary glance suggests there's skepticism about whether that involves any provable quantum effect), and there are frequent reports about pushing the limits of entangled qubit count, but I'm wondering if anyone's actually made a quantum device that solves even a specific problem faster than non-quantum physics would allow (hence my original comment along those lines), rather than faster than conventional hardware (which could take years or decades to match).
To your point, we invested billions in rockets before we knew we would go to the moon! Of course rockets were useful for moving bombs quickly in the meantime.
Quantum computers won't be faster at solving conventional problems, but they will be useful for simulating quantum behaviors related to chemistry and cosmology. Maybe we'll make sense of dark matter, who knows? I'm in the camp that we'll develop totally new problems to solve that didn't fit the domain of digital computers.
From a singular technology perspective, indeed it seems like investing a lot of money into a hypothetical device. However, there are many other factors you have to consider.
1. Quantum computing is a cryptographic arms race at the moment. One country can choose not the invest in it, but assuming QCs work, whichever country makes one first, is going to win big time. In a way, its a national security issue. Nobody wants to be left behind. Funding levels have to reflect this.
2. Many different architectures for QCs are being researched on, and in each area we have made tremendous advancements in new techniques of quantum-level-system control and new ways of nano scale manufacturing etc. The feedback alone from these advancements will enrich and enable many other areas of science and technology. For instance, the development of photonic quantum computation also advances the development of optical classical computer as the basic architecture is very similar.
3. Many physicists like myself don't care too much about actually building quantum computers, though it would be nice. Whether or not QCs are possible, just forcing ourselves to think about physical reality from a computational and information theoretic perspective has resulted in massive advancements in physics, a field which had pretty much stagnated since the 80s. The ideas generated from studying quantum information and computation have percolated into other areas of physics such as gravitation and the structure of spacetime. And its not sufficient to just think about QCs in the abstract. New ideas such as novel error correction codes are generated when physicists are forced to think about specific architectures and their limitations and/or real problems faced in the lab.
A "looming quantum engineering gap"?
Seems like you need a working technology before you can have a looming engineering gap. Which we don't have yet.
I'm surprised they didn't mention a looming gap of cryogenic maintenance technicians. I have no idea how a server farm operating at 15 millikelvin is to be maintained.
For the skeptical, there are two quantum computing job tracks which can operate independently for the next while:
(1) The engineering and basic physics research necessary to build a real, working quantum computer of high enough quality (low error rate) and size (number of qbits) for real-world use. Scott Aaronson believes we won't have a sufficiently-advanced quantum computer to, for example, run Shor's algorithm against a real-world key size for at least 15 years.
(2) The development of quantum algorithms, error-correction schemes, cryptography, and as-yet-unknown use-cases; the implementation thereof in a large, well-designed software library; finally, the development of education materials to ease onboarding of the existing software engineering workforce to quantum computing. Microsoft has an actual quantum software engineering job listed, at this very moment: https://careers.microsoft.com/us/en/job/503847/Quantum-Softw...
Now, it's completely possible that (1) just won't pan out and we'll never, ever have a quantum computer advanced enough to work on real-world problems, in which case all investment into both (1) and (2) will have been a complete waste. However, given that we have good reason to believe (1) will succeed, why should we put (2) on hold for the next 15 years? Do we really want to finally have a shiny new quantum computer, then not have anything to run on it?
For an overview of the current state of quantum computing and what we can do with current NISQ (noisy intermediate-scale quantum) computers, there's a good survey paper by John Preskill called Quantum Computing in the NISQ era and beyond: https://arxiv.org/abs/1801.00862
In my opinion, browse youtube for "microsoft q#" and check out their quantum development kit.
There will be the quantum mechanic quants that build new algorithms, but I think the Q# kit will be the SciKit of quantum and getting familiar with the classes and methods they provide will be a good step towards future-employability.
Can someone knowledgeable in the field explain to me what the implications of a deterministic universe would be for quantum computing? Correlated noise ruining any useful computation?
(I know about Bell's theorem but I think it uses circular reasoning so I am not a fan).
> In theory, a quantum machine with just a few hundred qubits should be able to run calculations that would be inconceivable using traditional hardware.
According to https://en.wikipedia.org/wiki/Timeline_of_quantum_computing Google has a 72-qubit system which I would expect to already be game changer if the above quote is true, but have heard about the applications of quantum computing only in the future tense. Does the power of a quantum computer scale linearly with number of qubits? Does the difficulty in manufacturing scale linearly with number of qubits?
In the quote, "few hundred qubits", qubits are logical qubits. Google's 72-qubits are physical qubits. You implement error correction on the physical qubits, after which you are left with a lot fewer logical qubits, to do your actual computation with.
> Does the power of a quantum computer scale linearly with number of qubits?
It scales linearly with the number of logical qubits, in the same sense the power of a turing machine scales linearly with the size of the tape. Also, for a realistic system of hundreds of qubits, you will need tens of thousands of physical qubits.
> Does the difficulty in manufacturing scale linearly with number of qubits?
If you want the ability to do entangling operations on any two qubits, however far apart they are physically, the manufacturing difficulty scales quadratically with the number of qubits at least. However, you can choose to only have the ability to do entangling operations on near by qubits, and use swap operations to move the state of the qubits around. This will reduce manufacturing difficulty scaling, but will increase the time of any computation you perform.
53 comments
[ 4.9 ms ] story [ 144 ms ] threadSeems we should be investing a tremendous amount into quantum computing research publicly.
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.
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.
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.
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.
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.
Number of bits.
I see a question on stack overflow [3] that has some information, and actually claims an O(n) bound on the number of qubits, which is much tighter than the O(nlogn) number, but that just makes my question about why the record for Shor's algorithm has not yet been broken.
I mean, forget about "quantum supremacy" -- where quantum anything?
[1] https://newsroom.intel.com/news/intel-advances-quantum-neuro...
[2] https://www.technologyreview.com/s/609451/ibm-raises-the-bar...
[3] https://stackoverflow.com/questions/41397576/how-many-qubits...
Can't wait to see the Intelli-J plugin, though!
https://www.microsoft.com/en-us/quantum/development-kit
It's actually a reasonable way to play around with simulations of quantum algorithms, much nicer than multiplying huge matrices which is typically what you'd otherwise do when learning. But it is a little silly that we have a quantum IDE before a usable quantum computer has been built.
Also Microsoft will have some advandage. This is probably the main motivation here.
This of course does not guarantee that the interface of an actual QC would be anything like this.
Nonsense! With a quantum debugger, we'll finally be able to find out if Schrodinger's cat is alive or dead!
People have been simulating quantum circuits as proof-of-concept for quantum algorithms, and D-Wave has a "quantum annealing" machine (although a preliminary glance suggests there's skepticism about whether that involves any provable quantum effect), and there are frequent reports about pushing the limits of entangled qubit count, but I'm wondering if anyone's actually made a quantum device that solves even a specific problem faster than non-quantum physics would allow (hence my original comment along those lines), rather than faster than conventional hardware (which could take years or decades to match).
Quantum computers won't be faster at solving conventional problems, but they will be useful for simulating quantum behaviors related to chemistry and cosmology. Maybe we'll make sense of dark matter, who knows? I'm in the camp that we'll develop totally new problems to solve that didn't fit the domain of digital computers.
1. Quantum computing is a cryptographic arms race at the moment. One country can choose not the invest in it, but assuming QCs work, whichever country makes one first, is going to win big time. In a way, its a national security issue. Nobody wants to be left behind. Funding levels have to reflect this.
2. Many different architectures for QCs are being researched on, and in each area we have made tremendous advancements in new techniques of quantum-level-system control and new ways of nano scale manufacturing etc. The feedback alone from these advancements will enrich and enable many other areas of science and technology. For instance, the development of photonic quantum computation also advances the development of optical classical computer as the basic architecture is very similar.
3. Many physicists like myself don't care too much about actually building quantum computers, though it would be nice. Whether or not QCs are possible, just forcing ourselves to think about physical reality from a computational and information theoretic perspective has resulted in massive advancements in physics, a field which had pretty much stagnated since the 80s. The ideas generated from studying quantum information and computation have percolated into other areas of physics such as gravitation and the structure of spacetime. And its not sufficient to just think about QCs in the abstract. New ideas such as novel error correction codes are generated when physicists are forced to think about specific architectures and their limitations and/or real problems faced in the lab.
I'm surprised they didn't mention a looming gap of cryogenic maintenance technicians. I have no idea how a server farm operating at 15 millikelvin is to be maintained.
(1) The engineering and basic physics research necessary to build a real, working quantum computer of high enough quality (low error rate) and size (number of qbits) for real-world use. Scott Aaronson believes we won't have a sufficiently-advanced quantum computer to, for example, run Shor's algorithm against a real-world key size for at least 15 years.
(2) The development of quantum algorithms, error-correction schemes, cryptography, and as-yet-unknown use-cases; the implementation thereof in a large, well-designed software library; finally, the development of education materials to ease onboarding of the existing software engineering workforce to quantum computing. Microsoft has an actual quantum software engineering job listed, at this very moment: https://careers.microsoft.com/us/en/job/503847/Quantum-Softw...
Now, it's completely possible that (1) just won't pan out and we'll never, ever have a quantum computer advanced enough to work on real-world problems, in which case all investment into both (1) and (2) will have been a complete waste. However, given that we have good reason to believe (1) will succeed, why should we put (2) on hold for the next 15 years? Do we really want to finally have a shiny new quantum computer, then not have anything to run on it?
For an overview of the current state of quantum computing and what we can do with current NISQ (noisy intermediate-scale quantum) computers, there's a good survey paper by John Preskill called Quantum Computing in the NISQ era and beyond: https://arxiv.org/abs/1801.00862
There will be the quantum mechanic quants that build new algorithms, but I think the Q# kit will be the SciKit of quantum and getting familiar with the classes and methods they provide will be a good step towards future-employability.
(I know about Bell's theorem but I think it uses circular reasoning so I am not a fan).
According to https://en.wikipedia.org/wiki/Timeline_of_quantum_computing Google has a 72-qubit system which I would expect to already be game changer if the above quote is true, but have heard about the applications of quantum computing only in the future tense. Does the power of a quantum computer scale linearly with number of qubits? Does the difficulty in manufacturing scale linearly with number of qubits?
[0]: https://www.sciencenews.org/article/google-moves-toward-quan...
> Does the power of a quantum computer scale linearly with number of qubits?
It scales linearly with the number of logical qubits, in the same sense the power of a turing machine scales linearly with the size of the tape. Also, for a realistic system of hundreds of qubits, you will need tens of thousands of physical qubits.
> Does the difficulty in manufacturing scale linearly with number of qubits?
If you want the ability to do entangling operations on any two qubits, however far apart they are physically, the manufacturing difficulty scales quadratically with the number of qubits at least. However, you can choose to only have the ability to do entangling operations on near by qubits, and use swap operations to move the state of the qubits around. This will reduce manufacturing difficulty scaling, but will increase the time of any computation you perform.