Friday, February 22, 2008

Seth Lloyd @ USC

I went to an interesting talk on campus today. Seth Lloyd who works in quantum information theory at MIT, spoke about his new paper, entitled, "Quantum Private Queries". Here's the problem description.

Imagine a communication scenario where you are given two parties, namely, Alice and Bob, who are spatially separated, let's say, and share a quantum communication channel. The latter just means that they can send quantum information between each other. Bob has access to a huge database. Alice would like to query Bob's database and retrieve an answer without Bob knowing the answer as well. If he cheats, she will come to know about it. Classically, a naive approach would be for Alice to send for example a million queries to Bob and Bob sends back a million answers from his database. One Alice gets the million answers she can look up the correct one. But you can see how this is inefficient. Quantum mechanically one can do the same in a very efficient manner. They get drastic reductions in communication and computational complexity. Later in the talk, he also touched upon how one can go about building a quantum random access memory (qRAM) device.

If you are interested in reading about the "Quantum Private Query" paper, you can find it on the arxiv here.

His qRAM paper is here.

Seth has also written a book, entitled, " Programming the Universe: A Quantum Computer Scientist Takes on the Cosmos." I had my copy autographed by him, heh heh. He was relating all these crazy stories where he was sitting in a hot tub with Sergey and Larry (Google founders) and talking about the quantum Internet.


Todd said...

Thanks for the description of the talk! Wish I could have been there...

The Quantum Poet said...

It would have been nice hear an insightful comment or two from you. Mark asked whether entanglement could help in further communication and computational complexity reduction. Mark and I thought about it a later after the talk. Also I am not sure how and where quantum private queries sit in with Igor's "Resource Framework" setting.