Last year, a company called DWave Systems announced their quantum computer (the ‘Orion’) – another milestone on the road to practical quantum computing. Their controversial claims seem worthy in their own right but they are particularly important to the semantic web (SW) community. The significance to the SW community was that their quantum computer solved problems akin to Grover’s Algorithm speeding up queries of disorderly databases.

Semantic web databases are not (completely) disorderly and there are many ways to optimize the search for matching triples to a graph pattern. What strikes me is that the larger the triple store, the more compelling the case for using some kind of quantum search algorithm to find matches. DWave are currently trialing 128qbit processors, and they claim their systems can scale, so I (as a layman) can see no reason why such computers couldn’t be used to help improve the performance of queries in massive triple stores.

What I wonder is:

- what kind of indexing schemes can be used to impose structure on the triples in a store?
- how can one adapt a B-tree to index each element of a triple rather than just a single primary key – three indexes seems extravagant.
- are there quantum algorithms that can beat the best of these schemes?
- is there is a place for quantum superposition in a graph matching algorithm (to simultaneously find matching triples then cancel out any that don’t match all the basic graph patterns?)
- if DWave’s machines could solve NP-Complete problems, does that mean that we would then just use OWL-Full?
- would the speed-ups then be great enough to consider linking everyday app data to large scale-upper ontologies?
- is a contradiction in a ‘quantum reasoner’ (i.e. a reasoner that uses a quantum search engine) something that can never occur because it just cancels out and never appears in the returned triples? Would any returned conclusion be necessarily true (relative to the axioms of the ontology?)

Any thoughts?

** UPDATE**DWave are now working with Google to help them improve some of their machine learning algorithms. I wonder whether there will be other research into the practicality of using DWave quantum computing systems in conjunction with inference engines? This could, of course, open up whole new vistas of services that could be provided by Google (or their competitors). Either way, it gives me a warm feeling to know that every time I do a search, I’m getting the results from a quantum computer (no matter how indirectly). Nice.

About the NP completeness see http://scottaaronson.com/blog/?p=198

Hi Simon,

I’ve read Scott’s comments on the hyperbole generated by DWave. But (and this is where Geordie Rose has a point) that doesn’t detract from the basic business proposition.

I’m not buying into the notion that NP-Complete problems are now tractable – I’m just pointing out that for truly massive triple stores, a quadratic speed up (Glover’s alg provides this) over the best search algorithm is going to make the QC platform a compelling proposition for semantic web systems, if there is no efficient and easy way to properly index triples.

Yeah, maybe, and that would really be a nice thing to have. But I’m scared of the day when we will have pratical quantum computers ’cause we can say good-bye to all our current encryption solutions then. :-)

Although it’s always nice to think about what quantum computers can be capable of, if quantum computers are supposed to be the answer to RDF reasoning scalability, then RDF still has a long way to go on one of its major promises :). I’d say it is more important to find ways that efficiently work with the architectures we have today, ones that can be effectively parallellised. Because I think that is what current consumer technology is heading to for now, quantum computing is still relatively far away.

By the way, I agree with Simon’s fears about encryption above, although I don’t think we can avoid it :(. Let’s just hope that we will get affordable desktop-sized quantum encryption modules very soon after effective quantum computers become available to governments and organisations.