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?
2
-
1$\begingroup$ Possible duplicate of "What does a “real” quantum computer need for cryptanalysis and/or cryptographic attack purposes?" $\endgroup$– e-sushiMar 6, 2017 at 20:59
-
$\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$– e-sushiMar 8, 2018 at 18:52
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
8
TL;DR: Not much. If the qubits were very high quality, some very tricky algorithms could use them to do some algorithm subprocesses more quickly, but we actually have more quantity than quality. So it's just research for now.
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 (iterative phase estimation) with an adaptive circuit 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. Without an adaptive circuit, you're down to 24 bits with Häner, Roetteler, & Svore which pretty much wipes out any quantum advantage.
A new quantum factorization algorithm, VQF, has been discovered that is well-suited to this sort of small quantum computer. Unfortunately, it does not scale well, not even as well as classical algorithms, and in particular does not display quantum advantage. It was able to factor an apparently large number, but this took a large amount of classical effort which isn't useful if you're using the quantum computer to offload classical work.
Generally, 50-75* qubits is where things start to get interesting for quantum supremacy, 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.
This assumes extremely high-quality qubits, 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. A careful reading of the latter shows that the most basic form of error correction—single-qubit error correction—'costs' 8 qubits using a shortened version of the [[85, 77, 3]] Hamming code. But actually encoding it requires ancilla qubits, and I don't know a way of doing this efficiently. The best scheme I'm aware of, via Chao & Reichardt, requires only two qubits for ancilla but costs 12 qubits if we can shorten the [[63, 51, 3]] Hamming code to [[48, 36, 3]], or effectively 27 (!) qubits if we have to use the [[31, 21, 3]] Hamming code. (The Hamming code can definitely be shortened, I just don't know if the Chao–Reichardt method would work with the shortened code or not.) So with current technology a 50-qubit quantum computer could simulate either 21 or 36 qubits with minimal error correction, depending on which of my interpretations is correct. If anyone knows a better approach please let me know.
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!
* Recent advances in classical simulation pushed it up from earlier estimates of 40 qubits.
-
$\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$– ponchoMar 7, 2017 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$– CharlesMar 7, 2017 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$– ponchoMar 7, 2017 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$– CharlesMar 7, 2017 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$– ponchoMar 8, 2017 at 1:48
$\begingroup$
$\endgroup$
7
What would be the applicability of that to cryptanalysis?
It wouldn't appear to have any direct applicability to cryptanalysis, for two reasons:
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.
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).
-
$\begingroup$ I would extend the last sentence to: can actually solve an interesting cryptographical problem significantly faster than a comparably priced classical computer. $\endgroup$– kasperdMar 6, 2017 at 23:31
-
2$\begingroup$ @kasperd: actually, if a cryptographical problem can be solved at all by a feasible classical computer, it isn't interesting... $\endgroup$– ponchoMar 7, 2017 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$– NatMar 7, 2017 at 2:24
-
8$\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$– tyloMar 7, 2017 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$– NatMar 8, 2017 at 9:38
$\begingroup$
$\endgroup$
1
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.
-
1$\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$– IevgeniNov 5, 2019 at 17:51