17
$\begingroup$

The cryptographic world has been buzzing the word "quantum" for a while now (even the NSA is currently preparing itself for a post-quantum crypto world) and quantum-related hardware engineering is evolving constantly. For example: the 5-qubit quantum computer created at MIT by using the technique of ion traps succeeded in prime-factorizing 15. Does that mean that since it succesfully managed that, that it is a all-purpose quantum computer which could be used for cryptanalysis and/or cryptographic attacks?

If that's not the case, what exactly would a "real" quantum computer need (think: rough description of expected technical abilities, aka specs) to enable its users to use it for cryptanalysis and/or cryptographic attack purposes? And - ignoring rumours about potentially existing but confidential governmental projects - does any such system already exist today?

$\endgroup$
  • 2
    $\begingroup$ IIRC for an attack on actual RSA parameters, you'd need about 1M logical qbits which may mean you need much more physical qbits (due to error correction). Here’s a paper about that. BTW, you may want to ping the people in the h bar to let them know about this. $\endgroup$ – SEJPM Oct 22 '16 at 19:45
22
$\begingroup$

For example: the 5-qubit quantum computer created at MIT by using the technique of ion traps succeeded in prime-factorizing 15. Does that mean that since it succesfully managed that, that it is a all-purpose quantum computer which could be used for cryptanalysis and/or cryptographic attacks?

No, not even close. Attacking e.g. RSA requires a lot more than five qubits. Going from five qubits to, say, a million, is not a simple matter of just making more of the same thing; the physics and engineering needed to scale a quantum computer to a large system is it's own particular challenge.

Qubits experience errors

The simplest and perhaps biggest problem is that the more qubits your algorithm needs, the lower the chance that the algorithm completes without any qubits undergoing an error. Suppose we need $n_\text{qubits}=100$ qubits to do a useful computation $[a]$ and suppose the number of logic operations we need for the computation is $n_\text{ops} = n_\text{qubits}^3 = 10^6$. Qubits typically have a certain probability per time of experiencing an error, which leads to the fact that the probability $P$ that a given qubit has not undergone an error is an exponential function of time, $$P = e^{-t / T_\text{coh}}$$ where $T_\text{coh}$ is the qubit's "coherence time". Denoting the time of a single logic operation as $T_\text{op}$, we have $$\ln P = -n_\text{ops}\frac{T_\text{op}}{T_\text{coh}} \, .$$ Supposing we want the qubit to have a reasonable probability to not have an error, say $P=1/2$, we get $$\frac{T_\text{coh}}{T_\text{op}} = \frac{- \ln (1/2)}{n_\text{ops}} \approx 1.4 \times 10^6 \, .$$ In other words, the qubit lifetime $T_\text{coh}$ has to be a million times longer than the time of a logic operation. As far as I know, current state of the art is $T_\text{coh}/T_\text{op} \approx 300$ $[b]$, which is a far cry away from $10^6$.

Now, so far we only talked about single qubits, but in order for the algorithm to succeed, we need all of the qubits to go without errors. With 100 qubits, that puts the target $T_\text{coh}/T_\text{op}$ at $10^{8}$, which, if you ask me, is hopelessly high.

Error correction

If that's not the case, what exactly would a "real" quantum computer need [...]?

Note that the arguments given above could be used to say that a normal computer shouldn't work! Of course, we know that normal computers do work, so what's going on? Regular computer bits (i.e. transistors) have extremely low error rates because they are self-correcting: if the current through a flip-flop fluctuates a bit, the bias circuitry and feedback keep it stable. This is not possible with individual qubits essentially because you can't monitor a quantum state without affecting it, so there's no way to feed back on fluctuations.

On the other hand, with groups of qubits we can correct errors. I'm not going to explain the details here, but it turns out that we can use a group of physical qubits to represent a single error-protected logical qubit. In other words, by encoding the information of a single qubit into a large group of actual physical qubits, we're able to keep the information stable in the presence of errors on the individual physical qubits. This is called "quantum fault tolerance" or "quantum error correction". Fault tolerance requires a large set of qubits, probably arranged in a 2D grid, with fast, accurate measurement and logic gates, and the ability to use the results of various measurements to feed back on the qubits with control signals.$^{[c]}$

...think: rough description of expected abilities/specs) to enable its user(s) to use it for cryptanalysis and/or cryptographic attack purposes?

A technical, but somewhat comprehensive discussion is given in a review of the surface code by Austin Fowler.

Summary

The experiment with five qubits factoring 15 was far too small to tackle a cryptographically useful problem. But even that aside, the underlying system is not fault tolerant, so even scaling that system up to lots of qubits wouldn't make it able to solve crytographically useful problems. To do that, we need a large system with fast and accurate enough logic gates and measurement that it can do error correction.

And - ignoring rumours about potentially existing but confidential governmental projects - does any such system already exist today?

No, there are no publicly known quantum computers capable of cracking RSA as of 07 March 2017.

As you've alluded, a lot of work in quantum computing has gone secret (e.g. all but one of the jobs I interviewed for after getting my PhD in experimental quantum computing would have required a security clearance) so we don't really know the full story. That said, based on my and other people's experience in the field, it seems pretty doubtful that any of the secret projects have built a quantum computer capable of e.g. cracking RSA.

$[a]$: I'm not talking about RSA here, I'm talking about the most basic but useful algorithm you might be able to do on a quantum computer.

$[b]$: That's in superconducting qubits but that was a few years ago and there may be better results in other systems now that I don't know about.

$[c]$: I'm being a little loosey-goosey here; not all fault tolerant protocols have the same requirements. I'm commenting on the ones that I think are most likely to be implemented due to the fact that they have the most forgiving requirements.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.