What are we going to do with quantum computers?
technologyreview.com
technologyreview.com
We've conducted ourselves for decades underthe assumption that the cryptographic invariants securing internet communications would hold. Looking to the future, we can switch to quantum-resistant ciphers and go on with our lives.
But the past? Mass decryption of archived communication would lead to learning things we never wanted to know. It would cause economic ruin, social turmoil, and worse on a huge scale. And it may now be inevitable. Everyone has secrets.
We should start moving toward quantum-resistant cryptography now so that by the time these machines become practical, sensitive information will have fallen out of most archives.
I think we actually are. NIST already gathered submissions for post quantum crypto[0] last year.
And people like djb are also clearly interested in it[1][2].
[0] https://csrc.nist.gov/projects/post-quantum-cryptography/rou...
If new network infrastructure is required, I can't imagine how we would ever get quantum computer resistant cryptography before it's way too late.
No. We just need to switch from existing public-key cryptographic algorithms to quantum-resistant public-key cryptographic algorithms. There are already a variety of such algorithms developed (see https://en.wikipedia.org/wiki/Post-quantum_cryptography). All that remains is to study them further and agree on a standard.
Symmetric ciphers such as AES are already quantum-resistant for 256-bit keys. (Grover's algorithm is the best known quantum attack for such algorithms. Cracking an N-bit key classically is approximately as hard as cracking an (N/2)-bit key on a quantum computer with Grover's algorithm.)
To break contemporary public-key crypto you need quantum computers orders of magnitude larger than anything built so far. To break something like Curve25519 you need 1600 or so logical qubits.
My gut feeling is that this question right now is like asking for Moore's Law in 1950.
The hard part is figuring out the best general engineering approach, i.e. what to make the qubits out of, how to entangle them, what materials to use. Once you figure that out and do small demonstration units I'd fully expect the right design to be scalable quickly. But the actual production of the right design should be less of a barrier.
Still a barrier, but nowhere near 50s levels.
I couldn’t understand how that worked and for the longest time thought either I was really stupid, or the whole world had lost its mind promoting something that obviously could not be true.
It took a couple of years for me to realize that it simply wasn’t a “law” in the first place and to recognize differences in academic speak and popular media.
It's not that uncommon for new technologies to experience exponential improvement for some period of time. It doesn't seem like an unreasonable question to ask.
I don't think this is true at all. No one has the capacity to store everything and governments would be the ones that come closest. Why would they cause all those bag things? It does not make sense.
I am not saying they won't use it, but it will not have nearly those effects that you list.
Don't be so sure about that: https://en.wikipedia.org/wiki/Utah_Data_Center
2. My point was that there's no way NSA will use the data stored there in ways that will give the effects mentioned in the grandparent post.
What?
The only thing THEY will gain is putting together the missing pieces of some puzzles (or discover new ones pieces/puzzles).
That would involve both the hardware and software is ready for production and use.
So it's my thing or is it MIT Technology Review writers who are misleading common people into thinking quantum computing will be usable in a couple of years?
https://www.brainyquote.com/quotes/arthur_c_clarke_100793
> On the other hand I'm sure you could find lots of other achievements where some scientists were denying it was possible right up to the point it was achieved.
True and I'm very aware that I'm creeping towards the age where I'm likely to be on the wrong side of these debates. (Not that I'm distinguished or even a scientist)
However - the distinguished, elderly scientists are sometimes right.
Granted, you can't be proved correct if you say some action is impossible as someone can always wait to see if you're wrong.
Sure, we can all think of cases where someone said something was impossible and then eventually it was achieved.
But are there any cases where the expert consensus on the physical possibility of something wasn't established until it was achieved in practice? I can't think of one off the top of my head.
Nuclear energy? No, the physical possibility of this was understood in the thirties; the objection was that, as one scientist put it, you would have to turn a whole country into a uranium refinery. Which wasn't exactly wrong; the Manhattan project took engineering resources in the ballpark of a small country.
Supersonic flight? No, artificial objects had been going supersonic for centuries.
Spaceflight? No, the physics of this was well understood long before it was achieved.
Any that I'm missing?
But I think there is a consensus on the physical possibility of quantum computing in principle. The [threshold theorem](https://en.wikipedia.org/wiki/Quantum_threshold_theorem) is very convincing.
"I, at any rate, am convinced that He [God] does not throw dice."
The "does not play dice" was mostly with regard to Heisenberg, in which he was determined to find a way to avoid the predicted lack of predictability of the future.
Also, if it's not "crypto season", what is it actually, nano, cryo, opto, ..?
"Yet only now, after decades of gradual progress, are researchers finally close to building quantum computers powerful enough to do things that conventional computers cannot."
And there are more parts of the article that make clear that it's definitely not possible to buy a quantum computer any time soon.
Granted, it's not the best headline ever, but it's a decent article.
For most people "close to building" means 1 or 2 years.
This is just a wild guess without much knowledge of quantum computing at all though.
Also if I'm not mistaken ray tracing scales well with conventional computers : the quality of your output is proportional to the number of rays you simulate. So it's not an appropriate use case for quantum computers.
Quantum computers don't really compute many things in parallel. Or rather, they do, but the problem is getting the results out.
To stick with your ray tracing question, you could probably indeed trace an exponentially (in the size of the computer) number of rays, but at the end you have to do go back to the classical world to actually read out data, and you'd essentially be able to only read out the result of one ray picked at random.
Quantum computers are only know to provide exponential speedups in cases where there is some algebraic structure to exploit when condensing the exponentially many computations down to a single result. That's why you can get an exponential speedup for factoring or discrete logarithm, but not for symmetric cryptography or really any other useful problem (except for the kind of circular problem of simulating quantum systems).
That's what makes me personally hope that quantum computers will never scale. The likely outcome of quantum computing is the worst of all worlds: all known practically useful cryptography will be broken, and practically nothing will really benefit.
I agree with you on the technical points, but I think this is a tad pessimistic.
Firstly, by the time we have quantum computing we will probably also have quantum cryptography. Quantum cryptography is secure against quantum computers and is also vastly more simple than existing crypto (no complicated algorithms to mess up). So I expect cryptography to improve.
Secondly, while quantum computers won't be useful for everything, they will have amazing applications. The "simulating quantum systems" thing will be hugely useful for studying chemistry. And Grover's algorithm will provide a significant speedup for a whole host of interesting problems, especially in machine learning.
Can you explain this statement? I understand that algorithms such as RSA might require particular padding or what have you to be secure in practice, but is quantum-resistant crypto much different?
Does it change your thoughts on the utility of quantum cryptography?
What I'm talking about is "quantum cryptography", in which qubits are actually used in the protocol. Quantum cryptography is also known to be secure against quantum computers (indeed it's secure against arbitrary amounts of computing resources, unless our theories of physics are wrong).
It's also simpler than RSA or elliptic curves, so I hope that (after the kinks are worked out) it will also be less susceptible to bad implementations and side-channel attacks.
>Not to mention a small initial secret
This is interesting, what are you referring to here?
As soon as there's any device between you and the recipient that breaks the entanglement, all the guarantees of quantum encryption go out of the window, and it's possible to attack the comms at that retransmission point.
No, the retransmitters can preserve the entanglement (and A and B can verify that this has been done).
In fact (providing qubits can be stored) the transmission can be done indirectly and in advance.
The telecom company produces lots of entangled qubits and gives a bunch to each customer, keeping half of each pair for itself. Then when Alice wants to communicate securely with Bob they ask the telecom company to take the corresponding qubits and perform a joint measurement. This entangles Alice's qubits with Bob's (like making a connection at a telephone exchange). Then Alice and Bob can measure their qubits (in various bases) to create a one-time-pad.
The clever thing is that Alice and Bob can (by checking that on a portion of the qubits their results always matched when they used the same basis) verify that they did indeed have maximally entangled qubits and therefore no one was listening-in.
I disagree for two reasons.
First, because there is a huge difference between having a single quantum computer and quantum computers in every household.
Second, because we don't need quantum cryptography, we need post-quantum cryptography. Quantum computers break only asymmetric cryptosystems, but despite common belief, quantum cryptography doesn't solve this! Post-quantum cryptography does, and there is already good promise in this field.
? You might not think that quantum cryptography is likely to be practical soon. But it is definitely resistant to quantum computers.
- https://www.schneier.com/essays/archives/2008/10/quantum_cry...
For symmetric crypto, some schemes will have to be dropped, and others will require larger keys. But we can (for example) just keep right on using AES 256.
For asymmetric crypto, we'll have to switch to some new schemes, but those exist (though I don't know of any current software using them). For example:
https://en.m.wikipedia.org/wiki/Lattice-based_cryptography
The bigger worry I think is what about all of the existing traffic that has been archived?
As for the alternatives to asymmetric crypto: I like lattices, I've studied them a lot myself, though not in a crypto context. But have you looked at the required key sizes of those alternative schemes? They're pretty horrible and not at all comparable to what we have today.
Obviously people will continue research on this, and perhaps something close to elliptic curves in terms of efficiency will be found. I certainly hope so, but I'm not holding my breath.
I agree that archived traffic is an issue as well, but personally I'm more worried about the future than the past.
File encryption, whether it be my entire hard drive, or just my password database, doesn't need asymmetric crypto.
A sibling comment points out one use case for symmetric-only crypto.
I'm also curious what people would actually do if forced to deal with a symmetric-only world.
I think it is more likely that we'd see cumbersome ways of dealing with key distribution than that people would just stop using crypto in all the places we rely on public key schemes today. Think symmetric keys printed on your bank statement (maybe with a qr code?) We'd definitely see it used a lot less than now.
That said, we'd probably have about the same number of people doing end to end email encryption; key distribution with an asymmetric scheme is no picnic either :P.
However currently these computers are constrained by classical memory and read write operations are still classical.
I'm willing to bet it'll be a century more at this rate before quantum computing comes of age.
Since the 40s people have been hyping them without any sort of clear understanding.
Groan: it's going to be Cloud/Big Data/ML/Blockchain hype all over again except possibly worse. I don't mind the technology, but the tsunami of vapid content (and conversation) that comes with it wears me out.
Remember how much effort the British put into making it hard for the Axis to realise that Engima had been cracked. To the extent that they allowed ships to be sunk and sailors to die. If a 3 letter agency does have anything then they are probably hoping to keep that edge for as long as possible.
(This doesn't mean that I believe they do - merely that I don't think it would be immediately obvious if they did)
It could be that they have some super secret projects which are protected by much better security, but I doubt it. If they could be that competent for one project, why not use the same protocols everywhere?
For exactly the reason set out in the post you are replying to, I would think, at least for a while.
Though that approach to security does not always last. The USA almost gave away that it had broken the Japanese navy's most important cyphers through its interception of Admiral Yamamoto.
This is a typo, surely? Quantum computers were first proposed in the 80s.
But tech-hype has always existed, side by side with those claiming tech has maxed out... It's disappointing to see the media even try TBH.
I guess it depends on the specific experimental setup of your quantum computer somehow, but I'm just curious about the real-world speeds. A hypothetical computer that does few steps but takes a minute for each measurement wouldn't be so useful.
Single measurement is like revealing single pixel of a picture. If you do it enough times, you know what's on the picture.
"Logic gates at the surface code threshold: Superconducting qubits poised for fault-tolerant quantum computing"
Campbell et al.
Nature, 2014 From page 9:
Initialization ~50ns
Measurement ~200ns
One-qubit gates ~20ns
Two-qubit gates ~40ns
With error correction... it depends how many spare qubits you have. All the non-trivial operations are done by "magic state distillation", where you produce special states in one part of the computer then consume them to perform the operation elsewhere. The more qubits you have, the more space you can allocate to magic state factories.
For example, a 32-bit addition can be done with 124 |T> states [1]. If you have N qubits allocated to factories then you can expect to get about 100N magic states per second. So if you have a tiny computer with 20 qubits dedicated to a factory, then a single addition will take over half a second. But if you can spare 2000 qubits for factories (about the same amount of qubits you'd need to store the problem in the first place) then you'd be producing T-states at 200KHz and 32-bit-adding at 1600Hz.
Shor's algorithm is, effectively, a single modular exponentiation. Performing an N-bit modular exponentiation requires something like 4N^3 |T> states. So 1024^3*4/200KHz = 6 hours to a factor a 1024 bit key, assuming 2000 qubits on factories and that the other rough numbers are close.
For example take the classic attacks on DLP -- instead of essentially manually factoring the keys we can create a program (Shor's algorithm, etc) that essentially treats the problem of factoring as the task of determining the base frequencies of the key when treating the public component as a wave (at least as I understand it).
On an ideal quantum computer that task should be polynomial complexity, although there's still some (hopefully small) probability of error, but basically you just repeat many times and use a classical computer to verify the solution.
class Qbit
{
var $p;
function randomize($p)
{
$this->p=$p;
}
function observe()
{
if ( $this->p > random() ) $this->p=1;
else $this->p=0;
return $this->p;
}
}
Would it be possible to simulate 'multiqbits' in a piece of code similarly small as the one above?
Here's a start.
I like this one better.
For a memory of N qubits, you need to store the amplitude for each bit configuration, so 2^N numbers. This is totally doable, and people have written quantum computer simulation software.
- A length 2^n array of complex numbers, such that the sum of the norms of those numbers is always 1. Each element represent a possible length n bit string.
- An "observe" method, which returns a given length n bit string with probability equal to the norm of the corresponding complex number in the array.
- Various "transform" methods. These are all linear unitary operators (matrices with special properties) on the array, but I think you can't pick and choose them arbitrarily; see https://en.m.wikipedia.org/wiki/Quantum_gate
All the usual bit operations are valid, but there are operations which don't have classical analogs, like this one in a 2-qbit system: "Maintain the probabilities of 00 or 11, but average the respective probabilities of 01 and 10".
The fact that you're working with complex numbers and not just probabilities is mathematically how entanglement can play a role, but I don't have a good minimal example of how this is helpful.
* The amplitude of a qubit is effectively a complex probability instead of a real one.
* Don't think of an n-qubit machine as having n instances of qubit. The representation you want is essentially:
struct quantum_state {
uint64_t bits;
complex_t amplitude;
};
struct quantum_register {
int num_bits;
size_t num_states;
struct quantum_state *states;
};
From a simulation perspective, quantum computers are just linear algebra operations, albeit over the complex field instead of the reals. The difficulty is that the equivalent vectors and matrices are of exponential size (2^n for an n-qubit computer), and the interesting operations don't exhibit regular patterns that permit aggressive optimization.
The amplitude of a qubit is effectively a
complex probability instead of a real one
As other people pointed out, you may need a factor of 100-1000 more physical qubits to get as many logical qubits.
Well, I don't know enough about quantum computers to be able to tell what's going on here, but "on the verge" and "finally here" sound a bit contradictory. Are we expecting to have useful quantum computers soon, like the article's opening paragraph suggests, or do we already have them, as the title does?
And even these algorithms can help asymptotic complexity, but not solve an NP complete problem in polynomial time.
(Even AES256 is pretty much safe against a quantum attack, since a quantum computer effectively square roots the time complexity, and that just leaves key-exchange protocols, of which several QR-variants exist.)
Personally, I think the hype far outweighs the value, even compared to Big Data/IoT.
Is this a theorem or conjecture?
IE, I was talking about quantum algorithms we have, none of which have done so, not stating the impossibility of such an algorithm.
I am not aware of a proof that comments on whether or not such an algorithm is impossible, however.