Capacity of Quantum Private Information Retrieval with Collusion of All But One of Servers
Seunghoan Song, Masahito Hayashi · 2019
Quantum private information retrieval (QPIR) is the problem to retrieve one of f classical files by downloading quantum systems from non-communicating n servers each of which contains the copy of f files, while the identity of the retrieved file is unknown to each server. As an extension, we consider the (n-1)-private QPIR that the identity of the retrieved file is secret even if any n-1 servers collude, and derive the QPIR capacity for this problem which is defined as the maximum rate of the retrieved file size over the download size. For an even number n of servers, we show that the capacity of the (n-1)-private QPIR is 2/n, when we assume that there are preexisting entanglements among the servers and require that no information of the nonretrieved files is downloaded. We construct an (n - 1)-private QPIR protocol of rate Γn/21-1and prove that the capacity is upper bounded by 2/n. The (n - 1)-private QPIR capacity is strictly greater than the classical counterpart. The full version of this paper is accessible at: https://arxiv.org/pdf/1903.12556.