Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1107.5881 · Theory of Computing

Quantum Private Information Retrieval with Sublinear Communication Complexity

Francois Le Gall

Published Jan 1, 2012• 24 citations
arXivHTMLPDF

Abstract

This note presents a quantum protocol for private information retrieval, in the case of a single (honest) server 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.

DOI
10.4086/toc.2012.v008a016

Related papers

On Quantum Advantage in Information Theoretic Single-Server PIR

Dorit Aharonov, Zvika Brakerski, Kai-Min Chung +3 more

In (single-server) Private Information Retrieval (PIR), a server holds a large database $DB$ of size $n$, and a client holds an index $i \in [n]$ and wishes to retrieve $DB[i]$ without revealing $i$ to the server. It is well known that information theoretic privacy even against an `honest but curious' server requires $Ω(n)$ communication complexity. This is true even if quantum communication is allowed and is due to the ability of such an adversarial server to execute the protocol on a superposition of databases instead of on a specific database (`input purification attack'). Nevertheless, there have been some proposals of protocols that achieve sub-linear communication and appear to provide some notion of privacy. Most notably, a protocol due to Le Gall (ToC 2012) with communication complexity $O(\sqrt{n})$, and a protocol by Kerenidis et al. (QIC 2016) with communication complexity $O(\log(n))$, and $O(n)$ shared entanglement. We show that, in a sense, input purification is the only potent adversarial strategy, and protocols such as the two protocols above are secure in a restricted variant of the quantum honest but curious (a.k.a specious) model. More explicitly, we propose a restricted privacy notion called \emph{anchored privacy}, where the adversary is forced to execute on a classical database (i.e. the execution is anchored to a classical database). We show that for measurement-free protocols, anchored security against honest adversarial servers implies anchored privacy even against specious adversaries. Finally, we prove that even with (unlimited) pre-shared entanglement it is impossible to achieve security in the standard specious model with sub-linear communication, thus further substantiating the necessity of our relaxation. This lower bound may be of independent interest (in particular recalling that PIR is a special case of Fully Homomorphic Encryption).

arXiv:1902.09768•Feb 26, 2019•0 citations

Quantum Private Queries

Vittorio Giovannetti, Seth Lloyd, Lorenzo Maccone

We propose a cheat sensitive quantum protocol to perform a private search on a classical database which is efficient in terms of communication complexity. It allows a user to retrieve an item from the database provider without revealing which item he or she retrieved: if the provider tries to obtain information on the query, the person querying the database can find it out. The protocol ensures also perfect data privacy of the database: the information that the user can retrieve in a single query is bounded and does not depend on the size of the database. With respect to the known (quantum and classical) strategies for private information retrieval, our protocol displays an exponential reduction in communication complexity and in running-time computational complexity.

arXiv:0708.2992•Physical Review Letters•Jun 10, 2008•217 citations

Information-Theoretic Aspects of Quantum Private Information Retrieval

Seunghoan Song

When a user retrieves information from databases, it is often required to protect the privacy of the user.Quantum private information retrieval (QPIR) is a protocol in which a user retrieves one of 𝑓𝑓 messages from non-communicating 𝑛𝑛 servers by downloading quantum systems without revealing the identity of the retrieved message to any individual server.Symmetric QPIR is a QPIR with server secrecy in which the user obtains no information of non-targeted messages.This thesis investigates the fundamental communication limit of the symmetric and nonsymmetric QPIR and constructs the optimal QPIR protocols achieving the communication limit.The communication cost of a QPIR protocol is evaluated by the QPIR rate defined as

•Dec 28, 2020•0 citations

Quantum Private Information Retrieval

Ämin Baumeler

This thesis discusses Quantum Private Information Retrieval in the single-server scenario with information-theoretic privacy.We show that for such a protocol to be secure against the weakest reasonable adversary, the protocol requires a linear amount of communication.Hence, the trivial protocol for Quantum Private Information Retrieval is optimal.Furthermore, we discuss the mentioned weakest reasonable adversaries, called specious.As a motivation to this research, we analyze and break a recent protocol for Quantum Private Information Retrieval.i Note that due to the effect of phase-kickback, the above unitary may leak information about the index i to the register DB.However, this happens only in the case of non-classical inputs on the registers A or IDX.Because we assume that the client is honest, and hence does not perform queries in superpositions, we nevertheless use this unitary as the ideal functionality.

•Jan 1, 2012•2 citations

A survey on communication complexity in quantum private information retrieval: Efficiency challenges and advances

Laxmi Kumari, Tarun Kumar Mahato

Quantum Private Information Retrieval (QPIR) is a new and growing area that uses quantum computing to improve privacy and efficiency in database searches. Traditional Private Information Retrieval (PIR) methods often require a large amount of communication between the user and the server, making them slow and costly. QPIR aims to solve this problem by using quantum techniques like superposition and entanglement to reduce communication while keeping the user’s query private. In this paper, we review different QPIR methods and analyze how they handle communication complexity. We compare multi-server and single-server models, discussing their strengths and weaknesses. We also explore the practical challenges of QPIR, such as the need for quantum resources, errors in quantum systems, and security against quantum attackers. Additionally, we highlight important research gaps, including how to make single-server QPIR more efficient, balancing security with speed, and understanding how future quantum computers might impact QPIR security. By addressing these challenges, this survey aims to support further research and help develop practical, efficient, and secure QPIR systems for real-world use.

International journal of applied research•Jan 1, 2025•0 citations

One-Way Quantum Symmetric Private Information Retrieval Protocol From A Single Database Server Using NISQ Devices

Xiang Zou, H. F. Chau

Symmetric private information retrieval (SPIR) lets an inquirer obtain one specific bit only, without leaking any information about its index to the database owner. With a single server, this is impossible for parties with unrestricted quantum power. We show that it becomes possible, with information-theoretic security, when the server and the user hold only noisy intermediate-scale quantum (NISQ) devices without long-term quantum memory and measure each qubit on arrival, while the eavesdropper remains all-powerful; this is a stricter form of the memory restriction of the bounded- and noisy-quantum-storage models. The server sends BB84 states one way; the user discriminates them unambiguously and so knows a random subset of the bits. After a joint random permutation into blocks, the user announces the conclusive locations of one privately chosen block, and the server hashes and takes a random parity of these locations in every block; the permutation makes it exponentially unlikely that one set of locations fits two blocks. We prove secrecy against the eavesdropper, database privacy through an explicit size rule for the announced set, and user privacy against a server who prepares the prescribed BB84 states and announces truthfully, exactly for single photons and up to a small multi-photon term over a tolerated noise channel. The only addition to BB84 equipment is a passive linear-optical measurement with one ancillary mode. For a $10^{4}$-bit database and database privacy $10^{-6}$, blocks of about a thousand qubits suffice over a tolerated noise channel for a user who applies the prescribed measurement; certifying an arbitrary memoryless user and committing to the permutation need larger auxiliary transmissions, which we quantify with finite keys. Database privacy extends to decoy-state weak coherent pulses, and simulations show that the bound is nearly tight.

quant-pharXiv:2610.02093•Oct 2, 2026•0 citations
This note presents a quantum protocol for private information retrieval, in the case of a single (honest) server and with information-theoretical privacy, that has O(n)O(\sqrt{n})O(n​)-qubit communication complexity, where nnn denotes the size of the database. In comparison, it is known that any classical protocol must use Ω(n)\Omega(n)Ω(n) bits of communication in this setting.
In (single-server) Private Information Retrieval (PIR), a server holds a large database DBDBDB of size nnn, and a client holds an index i∈[n]i \in [n]i∈[n] and wishes to retrieve DB[i]DB[i]DB[i] without revealing iii to the server. It is well known that information theoretic privacy even against an `honest but curious' server requires Ω(n)Ω(n)Ω(n) communication complexity. This is true even if quantum communication is allowed and is due to the ability of such an adversarial server to execute the protocol on a superposition of databases instead of on a specific database (`input purification attack'). Nevertheless, there have been some proposals of protocols that achieve sub-linear communication and appear to provide some notion of privacy. Most notably, a protocol due to Le Gall (ToC 2012) with communication complexity O(n)O(\sqrt{n})O(n​), and a protocol by Kerenidis et al. (QIC 2016) with communication complexity O(log⁡(n))O(\log(n))O(log(n)), and O(n)O(n)O(n) shared entanglement. We show that, in a sense, input purification is the only potent adversarial strategy, and protocols such as the two protocols above are secure in a restricted variant of the quantum honest but curious (a.k.a specious) model. More explicitly, we propose a restricted privacy notion called \emph{anchored privacy}, where the adversary is forced to execute on a classical database (i.e. the execution is anchored to a classical database). We show that for measurement-free protocols, anchored security against honest adversarial servers implies anchored privacy even against specious adversaries. Finally, we prove that even with (unlimited) pre-shared entanglement it is impossible to achieve security in the standard specious model with sub-linear communication, thus further substantiating the necessity of our relaxation. This lower bound may be of independent interest (in particular recalling that PIR is a special case of Fully Homomorphic Encryption).
We propose a cheat sensitive quantum protocol to perform a private search on a classical database which is efficient in terms of communication complexity. It allows a user to retrieve an item from the database provider without revealing which item he or she retrieved: if the provider tries to obtain information on the query, the person querying the database can find it out. The protocol ensures also perfect data privacy of the database: the information that the user can retrieve in a single query is bounded and does not depend on the size of the database. With respect to the known (quantum and classical) strategies for private information retrieval, our protocol displays an exponential reduction in communication complexity and in running-time computational complexity.
When a user retrieves information from databases, it is often required to protect the privacy of the user.Quantum private information retrieval (QPIR) is a protocol in which a user retrieves one of 𝑓𝑓 messages from non-communicating 𝑛𝑛 servers by downloading quantum systems without revealing the identity of the retrieved message to any individual server.Symmetric QPIR is a QPIR with server secrecy in which the user obtains no information of non-targeted messages.This thesis investigates the fundamental communication limit of the symmetric and nonsymmetric QPIR and constructs the optimal QPIR protocols achieving the communication limit.The communication cost of a QPIR protocol is evaluated by the QPIR rate defined as
This thesis discusses Quantum Private Information Retrieval in the single-server scenario with information-theoretic privacy.We show that for such a protocol to be secure against the weakest reasonable adversary, the protocol requires a linear amount of communication.Hence, the trivial protocol for Quantum Private Information Retrieval is optimal.Furthermore, we discuss the mentioned weakest reasonable adversaries, called specious.As a motivation to this research, we analyze and break a recent protocol for Quantum Private Information Retrieval.i Note that due to the effect of phase-kickback, the above unitary may leak information about the index i to the register DB.However, this happens only in the case of non-classical inputs on the registers A or IDX.Because we assume that the client is honest, and hence does not perform queries in superpositions, we nevertheless use this unitary as the ideal functionality.
Quantum Private Information Retrieval (QPIR) is a new and growing area that uses quantum computing to improve privacy and efficiency in database searches. Traditional Private Information Retrieval (PIR) methods often require a large amount of communication between the user and the server, making them slow and costly. QPIR aims to solve this problem by using quantum techniques like superposition and entanglement to reduce communication while keeping the user’s query private. In this paper, we review different QPIR methods and analyze how they handle communication complexity. We compare multi-server and single-server models, discussing their strengths and weaknesses. We also explore the practical challenges of QPIR, such as the need for quantum resources, errors in quantum systems, and security against quantum attackers. Additionally, we highlight important research gaps, including how to make single-server QPIR more efficient, balancing security with speed, and understanding how future quantum computers might impact QPIR security. By addressing these challenges, this survey aims to support further research and help develop practical, efficient, and secure QPIR systems for real-world use.
Symmetric private information retrieval (SPIR) lets an inquirer obtain one specific bit only, without leaking any information about its index to the database owner. With a single server, this is impossible for parties with unrestricted quantum power. We show that it becomes possible, with information-theoretic security, when the server and the user hold only noisy intermediate-scale quantum (NISQ) devices without long-term quantum memory and measure each qubit on arrival, while the eavesdropper remains all-powerful; this is a stricter form of the memory restriction of the bounded- and noisy-quantum-storage models. The server sends BB84 states one way; the user discriminates them unambiguously and so knows a random subset of the bits. After a joint random permutation into blocks, the user announces the conclusive locations of one privately chosen block, and the server hashes and takes a random parity of these locations in every block; the permutation makes it exponentially unlikely that one set of locations fits two blocks. We prove secrecy against the eavesdropper, database privacy through an explicit size rule for the announced set, and user privacy against a server who prepares the prescribed BB84 states and announces truthfully, exactly for single photons and up to a small multi-photon term over a tolerated noise channel. The only addition to BB84 equipment is a passive linear-optical measurement with one ancillary mode. For a 10410^{4}104-bit database and database privacy 10−610^{-6}10−6, blocks of about a thousand qubits suffice over a tolerated noise channel for a user who applies the prescribed measurement; certifying an arbitrary memoryless user and committing to the permutation need larger auxiliary transmissions, which we quantify with finite keys. Database privacy extends to decoy-state weak coherent pulses, and simulations show that the bound is nearly tight.