Skip to content
DraconiticResearch
Search Sources API
178,970 studies31 sourcesUpdated 57 min ago
PreprintarXiv licencearXiv

Quantum Private Information Retrieval on Forests

  • Mohamed Nomeir
  • Sennur Ulukus
Open at sourcePDFDOICite

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 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=3K2, which is equal to 4/6. G=3K2 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.

Related

  1. The Capacity of Private Information Retrieval from Coded Storage Systems with Colluding, Robust and Byzantine Servers
    Rui Sun, Yiwei Zhang
    arXivPreprintarXiv licenceFull textGeneral mathematicsarXiv
  2. Weak Private Information Retrieval for Graph-based Storage under ε-privacy
    Jayesh Seshadri, Prasad Krishnan
    arXivPreprintarXiv licenceFull textGeneral mathematicsarXiv
  3. Private Information Retrieval With Arbitrary Privacy Requirements: Introduction and Capacity Results
    Mohamed Nomeir, Shreya Meel, Sennur Ulukus
    arXivPreprintarXiv licenceFull textGeneral mathematicsarXiv
  4. Local Private Information Retrieval for Graph-Based Replicated Systems
    Shreya Meel, Mohamed Nomeir, Sennur Ulukus
    arXivPreprintarXiv licenceFull textGeneral mathematicsarXiv
  5. Bayesian Equilibria of Heterogeneous Non-Atomic Routing Games With Private Information
    Alexia Ambrogio, Leonardo Cianfanelli, Giacomo Como +1
    IEEE Control Systems LettersPeer-reviewedPublisher termsFull textGeneral mathematicsHAL

Cite

BibTeXRIS
BibTeX
@misc{nomeir2026quantum,
  title = {{Quantum Private Information Retrieval on Forests}},
  author = {Mohamed Nomeir and Sennur Ulukus},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.03558},
  eprint = {2611.03558},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.03558},
}
RIS
TY  - UNPB
TI  - Quantum Private Information Retrieval on Forests
AU  - Mohamed Nomeir
AU  - Sennur Ulukus
PY  - 2026
DA  - 2026/11/02
PB  - arXiv
DO  - 10.48550/arxiv.2611.03558
UR  - https://arxiv.org/abs/2611.03558
AB  - 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 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.
ER  -