Posted: Mar 04, 2011 
New algorithm raises hopes that some of the barriers blocking the wider application of quantum computing could soon be solved

(Nanowerk News) In recent years, quantum computers have lost some of their lustre. However, a new quantum algorithm, which shows how a quantum computer could be used to simulate a complex system of interacting particles, raises hopes that some of the barriers blocking the wider application of quantum computing could soon be solved.

The study, presented in the journal Nature ("Quantum Metropolis sampling"), was partly supported by the EU through the QUERG ('Quantum entanglement and the renormalization group') and QUEVADIS ('Quantum engineering via dissipation') projects. QUERG clinched more than EUR 1.2 million from the European Research Council (ERC) under the Ideas Programme of the Seventh Framework Programme (FP7), while QUEVADIS has been allocated EUR 10 million under FP7's 'Information and communication technologies' Theme.

Quantum technology exploits the weird properties of matter at extremely small scales. Where a bit in a classical computer can represent either a '1' or a '0,' a quantum bit  or qubit  can represent '1' and '0' at the same time. Two qubits can represent four values simultaneously, three qubits eight, and so on.

Under the right circumstances, performing computations with quantum bits is the equivalent of carrying out multiple classical computations in parallel. But the right circumstances are much rarer than was first anticipated by scientists.

'The original motivation to build a quantum computer came from Richard Feynman, who imagined a machine capable of simulating generic quantum mechanical systems  a task that is believed to be intractable for classical computers,' the researchers write.

Over the past decade, quantum computers with some 12 or 16 qubits have been built in the laboratory; but quantum computation is such a young field, and the physics of it are so counterintuitive, that researchers are still developing the theoretical tools for thinking about it.

To better understand the physics of a quantum system of interacting particles, the researchers, from Austria, Canada and Germany, tried to work out how the changes a quantum system undergoes could be reproduced on a universal quantum computer. To do this, they looked for a quantum version of the classical Metropolis algorithm.

Named after the physicist Nicholas Metropolis, who was part of the group that came up with it, the Metropolis algorithm appeared in 1953 but didn't find practical use until the first computers arrived. The classical version of the Metropolis algorithm used stochastic maps that converged (over many iterations) to the equilibrium state.

For the quantum version of the Metropolis algorithm, the team used completely positive maps of probability amplitudes instead; although this did introduce a few problems along the way, notably the introduction of quantum phase transitions that may lead to inaccurate computations.

Nonetheless, the implementation of the new quantum algorithm could have farreaching applications in the fields of chemistry, condensed matter and high energy physics, where until today the Schrödinger equation remains unsolved for complex systems of many interacting particles.

'Even though an implementation of this algorithm for fullscale quantum manybody problems may be out of reach with today's technological means, the algorithm is scalable to system sizes that are interesting for actual physical simulations,' claim the researchers.
