Physicists use Bose-Einstein condensates to enhance factoring algorithm

November 10, 2008 By Lisa Zyga, feature
An absorption image of the expanding Bose-Einstein condensate, demonstrating the diffraction pattern which constitutes the factoring signal. Image credit: Mark Sadgrove, et al.

( -- Theoretically, quantum computing has the potential to work more efficiently and accurately than classical computing for certain processes, such as factoring. But quantum methods are experimentally challenging, since they often require tiny, fragile systems that are difficult to handle.

Recently, some approaches have suggested “rediscovering” old techniques such as analog computing, which usually lie outside the usual qubit architecture, in the hope of finding new pathways to experimentally realize quantum computation. For instance, using analog techniques and the quantum properties of atomic clusters called Bose-Einstein condensates, a team of researchers from Japan has recently improved upon a classical factoring algorithm.

“Any algorithm where the output is continuous rather than divided into bits (as on a digital computer) is analog,” Mark Sadgrove of the Japan Science and Technology Agency (JSTA) told “In our case, we measure quantities which are continuous in principle. By this I mean that the energy or the probability to find an atom with a given momentum are continuous variables, in theory. In practice, we use a finite number of atoms, so in some sense the final outputs are discrete, but theoretically the result of the computation is analog in nature.”

Sadgrove and his colleagues Sanjay Kumar of the University of Electro Communications (UEC) in Chofushi, Chofugaoka, and Ken’ichi Nakagawa, who has affiliations with both JSTA and UEC, have demonstrated that, compared with the classical implementation, their method can distinguish more accurately between factors and non-factors of large numbers. Specifically, their quantum system could increase the accuracy of a classical algorithm called the Gauss sum algorithm, a technique pioneered by Wolfgang Shleich of Ulm University in Germany.

Their quantum system consists of thousands of rubidium-87 atoms that are cooled to near absolute zero to form a Bose-Einstein condensate (BEC). At such a low temperature, the atoms’ wavelengths increase and overlap, so that the cluster becomes a single quantum state and obeys quantum laws, yet has a relatively large size.

The physicists zapped the BEC with a brief light pulse composed of two counter-propagating beams. They programmed one beam to have phase jumps (to displace the beam’s wavelength), while the second beam had no phase jumps. Programming the first beam served as the input method, representing an integer to be factored.

The dynamics of the atoms subject to the pulse could then be used to perform factoring calculations. After applying the pulse, the researchers allowed the BEC to expand freely for 14 ms. They then took an absorption image of the BEC, which showed that the pulse had separated the atoms in the BEC into different momentum orders. The atoms formed a diffraction pattern, based on the relative number of atoms in each momentum order, which the physicists could interpret as the “factoring signal.” Specifically, high-momentum atoms represented factors, and low-momentum atoms represented non-factors.

“You can think of the laser beam as containing the software (encoded by phase jumps) and the atoms as providing the hardware (their natural dynamics in response to the light field is what actually calculates the Gauss sum),” Sadgrove explained.

In contrast to the usual Gauss sum, which is fundamentally limited in its accuracy, the quantum method significantly outperformed the classical method, in some cases doubling the atomic visibility and offering near-perfect factoring.

“In our case, our current method is still slow – it doesn't make factoring easy,” Sadgrove said. “What we showed is that quantum mechanics offers an unexpected improvement to the Gauss sum method, overcoming a fundamental accuracy limit. If the atoms behaved classically, there would be no enhancement.”

The researchers noted that the higher accuracy comes at a cost of requiring more atoms, so the quantum method’s efficiency is about the same as that of the classical method. Nonetheless, as Sadgrove explained, the method offers a novel experiment in a field in which experiments are difficult to realize.

“You might know that everyone doing research in quantum information is excited about [Peter] Shor's algorithm for quantum factoring,” Sadgrove said. “Shor found a remarkable way to factor numbers using the quantum properties of interference and entanglement, which offers amazing savings in the time it takes for factoring a number. But Shor's algorithm is hard to implement. It's only been done successfully for up to the number 15 at the moment, and some people don't even consider that to be a real test due to some details about the way the algorithm works. So that's the current state of play regarding quantum factoring.”

He added that researchers continue to investigate Shor’s algorithm because of its potential impact on security: “In terms of applications, there's just one, but it's very important. If you could do real quantum factoring, then the RSA encryption used to do secure transactions in public situations would be no good anymore. That's because it relies on the fact that factoring large numbers is a hard problem. But quantum factoring makes it easy.”

In the future, the physicists hope to use entangled systems as a factoring method, which they say the present scheme is ideally suited for. They also plan to investigate the use of multiple, correlated atomic ensembles to perform factoring of different integers simultaneously.

“We would also like to extend the method beyond factoring,” Sadgrove said. “We can actually compute general ‘exponential sums’ with this method. A Gauss sum is a simple example of an exponential sum, as is a Fourier transform, which can be used to extract information about a signal. These so called ‘exponential sums’ are intricately tied to the most interesting parts of number theory, such as the distribution of prime numbers, which is still unknown. We think there may be other powerful applications of exponential sums apart from factoring.”

More information: Sadgrove, Mark; Kumar, Sanjay; and Nakagawa, Ken’ichi. “Enhanced Factoring with a Bose-Einstein Condensate.” Physical Review Letters, 101, 180502 (2008).

Copyright 2008
All rights reserved. This material may not be published, broadcast, rewritten or redistributed in whole or part without the express written permission of

Explore further: Seeing is believing—precision atom qubits achieve major quantum computing milestone

Related Stories

Quantum speed limit may put brakes on quantum computers

January 12, 2018

Over the past five decades, standard computer processors have gotten increasingly faster. In recent years, however, the limits to that technology have become clear: Chip components can only get so small, and be packed only ...

Recommended for you

Scientists create diodes made of light

March 16, 2018

Photonics researchers at the National Physical Laboratory (NPL) have achieved the extra-ordinary by creating a diode consisting of light that can be used, for the first time, in miniaturised photonic circuits, as published ...

Quantum speed limits are not actually quantum

March 15, 2018

Quantum mechanics has fundamental speed limits—upper bounds on the rate at which quantum systems can evolve. However, two groups working independently have published papers showing for the first time that quantum speed ...

The view from inside supersonic combustion

March 15, 2018

In a jet engine, the flow of air is slowed down to increase the temperature and pressure for combustion—burning fuel with the right ratio of fuel and air to conquer drag allows for acceleration.


Adjust slider to filter visible comments by rank

Display comments: newest first

4.6 / 5 (5) Nov 10, 2008
Even if it takes 100 more years, work like this will eventually lead to the creation of viable commercially economical quantum computers and quantum communications which will herald an avalanche of discovery and technology and will fundamentally change civilization as we know it.
3.9 / 5 (11) Nov 10, 2008
History suggests that there is no technology invented by man that has not been used to harm other men.

Your ignorance of history suggests to you that the 20th century was a particularly bloody one with its two world wars than any previous but you are very wrong.

The diffuse effect of many more petty despots having people executed, ethnic cleansings, higher murder rates, wars(civil and otherwise) and slave trading utterly dwarfs the violence of the 20th century. It was in fact one of unprecedented peace and prosperity unequaled in all of human history.

The moral creep is immensely powerful. Slavery was openly defended in much of the world; even by people now considered great moral thinkers for their work in other areas. Mahatma Gandhi isn't remembered as the racist bigot that he was because nearly all Indians were like him in that respect. Hitlers morals would have been nothing at all out of the ordinary in the 19th century. The american genocide of indian tribes is every bit as bloody and every bit as systematic as any of the 20th century but is isn't remembered as such.

Technology is what made this amazing achievement possible, especially the communications and recording technology. Where previously the act of ethnic cleansing would disappear completely down the memory hole or at best be found in the memoirs of some of the perpetrators as one of their life-achievements we now had pictures of piles of emaciated jewish corpses from world war II with proud german soldiers smiling for the camera; we had the writings, audio and video of survivors explaining their experience.

You need only compare the way that the German concentration camps are remembered as opposed to how the untold millions killed in relative anonymity by the Japanese are forgotten to realize the abillity to record history as it happens is so important.

Why do we want quantum computers again?

Because the rest of us aren't necessarily self-hating anti-humanists.
1.3 / 5 (6) Nov 10, 2008
No offense Soylent, but I don't think you made an even remotely effective rebuttal. Quantum suggested that History shows that Technology is always used for violent means. Just because you demonstrated that one era was comparatively less violent, that doesn't mean you've disproven his point; nor does it mean that technology per se is the source of peace. If anything, you sound like an Anti-Humanist by implying that it is technology, not human growth, that makes the world more peaceful. I'd actually go further to suggest that your view of History is more ignorant than his... but thats a different topic. ^.^
3.7 / 5 (3) Nov 11, 2008
This may be off topic to the other comments but...

what number did they factor with their method? How big?
3 / 5 (1) Nov 11, 2008
Sorry to say AdrianAnansi, but your criticism of Soylant as is faulty as Soylants' rebuttal of Quantum_Conundrum original spurious argument. You've implied that Soylant is anti-Humanist, but thats an empty strawman, stated a just-so story. You havent demonstrated to any conclusion that he/she is an anti-Humanist, and indeed whether "Humanism", or lack thereof, is the core disagreement between him/her and Quantum_Conundrum. Please try again.
4.7 / 5 (46) Nov 11, 2008

Sorry doris, but i'll have to criticize your criticism of Adrian's criticism of Soylant's criticism of Quantum's original criticism of technology, uselessly recursive and redundant, as the claim of humanism was as irrelevant to the criticism of anti-humanism and thus pointless in regard to whatever it was that was originally criticized in regard to technology.
4.6 / 5 (49) Nov 11, 2008
The presumption of Quantum's argument is that it is rational to choose not to advance in an understanding and use of nature, on the basis of knowledge of past crimes against humanity. If this choice could ever made,... the mentality who would use technology against other men, the motivating factor of that choice, ... would in effect have committed their greatest crime against the humanity.

Auto's are a technology, and kill some 40,000 per year just in the USA,... should be outlaw cars? Overall, technology has improved the human condition in all respects.

p.s. Global Warming is the greatest scam of the 21st century,... discuss.:) LOL
2.7 / 5 (3) Nov 11, 2008
Stupid people can use money to hire smart people!
We must restrict advance information for the safety of us all! Today we live in fear that stupid people can hire "smart" people to employ atomic weapons!
4.7 / 5 (48) Nov 11, 2008
That's true Earnhardt, but limiting the advance of technology is akin to holding back the ocean, and is the same as curling up into a a$$ ball out of fear. The good will fight the bad, as was done before, is done now, and will be done in the future.

The natural curiosity of man resulted in the atomic bomb,.. the problem is not the freedom to be curious, its the bad men and was in the stone age and will be in the future as well.
not rated yet Nov 12, 2008
I dont think that the natural curiosity of man is the driving force behind making technology kill people(atomic bomb). You can imagine a world with no bombs..
And I dont think you can blame it on "evil" either..
I think its more of a learned bad behavior. (With no parents around.)
So why do people get pleasure from power lust??

Technology can be good for people depending on the technology and the people...

4.8 / 5 (45) Nov 13, 2008
Brant, that is exactly what i'm saying, you can't blame technological advancement because the driving force of it is not a bad inherent quality of man in itself,... and because it's a inherent quality of man to advance, it's not something we can chose to shut off or on at will.

(I also don't think the use of the atomic bomb within it's context in WWII was an evil thing,... the point was that the cat was out of the bag due to the curiosity of man)

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.