A Quantum Computer Finds Factors
A Quantum Computer Finds Factors
Written by Mike James   
Tuesday, 21 August 2012

The Shor quantum factoring algorithm has been run for the first time on a solid state device and it successfully factored a composite number. Is this the start of the quantum computing revolution?

Quantum computing is promised to provide many amazing advantages, but the one that is uppermost in the collective consciousness is its ability to factor numbers. The reason for this concern is that the Public Key Infrastructure (PKI) depends on the factoring of large numbers (600 digits or more) being a difficult task for a standard algorithm. In simple terms, public cryptography depends on the asymmetry between multiplying two primes together - easy - and factoring the number that results - difficult.

A quantum computer, on the other hand, promises to factor a number of any size in one operation and,  if one can be built, the future of the PKI looks bleak and we would have to find encryption methods that were safe against a quantum attack.

Until recently the idea of factoring using a quantum computer was just that - an idea. Actually making a quantum computer is a difficult task because of the need to maintain an entangled state between the quantum bits  - qubits. This is a task that gets more difficult as the number of qubits increases.

 quantumchipfactors

 

Now a team from UCSB has managed to build and operate a quantum circuit composed of four superconducting phase qubits. The complexity of operating these quantum elements required building a control system that allows for precise operation and a significant degree of automation. This prototype will facilitate scaling up to larger and more complex circuits. However, there are still a few computer scientists who believe that a useful quantum computer cannot be built because there is some deep law of nature that makes it more difficult the more qubits you try to use.

In this case the design creates entangled bits faster than before and the team verified that entanglement was happening using quantum tomography. The final part of the experiment implemented the Shor factoring algorithm using 15 as the value to be factored.  In 150,000 runs of the calculation, the chip gave the correct result 48% of the time. As Shor's algorithm is only supposed to give the correct answer 50% of the time, this is a good result.

Of course, factoring 15 isn't something that is going to threaten the PKI and cryptography in general, but factoring  larger numbers is just a matter of increasing the number of qubits and this approach does seem to be a scalable solid state approach.

More Information

Paper published in Nature Physics (subscription required):

http://www.nature.com/nphys/journal/vaop/ncurrent/full/nphys2385.html

Preprint(free pdf):

Computing prime factors with a Josephson phase qubit quantum processor

Related Articles

$100,000 Prize For Proving Quantum Computers Are Impossible

NYT on the Future of Computing

Spintronics 

 

 
 
 

blog comments powered by Disqus

 

To be informed about new articles on I Programmer, install the I Programmer Toolbar, subscribe to the RSS feed, follow us on, Twitter, Facebook, Google+ or Linkedin,  or sign up for our weekly newsletter.

 

Banner


Microsoft Student Contests Emphasize Azure
12/11/2016

Microsoft has increased the prize money for the 2017 Imagine cup and introduced an additional stipulation, Azure is required for all projects. Microsoft is also running a Hello Cloud contest for  [ ... ]



//No Comment - Three Videos, Alan Kay, Donald Knuth & Bjarne Stroustrup
25/11/2016

• Joe Armstrong interviews Alan Kay

• Donald Knuth Scientist 

• The Design of C++ , lecture by Bjarne Stroustrup 


More News

Last Updated ( Tuesday, 21 August 2012 )
 
 

   
RSS feed of news items only
I Programmer News
Copyright © 2016 i-programmer.info. All Rights Reserved.
Joomla! is Free Software released under the GNU/GPL License.