### A quantum computing solution for unstructured search

##### June 26, 2013

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 up 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.

Quantum computing, based on matter held in a quantum state, often for quite brief periods of time, takes advantage of an oddity of the quantum world in which a particle, like a photon or a boson, can exist in more than one state at once, a property called superposition. This would allow multiple possibilities to be considered simultaneously, though once measured, quantum objects will yeild a single answer.

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.

“It seems like we’re cheating somehow,” Wong said, exceeding the theoretical maximum speed, but on careful consideration of the resources required to accomplish this, he and Meyer determined that gains in speed would have physical costs.

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.”

This work was partially supported by the Defense Advanced Research Projects Agency (DARPA) as part of the Quantum Entanglement Science and Technology program and the Air Force Office of Scientific Research as part of the Transformational Computing in Aerospace Science and Engineering Initiative.

## Comments (7)

June 26, 2013by ivaray

Well, it seems like cheating, but it’s not! And you can justify. Sounds like postmodernism in mathematics, I wished this type of math was available when I was in the middle school or applicable for my bank account……..

June 26, 2013by someday69

Dr.Wong’got’the Re’tard’ed’step’child’..too walk…ok it’s with ah’limp..yet’

This is ah’very’use’full’…jar….is there’any’honey’in itj?

June 26, 2013by Eric Balingit

I like the idea of constructive and destructive wave functions for searching unsorted data, but what about high-dimensional relational database queries? I’m sure I’ve heard this mentioned somewhere as an area of interest.

June 26, 2013by Eric Balingit

Here is some recent work on quantum databases.

http://www.cs.cornell.edu/~sudip/QuantumDB.pdf

June 26, 2013by DeBee Corley

I ain’t smart enough to understand this.

You need the correct number of atoms?

June 26, 2013by melajara

I think he means the same number of atoms as data items, so in his example 1 million.

June 26, 2013by DAG

Nothing new here. It’s a very subtly different version of Simon’s algorithm… a quantum algorithm created in 1994 whose purpose and functionality is just like what this article describes.

The problem is not a lack of math and algorithms… we have a plethora already (not that more isn’t better)… what we need are engineering advances to take advantage of quantum mechanics.

Wong says “It seems like we’re cheating somehow”… maybe he should consult the father of quantum computing, David Deutsch… who would promptly tell him it seems like cheating because the information is coming from a multiverse. Wong’s justifications for the eerie feeling don’t up add up mathematically or physically.