Tom Wong, a graduate student in physics and David Meyer, professor of mathematics at the University of California, San Diego, have proposed a new algorithm for quantum computing that will speed a particular type of problem. But swifter calculations would come at the cost of greater physical resources devoted to precise timekeeping, their analysis has determined.
Their algorithm would be used to conduct a task called an unstructured search. The goal is to locate a particular item within an unsorted pile of data. Solving this problem on a classical computer, which uses 1s and 0s stored on magnetic media, is akin to flipping through a deck of cards, one by one, Wong said. Searching through a large data set could take a very long time.
The trick then, is to design algorithms so that wrong answers cancel out and correct answers accumulate. The nature of those algorithms depends on the medium in which information is stored.
Meyer and Wong considered a computer based on a state of matter called a Bose-Einstein condensate. These are atoms caught in an electromagnetic trap and chilled so cold that they “fall” into a shared lowest quantum state and act as one.
The equation usually used to describe quantum systems is linear, but the one that approximates the state of a Bose-Einstein condensate has a term that is cubed. They propose computing with this cubic equation which will more rapidly converge on the answer. For example, their algorithm can be made to search for a particular item among a million items in the same time it would take to search among ten items.
New Journal of Physics – Nonlinear quantum search using the Gross–Pitaevskii equation
We solve the unstructured search problem in constant time by computing with a physically motivated nonlinearity of the Gross–Pitaevskii type. This speedup comes, however, at the novel expense of increasing the time-measurement precision. Jointly optimizing these resource requirements results in an overall scaling of N^(1/4). This is a significant, but not unreasonable, improvement over the N^(1/2) scaling of Grover’s algorithm. Since the Gross–Pitaevskii equation approximates the multi-particle (linear) Schrödinger equation, for which Grover’s algorithm is optimal, our result leads to a quantum information-theoretic lower bound on the number of particles needed for this approximation to hold, asymptotically.
Because the search is so sudden, timekeeping, which uses an atomic clock, would have to be very precise. This requirement sets a lower limit on the number of ions that make up the atomic clock.
The other resource is the computing medium itself, the Bose-Einstein condensate. “If we want to run this algorithm, we’re going to need a certain number of atoms,” Wong said. “This is how many atoms we need for this nonlinear equation to be valid, to be a correct approximation of the underlying quantum theory. That is new.”
The paper shows that nonlinear systems can be utilized to perform computation faster than linear systems, but this speedup requires other physical resources. In our specific example, the additional resources are the clock to achieve sufficiently high time-measurement precision, and the number of particles in the BEC.
If you liked this article, please give it a quick review on ycombinator or StumbleUpon. Thanks
Brian Wang is a Futurist Thought Leader and a popular Science blogger with 1 million readers per month. His blog Nextbigfuture.com is ranked #1 Science News Blog. It covers many disruptive technology and trends including Space, Robotics, Artificial Intelligence, Medicine, Anti-aging Biotechnology, and Nanotechnology.
Known for identifying cutting edge technologies, he is currently a Co-Founder of a startup and fundraiser for high potential early-stage companies. He is the Head of Research for Allocations for deep technology investments and an Angel Investor at Space Angels.
A frequent speaker at corporations, he has been a TEDx speaker, a Singularity University speaker and guest at numerous interviews for radio and podcasts. He is open to public speaking and advising engagements.