Quantum Processor Calculates That 15 = 3x5 (With Almost 50% Accuracy!)

By Rebecca Boyle Posted 08.20.2012 at 3:00 pm 15 Comments

Quantum Processor The device in this photomicrograph was used to run the first solid-state demonstration of Shor's algorithm. It is made up of four phase qubits and five superconducting resonators, for a total of nine engineered quantum elements. The quantum processor measures one-quarter inch square. UCSB

For the first time, a functional solid-state quantum computer has completed a fairly simple math problem, factoring a prime number into its constituent parts. The solution itself isn’t that great an accomplishment — it was the number 15 — but it’s a major leap for quantum computers, because it’s a step toward factoring much larger numbers. Factoring very large numbers very quickly is crucial for cybersecurity.

Researchers led by PhD graduate Erik Lucero of the University of California-Santa Barbara built a quantum processor to map the number 15. The team built a quantum circuit made of four superconducting qubits, which are the logic gates of a quantum system, on top of a substrate made of sapphire. It also contained five microwave resonators. The fabrication itself was a breakthrough, because organizing nine separate quantum pieces required very precise, automated construction methods. The qubits were entangled and verified using quantum experiments. Then the team used this circuit to factor 15 using Peter Shor’s factoring algorithm. That code says for any given integer N, the computer must find its prime factors. But it does this quantum-fast, finding the solution exponentially faster than the quickest known classical factoring algorithm.

Why is this important? Quantum computers could greatly improve cybersecurity by enabling much more complex encryption than is possible with classical systems. The most common form of encoding is called RSA encryption, and it’s based on the fact that it is very hard to factor large prime numbers. The product of two large prime numbers serves as the key for encryption, and the prime factors themselves are secret. To solve the code, a classical computer system has to crunch a series of numbers. This can take a long time, especially as the prime numbers get very large.

With the fastest classical factoring algorithm, factoring the 600-digit, largest-ever RSA encryption number would take longer than the age of the universe. This system could theoretically do it in an hour.

Lucero and colleagues ran the experiment 150,000 times, and the processor got the right answer 48 percent of the time. Shor’s algorithm holds that a quantum system will get the right answer exactly half the time, so this is actually pretty good. The next step is to improve quantum coherence and build more complex circuits, so the computer can solve much larger factoring problems.

The paper appears in this week's issue of Nature Physics.

[UCSB]

Previous Article: Giant Cave Spider Discovered in Oregon

Next Article: The Army's Quick Fix for Soldier Suicides: Anti-Depressive Nasal Spray

15 Comments

Link to this comment

yetihehe

08/20/12 at 3:22 pm

15 isn't a prime number, but your article makes it sound so. Also in your source 15 is called composite number.

Link to this comment

TheZomb

08/20/12 at 3:34 pm

Its impossible to factor a prime number. I'm sure you guys mean they factored a number into its prime factors. especially since 15 isn't prime and 3 and 5 are.

Link to this comment

Bagpipes100

08/20/12 at 4:53 pm

There are many ways to factor a prime. None of which are useful. For instance 5 is prime. 5 can be factored 1*5, or (-1)*(-1)*5, etc. As long as all the other factors (besides the prime itself) are just units, it'll work. This also applies to primes in any ring (not just the integers).

Link to this comment

DirtySquirties

08/20/12 at 5:38 pm

I get how cyber security would improve with quantum computers in theory, but if everyone has a quantum computer, how would it be any different than now? A quantum computer's speed and ability to create more complex encryption would exist, but another just as fast and capable quantum computer is there to beat it.

Link to this comment

Robot

08/20/12 at 8:13 pm

I am glad this technology is improving, but with 50% accuracy, who wish to have a robot with this type of brain do heart surgery on a human? Let's see a raise of hands!!!! ;)

Link to this comment

tcolguin

08/20/12 at 10:12 pm

The article is exactly backwards. It would take something that is now secure and make it not secure.

Now if your idea is that you a government agency that wants to spy on people that is you consider you being able to break other people codes so that you can do that and keep society "secure" by knowing everything they are doing, then I guess you consider the future secure in this fact.

BTW if it had 50% accuracy to crack someone's code, well that would be pretty good, but of course this example extremely simple and there is no telling if the accuracy would scale to hard searches for prime numbers.

Link to this comment

khughes5

08/21/12 at 1:25 am

The number 15 was factored using a quantum computer in 2001... is all that has been done in the last decade moving from a liquid quantum computer to solid-state? or am I missing something else?

reference:

L. M. K. Vandersypen et al., ``NMR quantum computing: realizing Shor's algorithm,'' Nature 20/27, December 2001

Link to this comment

nighthawkich

08/21/12 at 2:42 am

@D13

All current forms of encryption will be rendered obsolete and will have to be upgraded with new qubit key based algorithms.

@khughes5

There is a little more involved than that. While the individual processes themselves haven't changed much, the devices and how they are processed have.

The liquid NMR quantum array used for prime factoring circa 2001 was about the size of 3 average office desks. The new hardware is approx the size of a desktop computer (less the cooling apparatus of course). This new system is also exponentially faster and can perform more parallel applications.

The other advantage is moving from nuclear materials to true superconductors. This allows for similar performance without as much exotic/hazardous materials.

I am very interested to see the immediate changes in the encryption standards as qubit processors become more commonplace. However my main interest lies in the accelerated evolution that these technologies will afford for developing true AI.

Link to this comment

phoenixamaranth

08/21/12 at 6:05 pm

Clearly the intent, and probably the funding, is for this to be used by government agencies to decrypt other nation's data. I don't think anyone has any plans of mass producing this for public use for at least a decade.

Link to this comment

adaptation

08/27/12 at 10:33 pm

Rebecca I liked your article, but the comments are even better.

Link to this comment

twmatthews

08/28/12 at 8:53 pm

I like Popsci. It beats the heck out of Popular Mechanics, for example.
I would like to ask Popsci, "Do you need a proofreader?"
You are a national, maybe worldwide magazine, and you don't seem to have anyone with a 4th grade reading level who can catch the ridiculous "factoring a prime number into its constituent parts" "the number 15".

Really? Are there no gatekeepers who take a look before the thing gets published? Apparently not.

Email me. I will do the job. Only asking 60k per year minimum, full benefits.

Link to this comment

berock212

02/22/13 at 11:44 pm

If a quantum computer can make better encryptions, then it can make better decryption. I think that before we could even start to make new encryptions, a quantum computer would decrypt the entire internet. But that's not the only thing a quantum computer could do. Eventually if we manage to make a quantum computer with no limit to the number of qubits you could fit in it and it was 100% accurate then we could probably simulate the entire universe. If we simulated the big bang on a quantum computer then we could simulate the entire universe if we give it a 100% accurate physics engine it would simulate the entire past present and future from the big bang onward. But that is not going to be in my lifetime.

Popular Tags

Science

All Tags All Photos All Videos

Science

+ More Photo Galleries

June 2013: American Energy Independence

Five amazing, clean technologies that will set us free, in this month's energy-focused issue. Also: how to build a better bomb detector, the robotic toys that are raising your children, a human catapult, the world's smallest arcade, and much more.