0
$\begingroup$

I ran into this graph where the red one is $$x^3$$ and represents the number of steps as a function of factorised bits for a quantum computer. The blue graph represents the classical computer and has the function $$e^{1.9(x^{1/3}ln^{2/3}(x)}$$ enter image description here

The quantum computer function seems to be derived from Shor's algorithm, and i have no idea where the classical one comes from. Can someone derive and or explain these two functions?

$\endgroup$
  • 1
    $\begingroup$ Sorry we don't do homework on this site... see the help centre .... physics.stackexchange.com/help $\endgroup$ – tom Mar 21 '18 at 18:55
  • 1
    $\begingroup$ This is not homework, i'm doing an assignment and i stumbled across this graph and would like to know where the two functions come from. $\endgroup$ – iBoughtWinrar Mar 21 '18 at 18:58
  • $\begingroup$ ok, but the way you are asking the question looks like homework... $\endgroup$ – tom Mar 21 '18 at 19:23
  • $\begingroup$ I cut out the small introduction to how i stumbled across the problem. It might be more clear now. $\endgroup$ – iBoughtWinrar Mar 21 '18 at 19:45
  • $\begingroup$ Note that x is the number of digits, so essentially $log N$, if $N$ is the number you want to factor $\endgroup$ – doetoe Mar 22 '18 at 0:11
0
$\begingroup$

The graph shows how computational time required to factorize an integer increases as the size of the integer increase. Note the logarithmic vertical scale, which means as the size of the integer increases the computational time required by a quantum computer gets faster and faster compared to the time required by a 'classical' or normal computer.

The computational times shown are theoretical for the quantum computer because, as described in the wikipedia page, quantum computers have not been made that can factorize large numbers. The principle, however, has been demonstrated by factorizing small numbers with quantum computers. Quantum computers are hard to build because it is necessary to have complete control over a set of quantum entities such as photons of light of nuclear spins. Whereas for current computer processors 64-bit processors are normal, in the case of quantum computers 4 or 5 bits is very hard, though perhaps with time it will get easier. At the time of writing, however, 64-bit quantum computers are not a reality.

The computational times shown are calculated theoretically based on the details of the algorithms used in quantum computers and normal computers and how much searching they will need to do to find the factors.

EDIT - PLEASE NOTE I NOW DESCRIBE A BAD WAY TO SEARCH FOR PRIMES, BUT A BAD WAY WHERE IT IS RELATIVELY EASY TO EXPLAIN WHERE THE $O$ EQUATION COMES FROM

(sorry for shouting in capitals..)

If to search for primes you check every possible factor from 2 to $\sqrt{N}$ you have roughly $\sqrt{N}$ steps and given that I think $x=\log(N)$ that would mean

$$time \propto \sqrt{{\rm e}^{x}}$$

or

$$ O(\sqrt{N}) $$

or

$$ O({\rm e}^{x/2} ) $$

I think, but I am not sure - you should look it up to check - this is much worse than the methods you have in your graph...

$\endgroup$
  • $\begingroup$ Is it possible for you to elaborate on how the times shown are calculated? I would like to know where the two functions come from because when i google this topic, i seem to find quite a few similar, but yet different, functions. I would like to be certain what is correct and what is approximation by following the calculations myself. $\endgroup$ – iBoughtWinrar Mar 21 '18 at 23:52
  • $\begingroup$ @iBoughtWinrar - I suggest you start with the wikipedia page that is linked.... but I will make a small edit.... $\endgroup$ – tom Mar 21 '18 at 23:56
  • 1
    $\begingroup$ There are much smarter methods for factorization then a naive divisibility test, which is why the OP's curve doesn't match your expectations. For example, the general number field sieve has a complexity of roughly $O(\mathrm{exp}((\ln n)^{1/3}(\ln\ln n)^{2/3}))$. $\endgroup$ – probably_someone Mar 22 '18 at 0:12
  • $\begingroup$ @probably_someone - YES == but it so much easier to explain the reasoning for the $O$ function for this naive method --- do you want to explain the reason that the general number field sieve has that form for $O$, which is what the OP wants to know??? :-) $\endgroup$ – tom Mar 22 '18 at 0:15
  • $\begingroup$ I believe i understand, "general number field sieve" was a good keyword to look up $\endgroup$ – iBoughtWinrar Mar 22 '18 at 11:20

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.