24
$\begingroup$

I've just been reading up on Shor's algorithm, and I find it both fascinating and baffling. I don't understand much about it, other than that it can factor semiprimes in polynomial time.

Could someone explain how it works in layman's terms and why it is reliant on quantum computing?

Keep in mind that while I understand quantum computing basics (i.e., it uses photons instead of electrons, and bits are replaced with qubits that can be 0, 1, or a superposition of both), I don't know anything in-depth about it. I know it's supposedly super-fast compared to classical computing mechanisms.

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ Take a look at scottaaronson.com/blog/?p=208 $\endgroup$
    – Huck Bennett
    Commented Oct 3, 2012 at 15:56
  • 1
    $\begingroup$ I'm not qualified to provide an answer, but the following article may be what you are seeking: arstechnica.com/security/2012/09/… $\endgroup$
    – ericball
    Commented Oct 4, 2012 at 12:28
  • $\begingroup$ I think Shor's algorithm would work even if its input wasn't a semiprime. $\:$ $\endgroup$
    – user991
    Commented Oct 6, 2012 at 10:12
  • 1
    $\begingroup$ No, because it also solves discrete logarithm efficiently. $\:$ $\endgroup$
    – user991
    Commented Oct 7, 2012 at 20:38
  • 3
    $\begingroup$ My take on it is that Shor's algorithm evaluates the period of $a^x \pmod{n}$ where $\gcd{(a, n)} = 1$. This is not efficient on a classical computer, but when run on a quantum computer, a miracle occurs and we get a congruence of squares with probability $0.5$ in polynomial time. The miracle part is, I guess, what you're asking.. but that requires physics and maths knowledge that's beyond me. $\endgroup$
    – Thomas
    Commented Oct 10, 2012 at 5:53

1 Answer 1

Reset to default
31
+50
$\begingroup$

The question to answer is "Is N the product of P*Q?" I believe that the easiest way to understand Shor is to imagine two sine waves, one length P and one length Q. Assuming that P and Q are co-prime, then the question above can also be answered "At what point does the harmony of P overlapped with Q repeat itself?" And the answer can be determined quickly, based upon the simple observation that we can figure out the phase of each wave at any given point on the number line. (The phase, remember, is "how far along the pattern is this point?" and is often measured in degrees; 90 degrees = 1/4 rotation)

If we look at the point N then the phase of P and Q must be 0 if they are factors of N (or else there would be a remainder of the division N/Q or N/P). Shor just tests whether the phase of P == the phase of Q == 0 at point N. It turns out that phase estimation is pretty easy for quantum computers, so it's a good tool to build into a factoring machine. See http://www.wikipedia.org/wiki/Quantum_phase_estimation_algorithm for more information.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ That's actually a really great way of explaining it. $\endgroup$
    – Polynomial
    Commented Oct 10, 2012 at 7:31
  • 4
    $\begingroup$ The question to answer is "Of which P and Q at least 2 is N the product of?" rather than "Is N the product of P*Q?". For the later we have very efficient algorithms, polynomial in Log(N) on classical computers. $\endgroup$
    – fgrieu ♦
    Commented Oct 10, 2012 at 10:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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