Physics

Quantum Computing Breakthrough With New Algorithm

Mark Hoffman
First Posted: Feb 26, 2013 02:09 PM EST

Quantum computing is still in its early infancy, but is evolving quickly. In what could be compared to solving the first simple puzzle by itself, an international research group has demonstrated a quantum algorithm that performs a true calculation for the first time.

The team, led by scientists from the University of Bristol, UK, and the University of Queensland, Australia, implemented the "phase estimation algorithm" - a central quantum algorithm that achieves an exponential speedup over all classical algorithms.

It lies at the heart of quantum computing and is a key subroutine of many other important quantum algorithms, such as Shor's factoring algorithm and quantum simulations--which are among the reasons that quantum computers will be much, much faster than current computers.

"Before our experiment, there had been several demonstrations of quantum algorithms, however, none of them implemented a quantum algorithm without knowing the answer in advance, said Dr Xiao-Qi Zhou, who led the project. "This is because in the previous demonstrations, the quantum circuits were simplified to make it more experimentally feasible.

"However, this simplification of circuits required knowledge of the answer in advance.  Unlike previous demonstrations, we built a full quantum circuit to implement the phase estimation algorithm without any simplification. We don't need to know the answer in advance and it is the first time the answer is truly calculated by a quantum circuit with a quantum algorithm."

According to Professor Jeremy O'Brien, director of the Centre for Quantum Photonics at the University of Bristol,"Implementing a full quantum algorithm without knowing the answer in advance is an important step towards practical quantum computing.  It paves the way for important applications, including quantum simulations and quantum metrology in the near term, and factoring in the long term."

Paper:

Xiao-Qi Zhou et al., Calculating Unknown Eigenvalues with a Quantum Algorithm, arXiv, 2011, arxiv.org/abs/1110.4276

See Now: NASA's Juno Spacecraft's Rendezvous With Jupiter's Mammoth Cyclone

More on SCIENCEwr