Spatial Quantum Search
Quantum Search
Suppose you have some database of N classically stored pieces of data (say a telephone book with N entries) and that you don’t know anything about the structure of the database (e.g. you don’t know that telephone books are organized alphabetically). If you want to find a particular entry, you have to look at, on average, N/2 entries; you just plain have to look at each entry, one at a time. In other words, finding one entry among N requires O(N) operations (the number of operations is upper bounded by something that scales like N).
That’s if the data is stored and accessed classically. Can searches be performed more quickly if the information is stored and accessed Quanum Mechanically? As it turns out, the answer is “yes”.
Back in 1996, L. Grover presented at the Annual ACM Symposium on Theory of Computing under the title A fast quantum mechanical algorithm for database search. The resulting paper can also be found on the arXiv. In that paper, Grover showed that search on a quantum database can be performed in [tex]O(\sqrt{N})[/tex] operations. Naively, this speedup comes from the fact that we can examine multiple sites in the database at the same time by using superposition properties of quantum mechanics. That same year, the bound was shown to be tight (that is, any other quantum search algorithm scales with N at least as badly), and the following year, Grover’s algorithm was proven optimal (that is, no other quantum search algorithm outperforms it).
So great; store data on a quantum computer and you can search it faster. We already know Grover’s algorithm is better than or as good as any other. What else needs to be done?
It turns out there’s a very strong assumption Grover makes: that the sites in the database at which the pieces of data are stored are not spatially separated. What happens when the sites are allowed to be space-like separated is, to some extent, an open question. It’s that question I’m currently working on: Spatial Quantum Search.
So how do we connect space to the problem…?
very neat. I wonder how useful you find the big-Oh notation? There was an article in the recent Comms of the ACM about how CS would be more of a big-s ‘Science’ if we could transcend big-Oh.
What’s your take on that?
I find the notation very useful. Mostly because I need to distinguish between upper bounds, lower bounds and tight bounds all the time.
I’m not sure, though, what you mean by transcending big-Oh. Can you explain what the communication proposes/pointed out or give a link?
The direct quote is:
— Is Computer Science Science? Peter J. Denning, Communications of the ACM Vol 48, No 4, P27-31
I could see how in some more developed areas of computer science, more exact calculations of efficiency are needed. But I still think big-O gives one a simple way of finding revoluationary new algorithms — ones that aren’t going to shave a few processor cycles off here or there, but will be a whole new class of algorithm. And if quantum computing didn’t hold the promise of doing this in at least a few areas, there would be a lot less reason to work on it.
MDA, remind me to ask you at some stage exactly how this search algorithms work, especially the spacial ones — I’m interested to hear how one incorporates growing amounts of entanglement into the algorithm, as more data arrives — if indeed that is what is done.
Uber, Well… we don’t have any real sets of data. I suppose it’s possible, but some better measure will entirely depend on the physical implementation of the quantum computer (which does not yet exist).
Better, theoretical models can be used to model the system (please note I’ve played a little fast and loose with the one I’ve described), but they become intractable fast. I think it’s typically easier to roll higher order effects into your error analysis.
Also, be wary of changing the problem under examination. Take as an example classical search on a database about whose structure you know nothing. As soon as you mention real world data, you’re probably talking about a different problem: classical search on a database about whose structure you can get away with assuming something(s).
Which problem is more useful is up for debate.
Paul.za, that’s not really what happens, though perhaps I don’t understand your question. Most of the search problems we consider only deal with finding one piece of information. What the rest of the pieces in the database are we never care about.
Most algorithms set up a clever Hamiltonian and evolve the system for a fixed time. If the algorithm does it’s job, you end up in the desired location with high probability.
At the moment, I’m working on lower bounds, though. Currently, I’m a bit less familiar with algorithmic work, which deals with upper bounds.
[…] uation Filed under: Uncategorized — jjk @ 12:33 am Following the lead of Paul and Mike, I have decided to write a little bit about what I work on at Caltech. But, instead of writing […]
Yeah yeah yeah… computer modeling or pencil-and-paper or whatever you do, that’s all very nice. But can you Crochet it?
Hey Mike. I found your site through Holly’s. This is interesting stuff, and while I don’t understand most of it, I am excited about the implications of quantum computing. I’ll be able to play cooler video games at higher frame rates!!
L, no I cannot
:)James, thanks for dropping by. I’ll let you know when the first Quantum Algorithm based version of the Half Life engine comes out.
[…] Let me offer you my perspective; Greg’s mileage may vary. Over the past several years (perhaps since senior year of college), my attention span has been diminishing (thankfully, only algebraically). I blame only myself and my lack of rigour. Nevertheless, my lacking in the powers of concentration has severely limited my ability to perform certain tasks like determining a tight bound on spatial quantum search, understanding the nuances of quantum pattern matching, or shaving. […]