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• 25 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•218 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

Secure quantum private information retrieval using phase-encoded queries

Łukasz Olejnik

We propose a quantum solution to the classical private information retrieval (PIR) problem, which allows one to query a database in a private manner. The protocol offers privacy thresholds and allows the user to obtain information from a database in a way that offers the potential adversary, in this model the database owner, no possibility of deterministically establishing the query contents. This protocol may also be viewed as a solution to the symmetrically private information retrieval problem in that it can offer database security (inability for a querying user to steal its contents). Compared to classical solutions, the protocol offers substantial improvement in terms of communication complexity. In comparison with the recent quantum private queries [Phys. Rev. Lett. 100, 230502 (2008)] protocol, it is more efficient in terms of communication complexity and the number of rounds, while offering a clear privacy parameter. We discuss the security of the protocol and analyze its strengths and conclude that using this technique makes it challenging to obtain the unconditional (in the information-theoretic sense) privacy degree; nevertheless, in addition to being simple, the protocol still offers a privacy level. The oracle used in the protocol is inspired both by the classical computational PIR solutions as well as the Deutsch-Jozsa oracle.

Physical Review A•Aug 8, 2011•125 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.
We propose a quantum solution to the classical private information retrieval (PIR) problem, which allows one to query a database in a private manner. The protocol offers privacy thresholds and allows the user to obtain information from a database in a way that offers the potential adversary, in this model the database owner, no possibility of deterministically establishing the query contents. This protocol may also be viewed as a solution to the symmetrically private information retrieval problem in that it can offer database security (inability for a querying user to steal its contents). Compared to classical solutions, the protocol offers substantial improvement in terms of communication complexity. In comparison with the recent quantum private queries [Phys. Rev. Lett. 100, 230502 (2008)] protocol, it is more efficient in terms of communication complexity and the number of rounds, while offering a clear privacy parameter. We discuss the security of the protocol and analyze its strengths and conclude that using this technique makes it challenging to obtain the unconditional (in the information-theoretic sense) privacy degree; nevertheless, in addition to being simple, the protocol still offers a privacy level. The oracle used in the protocol is inspired both by the classical computational PIR solutions as well as the Deutsch-Jozsa oracle.