The latest news from academia, regulators
research labs and other things of interest
Posted: December 27, 2007
Realization of Shor's algorithm on an optical quantum computer
(Nanowerk News) A research team led by Prof. PAN Jianwei with the University of Science and Technology of China (USTC), the Chinese Academy of Sciences (CAS), has been successful in performing Shor's algorithm, a quantum algorithm for factorization, on an optical quantum computer. The feat is also accomplished independently by another team led by Andrew White from the University of Queensland in Brisbane, Australia. Both results were published in the December 19 Physics Review Newsletters.
Well-known in quantum computing field, the algorithm is first proposed by US mathematician Peter Shor in the mid-1990s. He theoretically demonstrated that, by taking advantage of the parallelism of quantum computing, the algorithm is able to quickly factor a large number, which could make a quantum computer rapidly crack such widely-used cryptographic codes as the RSA public key system, posing a serious threat to information security in business transactions on the Internet, such as e-commerce. As a result, the algorithm has rekindled a worldwide concern, triggering an upsurge of investments in the studies of quantum computation. It is expected to exert a far-reaching and enduring impact on the business operation and national security in today's world.
However, it is no picnic to perform the algorithm on a quantum computer. In 2001, researchers from IBM and Stanford University demonstrated the factorization of the number 15 using nuclear magnetic resonance technology (NMR). Because of the inherent pitfalls of NMR itself, the experiment failed to exhibit the algorithm's quantum characteristics and be scaled up, hindering its further application.
In order to realize a true state of the Shor algorithm with quantum characteristics, Prof. Pan and his colleagues in Hefei National Laboratory for Physical Sciences at the Microscale under USTC, including LU Chaoyang, Daniel E. Browne and YANG Tao, experimentally showed a complied version of Shor's algorithm using four photonic qubits. They chose the simplest instance of this algorithm, that is, factorization of "N=15" and exploit a simplified linear optical network to coherently implement the quantum circuits of the modular exponential execution and semi-classical quantum Fourier transformation. During this computation, genuine multiparticle entanglement is observed which well supports its quantum nature. This experiment represents an essential step toward full realization of Shor's algorithm and scalable linear optics quantum computation.
The achievement has received world-wide concern and interest. It was a necessary step toward photon-based quantum computers, says Prof. Seth Lloyd from MIT. The achievement appears to be "the first experimental demonstrations of true (though rudimentary) quantum mechanical computations," comments Innovation Report, a German website on science and technology.
To find the prime factors of 15 is a simple mathematical question, however, the work is significant as we have done it by manipulating the quantum states of photons, says Prof. Pan. Although the current form of the quantum computer is quite primitive, just like a toddler. When it is well developed, Pan believes, the performance of a quantum computer is bound to excel all kinds of the classical computers now in operation.