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.