Quantum private information retrieval with sublinear communication complexity

DOI10.4086/TOC.2012.V008A016MaRDI QIDQ2913816zbMATH OpenOpenAlexFDO

Authors François Le Gall

Publication date 27 September 2012

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1107.5881

zbMATH Keywords

private information retrievalquantum communication complexity

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Quantum computation (81P68)

Abstract: This note presents a quantum protocol for private information retrieval, in the single-server case and with information-theoretical privacy, that has O(sqrt{n})-qubit communication complexity, where n denotes the size of the database. In comparison, it is known that any classical protocol must use Omega(n) bits of communication in this setting.

Recommendations

• Quantum private information retrieval has linear communication complexity
• Quantum Private Queries
• On quantum advantage in information theoretic single-server PIR
• Quantum symmetrically-private information retrieval
• Security improvements of several basic quantum private query protocols with \(O(\log N)\) communication complexity

Cited in

(6)

• Quantum private information retrieval has linear communication complexity
• On quantum advantage in information theoretic single-server PIR
• Quantum symmetrically-private information retrieval
• A property of quantum relative entropy with an application to privacy in quantum communication
• Authenticated sublinear quantum private information retrieval
• Quantum private information retrieval with lattice-based access authentication

This page was built for publication: Quantum private information retrieval with sublinear communication complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2913816)