Mark Gritter (markgritter) wrote,
Mark Gritter

Quantum Search Engines

"Privacy and the Quantum Internet" (in the October 2009 Scientific American) seems like a very cute and completely useless idea. The authors' proposal is to implement an eavesdropping-free "quantum private search" which makes use of quantum entanglement to allow the sender to verify that her query has not been observed. (See, for example, their security analysis.) In fact, a group at the University of Rome has demonstrated such a system built on "quantum RAM" which performs two index lookups simultaneously, given two queries in superposition.

This works great as long as you are doing retrieval of an entry in a fixed database. Forget about asking queries that aren't precomputed, though. Admittedly, most two-word queries could be encoded in the 30-bit table they suggest.

A larger problem, however, is that their security analysis depends upon Bob replying to Alice's query. A future quantum internet which does not drop any packets would be radical indeed! It seems completely infeasible to imagine a communication system with no error or noise, and thus the possibility of lost or damaged queries must be part of the protocol. But if Alice is willing to resend a query without a response from Bob, then Bob can take all the measurements he wants of the initial query, and simply fail to respond.

In fact Bob (or Larry or Sergey) does not have to collect queries at close to the rate of natural error. Bob can collect several minutes worth of queries, measure them, and simply claim to have experienced a power failure or other data center fault. Admittedly Bob will have worse end-user performance than competitors who do not cheat...

A review of their paper, mentioning an additional restriction: Alice must send her queries one at a time. The requirement of noiseless communication is brought up incidentally as a restriction, but I think it's closer to a fatal flaw.
Tags: computers, geek, networking, physics, quantum
  • Post a new comment


    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.