Spatial Quantum Search
Following Paul.za’s lead, I’ve decided to write up a brief sketch of some of the background behind my current research: Quantum Spatial Search. Be warned, this is the longest post blogwaffe has ever seen. Skip to the last page of this post and read the last line if you want the short of it. For the long of it, read on.
Use the little page numbers below to navigate this post.
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. […]