Introduction

Giovannetti, Lloyd, and Maccone (GLM) are "back at it again" with this recent contribution. Seth Lloyd has embarked on a "world tour" to describe this primitive for quantum communication to a wide audience of quantum information theorists. He has lectured on this topic at the University of Tokyo's "18th Quantum Information Technology Symposium," the "Quantum Information Processing Seminar" at MIT, and the "Quantum Information and Condensed Matter Physics Seminar" at USC in Los Angeles to name a few places. I was privileged to be at USC to attend the seminar there and will relate some of the discussion in this review.

This "quantum private query" primitive for quantum communication is simple in form and might eventually join quantum key distribution (http://en.wikipedia.org/wiki/Quantum_cryptography), quantum teleportation (http://en.wikipedia.org/wiki/Quantum_teleportation), or quantum superdense coding (http://en.wikipedia.org/wiki/Superdense_coding) as one of the fundamental primitives for quantum communication. Of the above fundamental primitives, the quantum private query resembles quantum key distribution most closely because it exploits the no-cloning theorem (http://en.wikipedia.org/wiki/No_cloning_theorem) to ensure security of the sender's query.

Seth provides a great description of a "quantum private query" on the MIT Quantum Information Processing Seminar web site http://qis.mit.edu/seminars.php:

Seth provided an interesting backdrop in his seminar by relating how the idea came to be. He mentioned that he was at a dinner with the founders of Google, Larry Page and Sergey Brin, and the Google founders wanted to find out what "quantum" could do for them. They discussed many ideas but the discussion ended by the group determining that they would need to figure out whatever something called "quantum internet search" would be and that Seth and collaborators would determine a protocol to implement it. Three years later, Giovannetti, Lloyd, and Maccone formulated the quantum private query. Seth reported their findings to Page and Brin. The Google founders thought it was neat, but told Seth that they were not sure how useful it would be for them because they actually want to know everything about what a user is searching for. But this protocol will actually be useful in a future quantum Internet to protect individual rights to privacy.

The GLM Protocol for a Quantum Private Query

I now describe the GLM protocol for quantum private query. Larry has a large database of distinct entries. The zeroth entry of the database is a fixed value that everyone already knows. Alice would like to find out the entry of Larry's database. So she prepares two quantum registers. One of the registers is in the state



and the other is in a superposed state



She picks one of the registers at random, records which one she picked, and sends it to Larry. Larry performs the following transformation on the register:



The above transformation appends a quantum register to Alice's and coherently copies the database entry corresponding to index into the appended register. Thus the resulting state is



if Alice sent or it is



if Alice sent the superposed state. Larry then sends Alice's original register and the appended one back to Alice. Alice sends her other register and Larry performs the same operation and sends back to Alice. Alice recalls which register is not superposed and performs a measurement on it to determine the answer to her query . Alice then can construct a measurement based on this result to determine if Larry cheated and tried to learn about her query. She has a non-zero probability of detecting a mischievous Larry.

The above protocol is a delightful addition to the quantum information toolbox because of its simplicity and elegant use of fundamental components of quantum theory. It exploits the no-cloning theorem to ensure the privacy of Alice's queries because the two states Alice prepares are not orthogonal. If Larry tries to learn about them, then Alice can detect this cheating---similar to the technique used in quantum key distribution. The other element of the protocol that protects the privacy of Alice's query is that Alice sends her queries one at a time. If she did not, then Larry could perform joint measurements across multiple queries to learn about them. The protocol also guarantees that Alice learns only about two of the entries in Larry's database: the zeroth entry known to everyone and the entry that she actually wanted to learn about.

Future Work

In the discussion after Seth's talk at USC, he mentioned that there is further work that needs to be done. One suggestion was that this protocol could be part of a future quantum market. This quantum market would guarantee the credibility of sellers of information by a rating that shows how honest they are.

This suggestion immediately provoked the question of a malicious middle-woman attacker Eve who wants to ruin the reputation of Larry or who would modify Alice's queries to learn about Larry's database. How can we protect against such an attacker when the above protocol assumes that noiseless quantum communication is available? Seth suggested that we could integrate the theory of quantum error correction with this protocol to protect against attacks that Eve may employ. This suggestion should be correct but it would be interesting to see how particular quantum codes may affect Alice's probability of detecting false positives for Larry cheating or how a quantum code can protect the entries of Larry's database.

There is also a trade-off between performance and security. In order to guarantee privacy, Alice must send her queries one at a time. This requirement could potentially harm performance in a multi-user scenario where Larry is processing multiple queries. Performance would be better if Larry processed queries in parallel, but this parallelizing might allow Larry to learn something about the different queries because "the subspaces spanned by the joint states of (different users') queries are orthogonal for different queries" as stated in a slightly different context of the original paper. This question could be a future line of investigation.

Other discussions of the "Quantum Private Queries" paper are available at the following links:

http://www.physorg.com/news129289258.html
http://thequantumpoet.blogspot.com/2008/02/seth-lloyd-usc.html