Quantum Private Information Retrieval has Linear Communication Complexity

In private information retrieval (PIR), a client queries an $$n$$ n -bit database in order to retrieve an entry of her choice, while maintaining privacy of her query value. Chor et al. [J ACM 45(6):965-981, 1998] showed that, in the information-theoretical setting, a linear amount of communication is required for classical PIR protocols (thus the trivial protocol is optimal). This linear lower bound was shown by Nayak [FOCS 1999, pp. 369-376, 1999] to hold also in the quantum setting. Here, we extend Nayak's result by considering approximate privacy, and requiring security only against specious adversaries, which are, in analogy to classical honest-but-curious adversaries, the weakest reasonable quantum adversaries. We show that, even in this weakened scenario, quantum private information retrieval (QPIR) requires $$n$$ n qubits of communication. From this follows that Le Gall's recent QPIR protocol with sublinear communication complexity [Theory Comput. 8(1):369-374, 2012] is not information-theoretically private, against the weakest reasonable cryptographic adversary.