more articles like this

Composite Number Factoring
updated: Aug 20, 2012, 11:00 AM

Source: UCSB

Computing prime factors may sound like an elementary math problem, but try it with a large number, say one that contains more than 600 digits, and the task becomes enormously challenging and impossibly time-consuming. Now, a group of researchers at UC Santa Barbara has designed and fabricated a quantum processor capable of factoring a composite number -- in this case the number 15 -- into its constituent prime factors, 3 and 5.

Although modest compared to a 600-digit number, the achievement represents a milestone on the road map to building a quantum computer capable of factoring much larger numbers, with significant implications for cryptography and cybersecurity. The results are published in the advance online issue of the journal Nature Physics.

"Fifteen is a small number, but what's important is we've shown that we can run a version of Peter Shor's prime factoring algorithm on a solid state quantum processor. This is really exciting and has never been done before," said Erik Lucero, the paper's lead author. Now a postdoctoral researcher in experimental quantum computing at IBM, Lucero was a doctoral student in physics at UCSB when the research was conducted and the paper was written.

"What is important is that the concepts used in factoring this small number remain the same when factoring much larger numbers," said Andrew Cleland, a professor of physics at UCSB and a collaborator on the experiment. "We just need to scale up the size of this processor to something much larger. This won't be easy, but the path forward is clear."

Practical applications motivated the research, according to Lucero, who explained that factoring very large numbers is at the heart of cybersecurity protocols, such as the most common form of encoding, known as RSA encryption. "Anytime you send a secure transmission -- like your credit card information -- you are relying on security that is based on the fact that it's really hard to find the prime factors of large numbers," he said. Using a classical computer and the best-known classical algorithm, factoring something like RSA Laboratory's largest published number -- which contains over 600 decimal digits -- would take longer than the age of the universe, he continued.

A quantum computer could reduce this wait time to a few tens of minutes. "A quantum computer can solve this problem faster than a classical computer by about 15 orders of magnitude," said Lucero. "This has widespread effect. A quantum computer will be a game changer in a lot of ways, and certainly with respect to computer security."

So, if quantum computing makes RSA encryption no longer secure, what will replace it? The answer, Lucero said, is quantum cryptography. "It's not only harder to break, but it allows you to know if someone has been eavesdropping, or listening in on your transmission. Imagine someone wiretapping your phone, but now, every time that person tries to listen in on your conversation, the audio gets jumbled. With quantum cryptography, if someone tries to extract information, it changes the system, and both the transmitter and the receiver are aware of it."

To conduct the research, Lucero and his colleagues designed and fabricated a quantum processor to map the problem of factoring the number 15 onto a purpose- built superconducting quantum circuit. "We chose the number 15 because it is the smallest composite number that satisfies the conditions appropriate to test Shor's algorithm -- it is a product of two prime numbers, and it's not even," he explained.

The quantum processor was implemented using a quantum circuit composed of four superconducting phase qubits -- the quantum equivalents of transistors -- and five microwave resonators. The complexity of operating these nine quantum elements required building a control system that allows for precise operation and a significant degree of automation -- a prototype that will facilitate scaling up to larger and more complex circuits. The research represents a significant step toward a scalable quantum architecture while meeting a benchmark for quantum computation, as well as having historical relevance for quantum information and cryptography.

"After repeating the experiment 150,000 times, we showed that our quantum processor got the right answer just under half the time" Lucero said. "The best we can expect from Shor's algorithm is to get the right answer exactly 50 percent of the time, so our results were essentially what we'd expect theoretically."

The next step, according to Lucero, is to increase the quantum coherence times and go from nine quantum elements to hundreds, then thousands, and on to millions. "Now that we know 15=3x5, we can start thinking about how to factor larger -- dare I say -- more practical numbers," he said.

Other UCSB researchers participating in the study include John Martinis, professor of physics; Rami Barends, Yu Chen, Matteo Mariantoni, and Y. Yin, postdoctoral fellows in physics; and physics graduate students Julian Kelly, Anthony Megrant, Peter O'Malley, Daniel Sank, Amit Vainsencher, Jim Wenner, and Ted White.

Comments in order of when they were received | (reverse order)

COMMENT 310360	2012-08-20 11:06 AM
Say WHAT?
COMMENT 310393	2012-08-20 12:14 PM
Knock, Knock. Who's There? Ennis Hay. Ennis Hay who?
COMMENT 310444P	2012-08-20 01:28 PM
cooooooooooool. politics and partying aside ucsb is such an awesome fixture in the community.
COMMENT 310484	2012-08-20 02:58 PM
The concept of solving a problem in multiple, parallel universes and having the one solution for ours appear here is hard to fathom. Whomever owns this owns the key to all encrypted data. Privacy go bye bye.
COMMENT 310536	2012-08-20 04:32 PM
I could do it for about a billion dollars less per computation. Quantum computing will remain an academic joke forever.
COMMENT 310543P	2012-08-20 05:07 PM
536 - Please tattoo that on your forehead for future reference when q-comp is in every iPhone.
COMMENT 310562	2012-08-20 06:35 PM
543, you think cold fusion is right around the corner too, eh?
COMMENT 310563P	2012-08-20 06:45 PM
536 - Nope. The cold fusion stuff was released without peer review, and was mostly fantasy. Quantum computing is pretty well established, more like actual fusion, but a little easier to do. Should I make assumptions about some of your thought processes, ones that you haven't made obvious in your comments?
COMMENT 310574	2012-08-20 07:21 PM
@310536 in re cold fusion, that's a fallacy of denial of the antecedent and an example of what Quine called "nefarious rhetoric". Also, your implication that, because initial quantum computing is focused on known problems easily solved with other technologies that it won't go anywhere is obviously fallacious. Call me crazy, but I'll go with the computational physicists with soaring IQs over the contra-logical opinions of an unknown internet commenter.
COMMENT 310577	2012-08-20 07:37 PM
@484 sounds more like modern codes become child's play and to play on an even field everyone will have to go quantum.
COMMENT 310587P	2012-08-20 08:02 PM
And once the NP-complete "halting problem" is solved, Windoze may finally work!
COMMENT 310640P	2012-08-21 07:16 AM
I love these UCSB news releases; if only I understood what they were talking about (it's not them; it's me).
COMMENT 310641P	2012-08-21 07:17 AM
Like I said, I love these UCSB press releases...
COMMENT 310654	2012-08-21 07:58 AM
574, my problem with quantum computing is not that it won't eventually work, it's that it is taking a ridiculous amount of money to fund something the human race just doesn't need. The researchers even stated they're getting the correct prime factors of 15 less than half the time, and we're supposed to be dazzled? Think of all the problems our society could solve with this cash and brainpower. On the other hand, nuclear fusion is truly a fantasy as it will always require more energy input than output. Oh, and how do you know my IQ ain't soaring? That was the only fallacious assumption in this thread! I just don't believe in the advancement of geek anymore. Computing speed is not what is holding our species back.
COMMENT 310665	2012-08-21 08:07 AM
310536 - Actually, yes. Cold fusion (in a way) IS right around the corner. The E-Cat, a low-energy nuclear reactor, will probably be available for home use in a year or two. Andrea Rossi is still being (rightly) secretive about his product, but that's simply because it will change energy usage as we know it, and there are companies out there worth a combined multi-trillion dollars that would not want to see this product put on the market.
COMMENT 310784	2012-08-21 11:21 AM
My sentiments exactly, 640P. :-D I shoulda stayed in school....
COMMENT 310793	2012-08-21 11:38 AM
@310543P The halting problem is not NP-complete, it is undecidable. @310536 They get the solution only half the time because that's the way the algorithm works ... it's statistical. Lack of understanding of the technology certainly could be a basis for not being dazzled by it. Also, I did not assume anything about your IQ ... that's another of your fallacies; what I said was that, other than the numerous errors in logic you have demonstrated here, you are "unknown". But if your IQ is soaring, then you're holding back here.

35% of comments on this page were made by Edhat Community Members.

*** One comment was removed from this thread by the Edhat Board Nanny for violating Edhat Comments Board policy. Click Here to see it.