30
$\begingroup$

IBM announced Q, a project for a 50-qubit universal quantum computer, according to the press realease. Here is more PR spin, and the research sub-page.

What would be the applicability of that to cryptanalysis?

$\endgroup$
35
$\begingroup$

What would be the applicability of that to cryptanalysis?

It wouldn't appear to have any direct applicability to cryptanalysis, for two reasons:

  1. 50 Qbits is just not enough to attack any cryptographical problem; to apply either Shor's or Grover's algorithm against any realistic problem, you'll end up needing thousands.

  2. It doesn't appear that they're addressing the decoherence issue. That is, in a quantum computer, you'll end up getting random perturbations to the running state. Cryptographical computations take quite a long time (far longer than we can go without expecting such a random event to occur), and are quite sensitive to such perturbations. What they'll need to do is run error correction logic (which has multiple physical qbits stand for the one logical one, and has logic to detect such a perturbation on one of the physical qbits, and correct it).

Now, I'm not saying that what IBM is trying to build is useless; for one, it would appear that the computations that Chemical modeling requires fits nicely into what they have.

And, while this isn't immediately useful for cryptography, it is another step towards a Real Quantum Computer (where "Real" means "can actually solve an interesting cryptographical problem).

$\endgroup$
  • $\begingroup$ I would extend the last sentence to: can actually solve an interesting cryptographical problem significantly faster than a comparably priced classical computer. $\endgroup$ – kasperd Mar 6 '17 at 23:31
  • 1
    $\begingroup$ @kasperd: actually, if a cryptographical problem can be solved at all by a feasible classical computer, it isn't interesting... $\endgroup$ – poncho Mar 7 '17 at 0:08
  • 4
    $\begingroup$ Even if a quantum computer doesn't have enough qubits to solve a cryptographic problem in one go, can it be used iteratively, to essentially reduce the search space by whatever factor it can compute in one go? $\endgroup$ – Nat Mar 7 '17 at 2:24
  • 7
    $\begingroup$ @Nat In general, that doesn't work, just like you can't break a hash or encryption one bit at a time (or passwords, like often shown in movies). For those quantum algorithms you actually need all qbits at once - full entanglement over all qbits is required. $\endgroup$ – tylo Mar 7 '17 at 10:38
  • $\begingroup$ @tylo Just to confirm, using small numbers for simplicity, say that a brute-force search space would have 100 possibilities, and a quantum computer only had enough qubits to crack a space with 10 possibilities. Then, it wouldn't be possible to attempt brute-forcing the 100-space by breaking it down into ten 10-spaces, then iteratively trying each? $\endgroup$ – Nat Mar 8 '17 at 9:38
26
$\begingroup$

A 50-qubit universal quantum computer could use Grover's algorithm to invert a 49-bit function in time $\approx7$ steps instead of $\approx25$ steps classically, yielding a speedup of 3.5, on the optimistic assumption that only 1 bit of overhead is needed to compute the function. Put another way, if you wanted to invert lots of 49-bit functions, a 1 GHz quantum computer with 50 qubits would be similar to a 3.5 GHz classical computer. Less optimistically it would take 25 bits, working on 25-bit functions with a speedup of 2.5. Not very exciting IMO.

A 50-qubit universal quantum computer could use a variant of Shor's algorithm with Griffiths & Niu/Kitaev recycling to factor a 49-bit number. I'm not sure exactly how long this would take, but you'd probably use a standard QFT plus schoolbook or possibly Karatsuba multiplication at that size, taking something like 100,000 steps. That's good, assuming a decently-clocked quantum computer, but a classical computer only takes half a millisecond to do the same with SQUFOF, so there are no cryptographic implications yet. Quantum speedup is, very roughly, a factor of 15 here.

Generally, 50-75 qubits is where things start to get interesting for quantum supremacy (thanks to recent advances in classical simulation), 100-200 qubits for quantum chemistry, 1000-2000 qubits for number theory and 2049-10000 qubits for crypto. (You get some good stuff before then, admittedly.) All of this is for high-quality universal quantum computers. Adiabatic quantum computers and quantum annealers are interesting but aren't known to outperform classical algorithms in anything other than simulating themselves.

Everything here assumes qubits that are extremely high-quality, in the sense that the chance of any decoherence during the computation is, say, < 50%. So for Grover's algorithm you'd need 99.8% nondecohering qubits and for Shor you'd need 99.99999% nondecohering qubits. If you can't get there, but you can get close, you can just rerun the calculation until it works, but a lot of patience only makes up for a little bit of quality. If you can't get to that quality level then conventional wisdom says you'll need to increase the number of qubits by a factor of at least 10-1000 for error correction. I don't know what's state of the art but Calderbank, Rains, Shor, & Sloane have two papers.

Current quantum computers are hitting the low end of the number of qubits but can’t get the required quality for the desired calculation depth. Google’s quantum supremacy paper discusses simulating depths up to 20 requiring tens of millions of runs to distinguish signal from noise; it would hardly be possible to run a circuit of depth 25 on that machine, even with great effort. But depths of thousands or millions will be required, so we have a long way to go. Still, progress!

$\endgroup$
  • $\begingroup$ I didn't think that a 50 bit qbit QC could use Grover's on a 49 bit function. AFAIK, Grover's algorithm requires the internal function it checks to be invertible, which means that we need to embed our one-way function into a larger invertible one. This is quite doable, but it means that we need more qbits to represent the state that allows it to be invertible. $\endgroup$ – poncho Mar 7 '17 at 21:11
  • $\begingroup$ @poncho 1 bit is the absolute best possible case, most functions will take more qubits. But probably many interesting functions can be encoded with a relatively small number of qubits using recycling and other techniques. I could have used a 25-bit function in 5 bits with a speedup of 2.5 to represent a more normal case. $\endgroup$ – Charles Mar 7 '17 at 21:28
  • $\begingroup$ Hmmm, if you're searching for a specific target value for your one-way function, you'll need to have at least n/2 (25 in this case) extra bits in your invertible functions to make it interesting. If you had a function that can be made invertible with fewer extra bits, then a conventional computer could invert all possible images with the value you're searching for, along with the various settings of the n/2 helper bits, and seeing which worked; this gives you the same performance as Grover's, without a QC. $\endgroup$ – poncho Mar 7 '17 at 21:48
  • 2
    $\begingroup$ @poncho I was looking for a lower bound like that but I didn't find one in the literature. If you have a reference make an answer and I'll definitely upvote. Up until this year I didn't know it was possible to do Shor with only 1 qubit of overhead, and I thought $n+3$ (total $2n+3$) was pretty impressive, so I used a similarly optimistic 1 qubit for Grover. $\endgroup$ – Charles Mar 7 '17 at 22:14
  • $\begingroup$ Actually, I was just thinking it through; if you have an inverse function that takes $n$ postimage bits (known, that's the image you're looking for) and $k$ "helper" bits (that make the function invertible), then you can scan through all possibilities in $2^k$ time on a conventional computer (and pick out the one that works); that'll give you the inverse of your one-way function. If $k < n/2$, that gives you a time better than Grover's. That doesn't mean Grover's won't work, it means that there are better solutions out there... $\endgroup$ – poncho Mar 8 '17 at 1:48
-1
$\begingroup$

I am not 100% sure if there is a direct use specific to cryptoanalysis. However, if this machine is applied to another discipline, such as machine learning and data science in general, it could have an effect on crypto work. For example, in data science, neural networks can be an effective tool for solving many problems. The issue is that they are painfully slow and is one of those rare cases where throwing more hardware at the problem can be a solution.

So while there may not be a direct link to crypto as we stand right now, who knows what the future may bring.

$\endgroup$
  • $\begingroup$ As far as I know neural networks don't have any application in cryptanalysis (with or without quantum computer) for common encryption schemes. $\endgroup$ – Ievgeni Nov 5 at 17:51

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.