11
$\begingroup$

Let us assume that we have quantum and classical computers such that, experimentally, each elementary logical operation of mathematical factorization is equally time-costing in classical and in quantum factorization: Which is the lowest integer value for which the quantum proceeding is faster than the classical one?

$\endgroup$
  • 2
    $\begingroup$ A very precise reckoning would depend on details such as the implementation of addition operations in the quantum algorithm, and also on the precise operations used in the best classical factorisation algorithm. In both cases, we are often accustomed to ignoring constant factors in the amount of work required, but even moreso in the classical case than the quantum case. Would you be satisfied with an order-of-magnitude estimate (e.g. a quantum advantage being gained somewhere between 350-370 bits --- to provide a possible answer which I've created from thin air based on no actual analysis)? $\endgroup$ – Niel de Beaudrap Apr 17 '18 at 9:45
  • $\begingroup$ @NieldeBeaudrap I would say that for the reasons you stated, an exact number would be impossible to provide. If your 'out of the air' estimate is based on some reasoning, I think it would be interesting. (In other words, an educated guess has value, but a wild guess doesn't) $\endgroup$ – Discrete lizard Apr 17 '18 at 10:02
  • $\begingroup$ @DiscreteLizard: if I had a sound means of estimating ready to hand, I would not have produced an example answer based on no analysis :-) I'm sure there's a reasonable way to produce an interesting estimate, but the ones I would be able to easily provide would have error bars too large to be very interesting. $\endgroup$ – Niel de Beaudrap Apr 17 '18 at 10:11
  • $\begingroup$ Since this problem is (or was) commonly taken as typical "proof" that quantum computers are capable of feats outside the realms of classical computing, but nearly always in strict computational complexity terms (so, neglecting all constants and only valid for arbitrarily high input sizes) I'd say a rough order-of-magnitude answer (and its derivation) would already be useful/pedagogical. Maybe the people on CS/theoreticalCS might be willing to help. $\endgroup$ – agaitaarino Apr 17 '18 at 10:13
  • 1
    $\begingroup$ @agaitaarino: I agree, though the answer will have to presume some more-or-less precise account of the performance of the best classical algorithms for factorisation. The rest can then be done by a reasonably good student of quantum computation. $\endgroup$ – Niel de Beaudrap Apr 17 '18 at 10:28
8
$\begingroup$

The quantum part of Shor's algorithm is, essentially, a single modular exponentiation done under superposition followed by a Fourier transform and then a measurement. The modular exponentiation is by far the most expensive part.

Let us assume that [...] each elementary logical operation of mathematical factorization is equally time-costing in classical and in quantum factorization

If we assume that the modular exponentiation takes exactly as long on a quantum computer as it would on a classical computer, then the transition where the quantum computation became better would happen at a very low number. Computing modular exponentiations is very fast, classically, because you can use repeated squaring. I would wildly estimate the crossover to happen even before you even get to 30 bit numbers (numbers over a billion).

But quantum computers are not going to do math nearly as fast as classical computers. For example, on my laptop, I can do a 1000-bit modular exponentiation in python in a fraction of a second. But on foreseeable quantum computers, it would take hours or days. The issue is the massive (massive) difference in the cost of an AND gate.

On a classical machine, performing an AND is so inconsequential that we don't even really think about it when programming. It's way more likely for you to think in terms of counting 64-bit additions than in terms of counting AND gates, when determining the cost of your algorithm. But on an error corrected quantum computer, performing an AND (usually temporarily, via a Toffoli) tends to be expensive. For example, you can do it by distilling four high-quality $|T\rangle$ states. I won't go into the numbers... suffice it to say that on early error corrected machines you would be very happy to get a million T states per second.

So suppose we get a million T states per second, and we want to convert this into a rate of 64-bit additions to compare with the classical machine. A 64-bit addition requires 64 AND gates, each requiring 4 T gates. 1 million divided by 4 divided by 64 gives... about 4KHz. For contrast a classical machine will easily do a billion additions per second. Quantum adders are a million times slower than classical adders (again, wildly estimating, and keep in mind this number should improve over time).

Another factor worth considering is the differing costs of quantum and classical computers. If you have a hundred million dollars, and you're choosing between one quantum computer and a thousand classical computers, that factor of 1000 has to be accounted for. In this sense, we could say quantum adders are a billion times less efficient than classical adders (in FLOPS/$).

A constant factor penalty of a billion is normally an immediate deal breaker. And for quantum algorithms with a mere quadratic advantage (like Grover), I contend that it is in fact a deal breaker. But Shor's algorithm gets exponentially better relative to the classical strategy as you increase the number of bits in the number to factor. How many bits before we eat away that "measly" 10^9 constant with our exponential growth in advantage?

Consider that RSA-640 was factored in 2005 using ~33 CPU years. A quantum computer should be able to do that number in under a day. If you have a thousand classical computers working on the problem, they'd finish in about two weeks. So it seems like quantum is winning by 640 bits, but only by an order of magnitude or three. So maybe the cutoff would occur somewhere around 500 bits?

Anyways, I know this is not a hard and fast answer. But hopefully I've conveyed some sense of the quantities I would think about when comparing classical and quantum. Really no one knows the constant factors involved yet, so I'd be surprised if anyone could give you a proper estimate better than "somewhere in the hundreds of bits".

$\endgroup$
  • $\begingroup$ This is a good effort, but how do you come about the estimate of 30 bits? What precisely are you comparing Shor's algorithm to, when you consider that a likely crossover point? $\endgroup$ – Niel de Beaudrap Apr 18 '18 at 8:37
  • 1
    $\begingroup$ @NieldeBeaudrap Like I said, it's a wild guess. I figure: modular multiplication has a decent constant factor (classically). So does continued fractions. Do factoring algorithms also have good constant factors? Probably not? If so, the crossover would happen almost immediately instead of at big numbers. If someone wants to actually benchmark those two things against each other, I'll update the answer. I consider the "meat" to be the rest of it. $\endgroup$ – Craig Gidney Apr 18 '18 at 8:48
  • 1
    $\begingroup$ I wouldn't normally object to this as providing an intuition, except that your wild guess is precisely on the subject of the question. (The question is also posed in such a way that suggests awareness of clock-speed issues.) The fastest techniques for factorising very large numbers involve large constant factors, but actually reckoning with them is the point of the question; but for numbers around a billion we might even consider trial division using a table of primes up to about 32,767, which would be very fast in practise. A quantitative comparison even with this would be a start. $\endgroup$ – Niel de Beaudrap Apr 18 '18 at 9:19
6
$\begingroup$

As I mentioned in the comments, a very precise answer will likely depend on a lot of technical choices which are somewhat arbitrary. It is likely to be more important to obtain an order-of-magnitude estimate, and to account for as much as possible in making it.

This answer is intended not as a definitive answer, but as a step in the right direction by reference to the existing literature (though admittedly over a decade old by now), specifically:

  • Van Meter, Itoh, and Ladd. Architecture-Dependent Execution Time of Shor's Algorithm. Proc. Mesoscopic Superconductivity + Spintronics 2006; [arXiv:quant-ph/0507023]

Van Meter, Itoh, and Ladd attempt to compare the performance of Shor's algorithm with available computing technology performing the Number Field Sieve (the best known classical algorithm for factorisation). I have not had the time to plumb through the details of the paper — a superior answer could likely be obtained by doing so — but Figure 1 of that article allows us to make a reasonable numerical estimation:

enter image description here

Here, the steep curves represent the computing time of classical computing networks. The curve labeled 'NFS, 104 PCs, 2003' seems to indicate computations (and the projected computing time) of one hundred and four personal computers circa 2003, as reported by RSA Security Inc. in 2004 [http://www.rsasecurity.com/rsalabs/node.asp?id=2096].

We will carry out a Fermi calculation. Let us assume that the curve corresponds to a computation on 104 essentially identical computers, and let us presume that $n$ computers carrying out number field sieve can carry out $n \cdot v$ computations per second of Number Field Sieve, where $v$ is the number of operations per second which a single computer can carry out. A quick web search suggests the speed of a good commercially available PC circa 2003 was about 2GHz. Assuming that the computers were performing one logical operation per clock cycle, the classical computation in 2003 was effectively operating at about $2 \times 10^{11}$ operations per second. A hypothetical benchmarking of Shor's algorithm would have to be made against a quantum computer performing at a comparable clock speed.

Unfortunately the lowest curve for quantum algorithms represents a clock-rate of $10^9$, so the point at which a hypothetical realisation of Shor's algorithm would surpass this performance is not on the graph shown. However, there is some interesting information which is shown.

  • Despite a operations-per-second advantage of a factor of 200 or more, the plot does indicate when this 200GHz classical NFS implementation is surpassed by a 1GHz quantum computer performing Shor's algorithm (at about 200 digit numbers) and by a 1MHz quantum computer (at about 330 digit numbers).
  • We also have a curve projecting the performance "in 2018", representing 1000 times the classical computation power: the intercepts with the 1GHz and 1MHz quantum computers are at 350 bit numbers and 530 bit numbers.

The increase in the crossing points against quantum computations, from the computation in 2003 to the projected one in 2018, representing a clock-speed boost of 1000, is a factor of about 5/3. From this we can estimate that the computational advantage to the size of numbers that can be quickly solved by a classical computer, due to a speed increase of a factor of 200, is roughly 7/6. Then we can estimate that the crossing point of a single 1GHz classical computer performing NFS, with a 1GHz quantum computer performing Shor's algorithm, is at about 170 bit numbers.

The bottom line — a precise answer will depend on many technical assumptions which can change the precise result significantly, so it is better to seek a rough estimate. But this question has been researched at least once before, and making some number of assumptions and extrapolations on performance based on classical performance in 2003, it seems that Shor's algorithms will outperform the best known classical algorithm on an operation-by-operation basis for numbers around 170 bits.

$\endgroup$
  • $\begingroup$ This is a good answer. It's worth noting that this paper's idea of an "elementary logical operation" is (very appropriately) at the level of an AND gate, as opposed to at the level of a CPU instruction or a BigInt operation (which I suspect is what the asker was thinking). In my own answer I was assuming the modular exponentiation was done "as if classically", which would involve e.g. FFT multiplications. This is why I guessed a number that was so much lower than this paper, which (appropriately) does schoolbook multiplication with ripple carry adders for its quantum arithmetic. $\endgroup$ – Craig Gidney Apr 18 '18 at 18:53
  • $\begingroup$ @SalvaCardona: I recommend that you do not accept my answer. My analysis is very cursory, and you should hold out for a better analysis. $\endgroup$ – Niel de Beaudrap Apr 19 '18 at 13:53

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.