Shor’s Algorithm In Five Atoms

If you want to factor a number, one way to do it is Shor’s algorithm. That’s a quantum algorithm and finds prime factors of integers. That’s interesting because prime factorization is a big deal of creating or breaking most modern encryption techniques.

Back in 2001, a group at IBM factored 15 (the smallest number that the algorithm can factor) using a 7 qubit system that uses nuclear magnetic resonance. Later, other groups duplicated the feat using photonic qubits. Typical implementations take 12 qubits. However, recent work at MIT and the University of Innsbruck can do the same trick with 5 atoms caught in an ion trap. The researchers believe their implementation will easily scale to larger numbers.

Each qubit is an atom and LASER pulses perform the logic operations. By removing an electron to make each atom positively charged, an electric field can exactly hold the positively charged ions in position only microns apart.

We’ve covered quantum computing before. We’ve even talked about the effect of practical quantum computing on encryption. You might also want to read more about the algorithm involved.

Photo credit: Jose-Luis Olivares/MIT

26 thoughts on “Shor’s Algorithm In Five Atoms

      1. well that’s an entirely different question.
        My point was that the writer used a classically bad expession that even Bill Gates used : “to factor primes”… You can’t factor a prime because it’s its own factor (and 1). Instead it should be something like “to factor a number into primes” (I’m not english but this should be close enough)

          1. No, people often just say factorization when they mean prime factorization, but pedantically and mathematically speaking, they are not equivalent.

            Factorization is the process of finding all sets of natural numbers greater than 1 whose product is exactly equal to the given number. So the factorization of 12 is {{12},{2,6},{3,4},{2,2,3}}.

            Prime factorization is the process of finding the set of primes whose product is exactly equal to the given number. It is exactly one of the subsets of the factorization of the number. For 12, it is {2,2,3}.

      2. Actually, there are deterministic primality tests that allow you to check if a given number is prime and scale surprisingly well. The AKS primality test runs in O((log n)^6) so if you’re given a number you can absolutely test if its prime or not efficiently.

        1. Primality testing is not factorization but still as fascinating.
          Now, abb wanted to have the result in one easy step, and I have no idea of how a Selfridge test works. But a few know.

    1. Not sure about that. 1 is not a prime number.

      “A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number.” – Wikipedia

  1. OK, I will freely admit complete ignorance of quantum anything. I get prime factorization because I have helped my son with his math homework in the past, BUT:

    This article reads like Jeordi LaForge engaging in some heavy duty treknobable. All it needs is a passing mention of reversing a tri-phasic field or something.

    1. Forget about quantum computing for a moment. Think lock and key, public private key encryption can be thought of a bit like a lock and a key. You can examine the lock, and so can everyone else on the planet, but in theory without the key (or a copy of the key) no one but you can open the lock. Here is where the quantum computing comes along without access to the key, they can simultaneously try every key at once to open the lock. Quantum computing is statistics based so it may take many iterations for the solution to converge when the wave functions collapse.

      The good news is they can currently factor 15, but now they have a way to increase that.
      The bad news is that the bulk of secured data and communications world wide is encrypted with public and private keys.
      54 bits (GSM phone calls – but A5/1 *ponder* yea …)
      64 bit (GPRS/EDGE phone calls)
      128bit (some https websites)

      The world of post quantum decryption will be interesting.

      1. While I know you’re probably oversimplifying to ease explanation I think it’s important to say that quantum computers don’t ‘try all solutions at once’ and find the correct one. You could certainly put a quantum computer in a superposition of all possible problem configurations but when you collapse the superposition you only get one result. The real gravy comes from when you have a problem with some structure that allows you to use interference between different paths in a calculation so that the correct result becomes dominant and the others die out. That way when you measure it you’re most likely to get the correct result.

        1. I could not think of any other easy way to explain it using keys and locks. But yes you are totally right, the reality is that not all keys are tried at once. The quantum world is just not easily related to most peoples every day experience of reality.

      2. “The world of post quantum decryption will be interesting.”

        Long before quantum decryption is practical enough to be harmful we will have government-mandated back-doors, which will be (at-least) as destructive.

        1. at which point we will be allowed to use non-backdoored encryption. Just assume SMM and TrustZone run a second OS on your devices regardless of you using Linux/Windows/Os-X… backdoor was there for a long time already…

    1. Shor’s algorithm can also do discrete logarithms. Whenever quantum computers are able to solve prime factorization, discrete log-based cryptography will soon fall too.

  2. Sometimes I wonder if it might be quicker in some circumstances to find primes backwards.
    If there was a computer created with a really large memory. Maybe one bit per digit. The system being hardwired as a huge cascading switch, set to multiply every combination of all the numbers left in the subset below the current number. In that way you illuminate calculations as you go and the larger the numbers become, the larger your lookup table gets.
    It’s like trying to calculate 2Pi you don’t need to do it all to know what’s not going to be in the circle.

    1. You can determine relatively quickly if a number is prime or not (relatively quickly means “in time proportional to some polynomial on the number of digits in the number”). It doesn’t take long to test a 2048-bit number for primality, and you only have to test a few thousand random 2048-bit numbers to find a prime, so you can find two 2048-bit primes in just a few seconds (if you ever make a 4096-bit RSA key, this is what you are doing).

      The problem that Shor’s algorithm is doing is the opposite. Starting with a number you know isn’t prime (or can quickly check with a conventional machine is not prime), find a non-trivial divisor of that number. So if I had a 4096-bit RSA key, which includes a product of two 2048-bit primes, Shor’s algorithm would allow me to relatively quickly find the two 2048-bit primes.

      When thinking of your “computer with a really large memory”, keep in mind how big that would have to be. There are well over 10^600 prime numbers with 2048 bits, and less than 10^100 particles in the observable universe. So the “really large memory” would likely need somewhere on the range of 1 GB of storage for every quark, electron, neutrino, and photon in the universe. That’s a bit large.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.