28
$\begingroup$

Assuming in the future there was a functioning 1024 qubit quantum supercomputer and it could run Shor's algorithm or Grover's algorithm to crack encryption very quickly. I'm interested in how the number of qubits translates to performance improvement over a regular 2 bit computer.

For example, if I used Shor's algorithm on a 4 qubit quantum supercomputer, would this take half the time to factor 1024 bit RSA as it would a regular 2 bit supercomputer? Then if we extrapolate upwards to 8 qubit supercomputer through to 512 qubit, 1024 qubit and even 2048 qubit etc. What sort of factorization speed increase would you get from adding more qubits? I originally thought quantum computers could have only 4 qubits. But it seems these days you can keep adding qubits up to the amount you want within technical reason. Does this mean if I had a 1024 qubit supercomputer I could factor RSA 1024 bit in a split second? At what speed could it check possible factorizations?

So I'm interested how long it would "theoretically" take to:

  1. Brute force find the key for a 1024 bit encrypted RSA message using Shor's algorithm.
  2. Brute force find the key for a 256 bit AES encrypted message using Grover's algorithm.
  3. Find a pre-image for a SHA2-512 bit hash.
  4. Construct a rainbow table for a SHA2-512 bit hash.
  5. If people are using 2048 bit RSA now as standard, will it take double the above time?

Some explanation for how to calculate that and a breakdown into the time it would take in seconds, minutes, hours, days or years would be much appreciated.

$\endgroup$
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – e-sushi Dec 16 '17 at 18:27
  • $\begingroup$ You can't just keep adding qubits. Each qubit needs to be entangled with the others (at least to have a fully general-purpose QM), so each and every qubit drastically increases the precision required for the machine to function. Every single instance of quantum decoherence requires the calculation to start over. $\endgroup$ – forest Dec 14 '18 at 2:49
21
$\begingroup$

Adding more qubits does not increase the computation speed. A quantum computer with 4 qubits does not factorize faster than one with 2. The qubits are the "memory" of the quantum computer. More qubits mean you can factor bigger numbers. If I remember correctly, you need a superposition of $\Theta(N^2)$ terms, which means $\Theta(\log(N^2))$ qubits to factor N. The running time of Shor's algorithm is $O((\log N)^3)$ to factorize $N$. What is important to remember is that Shor's algorithm can only factorize (by solving the discrete log problem). See wikipedia's entry on Shor's algorithm.

As for Grover's algorithm, it provides quadratic advantage over classical computers for "black-box" queries. So a quantum computer could perform a brute-force attack in $O(\sqrt{N})$ trials whereas a classical computer would need $O(N)$ trials. Again, increasing the number of qubits does not lower the running time, but increases the "memory" of the quantum computer. In order to run Grover's algorithm to brute-force a key, you need a superposition of all keys, which requires $\log K$ qubits where $K$ is the number of possible keys.

$\endgroup$
  • $\begingroup$ 'Shor's algorithm can only factorize (by solving the discrete log problem)...' I'm confused by this. $\endgroup$ – pg1989 Aug 23 '13 at 17:21
  • 8
    $\begingroup$ Shor's algorithm consists of two parts, one classical and one quantum. The quantum part does the following: given $a$ and $N$ such that $gcd(a,N)=1$, find $r$ such that $a^x = a^{x+r} \mod N$ for all $x$. This is done using quantum Fourier transform. The classical part uses this $r$ to factorize $N$, i.e., it reduces the problem of factoring to the discrete logarithm problem. $\endgroup$ – Philippe Lamontagne Aug 23 '13 at 19:05
  • 2
    $\begingroup$ @PhilippeLamontagne: actually, in practice, adding the number of qubits often does increase the practical speed of Shor's and Grovers - not because it helps those algorithms themselves, but instead adding additional ancillary qubits allows faster implementations of the subroutines (modular multiply, Oracle implementation) that those algorithms rely on. $\endgroup$ – poncho Aug 26 '18 at 22:51
14
$\begingroup$

With a 1024 qubit quantum computer you cannot break any of the algorithm you mentioned.

Current estimations for an impelmentation of Grover's algorithm for AES requires much more qubits. According to this paper by Grassl et al. the required number of qubits required for AES-256 is 6681, see the following extracted table:

enter image description here

I guess it's not unreasonable to draw similar conclusions for SHA2-512, which has a much bigger internal state, and say that 1024 qubits are not enough.

And regarding RSA, there is a paper from Proos and Zalka with estimations for RSA and ECC. See the image below extracted from the paper:

enter image description here

Which clarifies that you need 2048 qubits to factor a 1024 RSA key. As noted by user1147688 in a comment this paper talks about logical qubits, and specifies that:

Also it seems very probable that for large scale quantum computation error correction or full fault tolerant quantum computation techniques are necessary. Then each of our "logical" qubits has to be encoded into several physical qubits (possibly dozens) and the logical quantum gates will consist of many physical ones.

Making the target number of qubits to break RSA-1024 much higher than the theoretical 2048.

Edit1: to take into account comment by user1147688

$\endgroup$
  • $\begingroup$ Just to clarify the C time values: "The column to the right roughly indicated the classical computing resources necessary in multiples of C, where C is what’s barely possible today." Since, the paper was written 2008, that means what was possible using the technology of 2008. And we're now 9 years later... $\endgroup$ – not2qubit Feb 3 '17 at 12:49
  • 4
    $\begingroup$ In addition, the comments in the 2nd paper states: "Also it seems very probable that for large scale quantum computation error correction or full fault tolerant quantum computation techniques are necessary. Then each of our "logical" qubits has to be encoded into several physical qubits (possibly dozens) and the logical quantum gates will consist of many physical ones." $\endgroup$ – not2qubit Feb 3 '17 at 12:52
3
$\begingroup$

Assuming that it will also be possible to reduce the error rate of each quantum operation below 0.01%, it would be possible to perform the 2048-bit number factorization in approximately 10 days, requiring on the order of 5 × 108 ions.

From: Blueprint for a microwave trapped ion quantum computer

As a comparison : "RSA Labs claim (see: http://www.rsa.com/rsalabs/node.asp?id=2004) that 2048-bit keys are 2^32 (2 to the power of 32) times harder to break using NFS, than 1024-bit keys. 2^32 = 4,294,967,296 or almost 4.3 billion, therefore breaking a DigiCert 2048-bit SSL certificate would take about 4.3 billion times longer (using the same standard desktop processing) than doing it for a 1024-bit key. It is therefore estimated, that standard desktop computing power would take 4,294,967,296 x 1.5 million years to break a DigiCert 2048-bit SSL certificate."

From : https://www.digicert.com/TimeTravel/

$\endgroup$
3
$\begingroup$

An additional answer based an the following quote from the blueprint article of @jhegedus.
A quantum computer with $2\times 10^9$ trapped ions needs 14 days to break RSA-1024 and about 10,000m² space.

On the basis of the same scheme, we can give quantitative estimates on the system size and processing time for a machine that solves a relevant, hard problem, such as the Shor factoring of a 2048-bit number. For the calculations, we assume a single-qubit gate time of 2.5 μs, two-qubit gate time of 10 μs, ion separation and shuttling time of 15 μs each, static magnetic field gradient ramp-up and ramp-down time of 5 μs each, and a measurement time of 25 μs, resulting in a total error correction cycle time of 235 μs. On the basis of these numbers, performing a 2048-bit number Shor factorization will take on the order of 110 days and require a system size of 2 × 109 trapped ions. Shor factoring of a 1024-bit number will take on the order of 14 days. Both of these factorizations will require almost the same amount of physical qubits because the required pace of the ancilla qubit generation is the same for a 2048-bit and a 1024-bit factorization. Trapping 2 × 109 ions will require 23 × 23 vacuum chambers occupying an area of ca. 103.5 × 103.5 m2.

$\endgroup$
  • $\begingroup$ I guess that is still cheaper than the LHC. 100 vacuum chambers.... $\endgroup$ – jhegedus Feb 4 '17 at 10:27

protected by SEJPM Dec 13 '18 at 19:25

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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