Quantum computer factors numbers, could be scaled up

March 3, 2016 by Jennifer Chu, Massachusetts Institute of Technology
Researchers have designed and built a quantum computer from five atoms in an ion trap. The computer uses laser pulses to carry out Shor’s algorithm on each atom, to correctly factor the number 15. Credit: Jose-Luis Olivares/MIT

What are the prime factors, or multipliers, for the number 15? Most grade school students know the answer—3 and 5—by memory. A larger number, such as 91, may take some pen and paper. An even larger number, say with 232 digits, can (and has) taken scientists two years to factor, using hundreds of classical computers operating in parallel.

Because factoring large numbers is so devilishly hard, this "factoring problem" is the basis for many encryption schemes for protecting credit cards, state secrets, and other confidential data. It's thought that a single computer may easily crack this problem, by using hundreds of atoms, essentially in parallel, to quickly factor huge numbers.

In 1994, Peter Shor, the Morss Professor of Applied Mathematics at MIT, came up with a quantum algorithm that calculates the prime factors of a large number, vastly more efficiently than a classical computer. However, the algorithm's success depends on a computer with a large number of . While others have attempted to implement Shor's algorithm in various quantum systems, none have been able to do so with more than a few quantum bits, in a scalable way.

Now, in a paper published today in the journal Science, researchers from MIT and the University of Innsbruck in Austria report that they have designed and built a quantum computer from five atoms in an ion trap. The computer uses laser pulses to carry out Shor's algorithm on each atom, to correctly factor the number 15. The system is designed in such a way that more atoms and lasers can be added to build a bigger and faster quantum computer, able to factor much larger numbers. The results, they say, represent the first scalable implementation of Shor's algorithm.

"We show that Shor's algorithm, the most complex quantum algorithm known to date, is realizable in a way where, yes, all you have to do is go in the lab, apply more technology, and you should be able to make a bigger quantum computer," says Isaac Chuang, professor of physics and professor of electrical engineering and computer science at MIT. "It might still cost an enormous amount of money to build—you won't be building a quantum computer and putting it on your desktop anytime soon—but now it's much more an engineering effort, and not a basic physics question."

Seeing through the quantum forest

In classical computing, numbers are represented by either 0s or 1s, and calculations are carried out according to an algorithm's "instructions," which manipulate these 0s and 1s to transform an input to an output. In contrast, quantum computing relies on atomic-scale units, or "qubits," that can be simultaneously 0 and 1—a state known as a superposition. In this state, a single qubit can essentially carry out two separate streams of calculations in parallel, making computations far more efficient than a classical computer.

In 2001, Chuang, a pioneer in the field of , designed a quantum computer based on one molecule that could be held in superposition and manipulated with nuclear magnetic resonance to factor the number 15. The results, which were published in Nature, represented the first experimental realization of Shor's algorithm. But the system wasn't scalable; it became more difficult to control the system as more atoms were added.

"Once you had too many atoms, it was like a big forest—it was very hard to control one atom from the next one," Chuang says. "The difficulty is to implement [the algorithm] in a system that's sufficiently isolated that it can stay quantum mechanical for long enough that you can actually have a chance to do the whole algorithm."

"Straightforwardly scalable"

Chuang and his colleagues have now come up with a new, scalable quantum system for factoring numbers efficiently. While it typically takes about 12 qubits to factor the number 15, they found a way to shave the system down to five qubits, each represented by a single atom. Each atom can be held in a superposition of two different energy states simultaneously. The researchers use laser pulses to perform "logic gates," or components of Shor's algorithm, on four of the five atoms. The results are then stored, forwarded, extracted, and recycled via the fifth atom, thereby carrying out Shor's algorithm in parallel, with fewer qubits than is typically required.

The team was able to keep the quantum system stable by holding the atoms in an ion trap, where they removed an electron from each atom, thereby charging it. They then held each atom in place with an electric field.

"That way, we know exactly where that atom is in space," Chuang explains. "Then we do that with another atom, a few microns away—[a distance] about 100th the width of a human hair. By having a number of these atoms together, they can still interact with each other, because they're charged. That interaction lets us perform logic gates, which allow us to realize the primitives of the Shor factoring algorithm. The gates we perform can work on any of these kinds of atoms, no matter how large we make the system."

Chuang's team first worked out the quantum design in principle. His colleagues at the University of Innsbruck then built an experimental apparatus based on his methodology. They directed the quantum system to factor the number 15—the smallest number that can meaningfully demonstrate Shor's algorithm. Without any prior knowledge of the answers, the system returned the correct factors, with a confidence exceeding 99 percent.

"In future generations, we foresee it being straightforwardly scalable, once the apparatus can trap more and more laser beams can control the pulses," Chuang says. "We see no physical reason why that is not going to be in the cards."

What will all this eventually mean for encryption schemes of the future?

"Well, one thing is that if you are a nation state, you probably don't want to publicly store your secrets using encryption that relies on factoring as a hard-to-invert problem," Chuang says. "Because when these quantum computers start coming out, you'll be able to go back and unencrypt all those old secrets."

Explore further: Simon's algorithm run on quantum computer for the first time—faster than on standard computer

More information: "Realization of a scalable Shor algorithm," Science (2016). DOI: 10.1126/science.aad9480

Related Stories

New largest number factored on a quantum device is 56,153

November 28, 2014

(Phys.org)—Researchers have set a new record for the quantum factorization of the largest number to date, 56,153, smashing the previous record of 143 that was set in 2012. They have shown that the exact same room-temperature ...

Quantum computing advance locates neutral atoms

August 12, 2015

For any computer, being able to manipulate information is essential, but for quantum computing, singling out one data location without influencing any of the surrounding locations is difficult. Now, a team of Penn State physicists ...

Quantum algorithm breakthrough

February 24, 2013

An international research group led by scientists from the University of Bristol, UK, and the University of Queensland, Australia, has demonstrated a quantum algorithm that performs a true calculation for the first time. ...

Physicists demonstrate that 15=3x5 about half of the time

August 19, 2012

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, ...

Recommended for you

Researchers study interactions in molecules using AI

October 19, 2018

Researchers from the University of Luxembourg, Technische Universität Berlin, and the Fritz Haber Institute of the Max Planck Society have combined machine learning and quantum mechanics to predict the dynamics and atomic ...


Adjust slider to filter visible comments by rank

Display comments: newest first

1 / 5 (2) Mar 03, 2016
NO IDIOT in this World to COMMENT on this?
This Planet is supposed to be BIG!
1 / 5 (2) Mar 03, 2016
Obama should IMMEDIATELY DIVERT $10B to these guys.
ALL Defense/Offense PROJECTS should YIELD!
Just like Right of Way given to VIP's Car here OR Elsewhere on the H'way!
1 / 5 (2) Mar 03, 2016
THIS WORLD Does NOT Need SICK IDIOT, TRUMP (Of course, only if HE is one belonging to that Category), but Only THESE Marvellous GUYS.
Kick out Gods+Religions...EMBRACE These Guys!
Otherwise, All Those of Future will just Laugh at you & Xshttttttt on YOU...Your Faces will be The Worst Areas to be Affected by That!
No Paper Towel will help in WIPING THAT OFF out of your Face/Coffin!
1 / 5 (2) Mar 03, 2016
Halifax scientist's breakthrough gene work stalled by lack of funding
A Halifax scientist has made a breakthrough when it comes to gene editing that ... It's really changing the way that we are able to do cancer research
5 / 5 (2) Mar 03, 2016
The FBI would like one. They have an iPhone to break.

But seriously, what are the banks going to do when they cant secure transactions anymore?
1024 or 2048 or 4096 etc.bit encryption will only last till the next breakthrough.

Blockchain (the newest kid on the banking security block) will only last until a big enough PC zombie army attacks the chain simultaneously.

There will suddenly be a market for banking quantum cryptologists.
1 / 5 (2) Mar 03, 2016
Halifax scientist's breakthrough gene work stalled by lack of funding
A Halifax scientist has made a breakthrough when it comes to gene editing that ... It's really changing the way that we are able to do cancer research
Gene editing technique that allows for the editing of genomes – organism's complete set of DNA – with unheard of precision.Dr. Graham Dellaire, a researcher at Dalhousie University, has created a new technique that will work with CRISPR to help researchers measure how efficient gene therapy is."We've really added to the toolbox for researchers internationally to be able to look at the effectiveness of their compounds and enhancing CRISPR," Dellaire said
gene @globalhalifax pic.twitter.com/9vvmBuCurs
1 / 5 (2) Mar 03, 2016
Natasha Pace (@NatashaPace) March 3, 2016"It's very rare that you would see a game changing technology like this come along," said research associate Jayme Slasman."So it's been an incredible opportunity to kind of be a part of how we use this and how we implement this."Aiming at cancers, genetic diseasesThe hope is that this new technique could lead researchers closer to finding cures for genetic diseases and learning more about how cancers are treated."It's really changing the way that we are able to do cancer research here in our own lab," said Salsman.Dellaire has already had requests from scientists around the world. But the future of his lab, and labs of fellow researchers across the country, remains unclear as all research scientists in Canada are fighting for a share of the same funding."We can't maintain status quo, never mind be competitive when we're all holding our breath," said Dellaire.
1 / 5 (2) Mar 03, 2016
Dellaire says he's ready to move on to the next phase of his research, which would include using animal models to correct muscle disease, but he's at a stand still due to the lack of funds."This laboratory has enough operating funds to operate for one year with no additional funding. Next year, I'm going to have to lay off at least one employee. The following year, all my students will have to graduate," said Dellaire."That means the research in this lab will stop."CRISPR was recently named 2015's breakthrough discovery of the year.
1 / 5 (2) Mar 03, 2016
Using his knowledge of how genes are organized and repaired in human cells, Dr. Graham Dellaire, Dalhousie Medical School's Cameron Research Scientist in Cancer Biology, has developed a technique that could make gene therapy more effective and safer to use. His work was recently published in Nucleic Acids Research and Nature.
3.7 / 5 (6) Mar 04, 2016
I see BE forgot to take their meds.
not rated yet Mar 06, 2016
BE tldr; Some of your points may be valid, but you couch them in such bombastic ranting & shouting that I gave you a 1 for every post.

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.