arXiv:2611.03558
Quantum Private Information Retrieval on Forests
Mohamed Nomeir, Sennur Ulukus
Abstract
We consider the problem of graph private information retrieval (PIR) in the quantum setting. We focus on a specific type of graphs, namely the forest graphs. A forest graph is a union of disjoint trees. We consider the quantum setting where all the servers share an entangled state. Each server is allowed to send only one qudit per retrieval round. We design a scheme for the forest graphs that achieves the rate of $\frac{3}{N}$. The scheme uses a GHZ state as the initial entangled state between the servers prior to the scheme initiation. We compare our scheme with the only work done in the literature that considered the quantum setting of graph PIR. We show that our scheme is more efficient in this setting. We derive the quantum capacity for the case of $G=3K_2$, which is equal to $4/6$. $G=3K_2$ is a special case of the forest graph. We design a scheme that is specialized for this graph, achieving a rate equal to $4/6$ and provide the corresponding matching upper bound, establishing it as the capacity.
AI Summary
The paper studies quantum private information retrieval (QPIR) with graph-based storage: vertices are noncolluding servers, and each independent classical message is replicated at the two endpoints of an edge. Queries are classical, servers share entanglement before retrieval, and each server sends one qudit to the user. The objective is zero-error recovery while hiding the requested message index from every individual server. For forests consisting of at least two nontrivial tree components, with no isolated vertices, it constructs a one-round scheme achieving $R_Q=3/N$ for every prime qudit dimension $p>N$. Each file contains three field symbols. Local Pauli encodings of a shared $N$-party GHZ state allow the user to measure one sum and $N-1$ differences of server-generated quantities. Cancellation across undesired edges, cuts formed by removing the desired edge, and an additional tree component recover the three desired symbols. Random invertible transformations of each file ensure query privacy. The rate is $3/2$ times the cited general graph-based quantum construction’s $2/N$, and also exceeds classical capacity by that factor for matching graphs. For the six-server matching $G=3K_2$, a separate construction over $\mathbb F_7$, using the $N$-sum-box framework and linear decoding, retrieves four symbols from six qudits. A non-signaling cut-set converse proves capacity $C_Q=4/6=2/3$. The general forest result is an achievable rate rather than a capacity characterization; its stated scope excludes connected trees and isolated vertices.
Central claim may not hold: The abstract's forest-wide 3/N claim is broader than the proved construction, which requires at least two nontrivial tree components; the unrestricted claim fails already for K₂ by the Holevo dimension bound. The 3K₂ construction prints an incorrect block-matrix inverse, producing a transfer-matrix sign inconsistent with its outputs, although replacing Γ with −Γ in G repairs the construction.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.