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:2101.09041 · IEEE International Symposium on Information Theory (ISIT)

Quantum Private Information Retrieval for Quantum Messages

Seunghoan Song, Masahito Hayashi

Published Jul 12, 2021• 11 citations
arXivHTMLPDF

Abstract

Quantum private information retrieval (QPIR) for quantum messages is the protocol in which a user retrieves one of the multiple quantum states from one or multiple servers without revealing which state is retrieved. We consider QPIR in two different settings: the blind setting, in which the servers contain one copy of the message states, and the visible setting, in which the servers contain the description of the message states. One trivial solution in both settings is downloading all states from the servers and the main goal of this paper is to find more efficient QPIR protocols. First, we prove that the trivial solution is optimal for one-server QPIR in the blind setting. In one-round protocols, the same optimality holds even in the visible setting. On the other hand, when the user and the server share entanglement, we prove that there exists an efficient one-server QPIR protocol in the blind setting. Furthermore, in the visible setting, we prove that it is possible to construct symmetric QPIR protocols in which the user obtains no information of the non-targeted messages. We construct two-server symmetric QPIR protocols for pure states. Note that symmetric classical PIR is impossible without shared randomness unknown to the user.

DOI
10.1109/isit45174.2021.9517794

Related papers

Prior entanglement exponentially improves one-server quantum private information retrieval for quantum messages

Seunghoan Song, François Le Gall, Masahito Hayashi

Quantum private information retrieval (QPIR) for quantum messages is a quantum communication task, in which a user retrieves one of the multiple quantum states from the server without revealing which state is retrieved. In the one-server setting, we find an exponential gap in the communication complexities between the presence and absence of prior entanglement in this problem with the one-server setting. To achieve this aim, as the first step, we prove that the trivial solution of downloading all messages is optimal under QPIR for quantum messages, which is a similar result to that of classical PIR but different from QPIR for classical messages. As the second step, we propose an efficient one-server one-round QPIR protocol with prior entanglement by constructing a reduction from a QPIR protocol for classical messages to a QPIR protocol for quantum messages in the presence of prior entanglement.

arXiv:2304.05125•EPJ Quantum Technology•Sep 6, 2024•2 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

Capacity of Quantum Private Information Retrieval with Colluding Servers

Seunghoan Song, Masahito Hayashi

Quantum private information retrieval (QPIR) is a protocol in which a user retrieves one of multiple files from $\mathsf{n}$ non-communicating servers by downloading quantum systems without revealing which file is retrieved. As variants of QPIR with stronger security requirements, symmetric QPIR is a protocol in which no other files than the target file are leaked to the user, and $\mathsf{t}$-private QPIR is a protocol in which the identity of the target file is kept secret even if at most $\mathsf{t}$ servers may collude to reveal the identity. The QPIR capacity is the maximum ratio of the file size to the size of downloaded quantum systems, and we prove that the symmetric $\mathsf{t}$-private QPIR capacity is $\min\{1,2(\mathsf{n}-\mathsf{t})/\mathsf{n}\}$ for any $1\leq \mathsf{t}< \mathsf{n}$. We construct a capacity-achieving QPIR protocol by the stabilizer formalism and prove the optimality of our protocol. The proposed capacity is greater than the classical counterpart.

arXiv:2001.04436•Jan 13, 2020•0 citations

Capacity of Quantum Private Information Retrieval With Colluding Servers

Seunghoan Song, Masahito Hayashi

Quantum private information retrieval (QPIR) is a protocol in which a user retrieves one of multiple files from n non-communicating servers by downloading quantum systems without revealing which file is retrieved. As variants of QPIR with stronger security requirements, symmetric QPIR is a protocol in which no other files than the target file are leaked to the user, and t-private QPIR is a protocol in which the identity of the target file is kept secret even if at most t servers may collude to reveal the identity. The QPIR capacity is the maximum ratio of the file size to the size of downloaded quantum systems, and we prove that the symmetric t-private QPIR capacity is min{1,2( n- t)/ n} for any 1 ≤ t <; n. We construct a capacity-achieving QPIR protocol by the stabilizer formalism and prove the optimality of our protocol. The proposed capacity is greater than the classical counterpart.

IEEE Transactions on Information Theory•May 4, 2021•28 citations

Capacity of Quantum Private Information Retrieval With Multiple Servers

Seunghoan Song, Masahito Hayashi

We study the capacity of quantum private information retrieval (QPIR) with multiple servers. In the QPIR problem with multiple servers, a user retrieves a classical file by downloading quantum systems from multiple servers each of which contains the copy of a classical file set while the identity of the downloaded file is not leaked to each server. The QPIR capacity is defined as the maximum rate of the file size over the whole dimension of the downloaded quantum systems. When the servers are assumed to share prior entanglement, we prove that the QPIR capacity with multiple servers is 1 regardless of the number of servers and files. We construct a rate-one protocol only with two servers. This capacity-achieving protocol outperforms its classical counterpart in the sense of the capacity, server secrecy, and upload cost. The strong converse bound is derived concisely without using any secrecy condition. We also prove that the capacity of multi-round QPIR is 1.

arXiv:1903.10209•IEEE Transactions on Information Theory•Sep 7, 2020•35 citations

Capacity of Quantum Private Information Retrieval with Colluding Servers

Seunghoan Song, Masahito Hayashi

Quantum private information retrieval (QPIR) is a protocol that a user retrieves one of f files from non-communicating n servers by downloading quantum systems without revealing the identity of the target file. As variants of the QPIR with stronger security requirements, the symmetric QPIR is that the files except for the target file are not leaked to the user, and the t-private QPIR is that the identity of the target file is kept secret even if at most t servers may collude to reveal the identity. The QPIR capacity is the maximum ratio of the one file size to the size of downloaded quantum systems, and we prove that the symmetric t-private QPIR capacity is min {1, 2(n - t)/n} for any 1 ≤ t <; n. We construct a capacity-achieving QPIR protocol by the stabilizer formalism and prove the optimality of our protocol. The proposed capacity is greater than the classical counterpart.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2020•7 citations
Quantum private information retrieval (QPIR) for quantum messages is the protocol in which a user retrieves one of the multiple quantum states from one or multiple servers without revealing which state is retrieved. We consider QPIR in two different settings: the blind setting, in which the servers contain one copy of the message states, and the visible setting, in which the servers contain the description of the message states. One trivial solution in both settings is downloading all states from the servers and the main goal of this paper is to find more efficient QPIR protocols. First, we prove that the trivial solution is optimal for one-server QPIR in the blind setting. In one-round protocols, the same optimality holds even in the visible setting. On the other hand, when the user and the server share entanglement, we prove that there exists an efficient one-server QPIR protocol in the blind setting. Furthermore, in the visible setting, we prove that it is possible to construct symmetric QPIR protocols in which the user obtains no information of the non-targeted messages. We construct two-server symmetric QPIR protocols for pure states. Note that symmetric classical PIR is impossible without shared randomness unknown to the user.
Quantum private information retrieval (QPIR) for quantum messages is a quantum communication task, in which a user retrieves one of the multiple quantum states from the server without revealing which state is retrieved. In the one-server setting, we find an exponential gap in the communication complexities between the presence and absence of prior entanglement in this problem with the one-server setting. To achieve this aim, as the first step, we prove that the trivial solution of downloading all messages is optimal under QPIR for quantum messages, which is a similar result to that of classical PIR but different from QPIR for classical messages. As the second step, we propose an efficient one-server one-round QPIR protocol with prior entanglement by constructing a reduction from a QPIR protocol for classical messages to a QPIR protocol for quantum messages in the presence of prior entanglement.
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
Quantum private information retrieval (QPIR) is a protocol in which a user retrieves one of multiple files from n\mathsf{n}n non-communicating servers by downloading quantum systems without revealing which file is retrieved. As variants of QPIR with stronger security requirements, symmetric QPIR is a protocol in which no other files than the target file are leaked to the user, and t\mathsf{t}t-private QPIR is a protocol in which the identity of the target file is kept secret even if at most t\mathsf{t}t servers may collude to reveal the identity. The QPIR capacity is the maximum ratio of the file size to the size of downloaded quantum systems, and we prove that the symmetric t\mathsf{t}t-private QPIR capacity is min⁡{1,2(n−t)/n}\min\{1,2(\mathsf{n}-\mathsf{t})/\mathsf{n}\}min{1,2(n−t)/n} for any 1≤t<n1\leq \mathsf{t}< \mathsf{n}1≤t<n. We construct a capacity-achieving QPIR protocol by the stabilizer formalism and prove the optimality of our protocol. The proposed capacity is greater than the classical counterpart.
Quantum private information retrieval (QPIR) is a protocol in which a user retrieves one of multiple files from n non-communicating servers by downloading quantum systems without revealing which file is retrieved. As variants of QPIR with stronger security requirements, symmetric QPIR is a protocol in which no other files than the target file are leaked to the user, and t-private QPIR is a protocol in which the identity of the target file is kept secret even if at most t servers may collude to reveal the identity. The QPIR capacity is the maximum ratio of the file size to the size of downloaded quantum systems, and we prove that the symmetric t-private QPIR capacity is min{1,2( n- t)/ n} for any 1 ≤ t <; n. We construct a capacity-achieving QPIR protocol by the stabilizer formalism and prove the optimality of our protocol. The proposed capacity is greater than the classical counterpart.
We study the capacity of quantum private information retrieval (QPIR) with multiple servers. In the QPIR problem with multiple servers, a user retrieves a classical file by downloading quantum systems from multiple servers each of which contains the copy of a classical file set while the identity of the downloaded file is not leaked to each server. The QPIR capacity is defined as the maximum rate of the file size over the whole dimension of the downloaded quantum systems. When the servers are assumed to share prior entanglement, we prove that the QPIR capacity with multiple servers is 1 regardless of the number of servers and files. We construct a rate-one protocol only with two servers. This capacity-achieving protocol outperforms its classical counterpart in the sense of the capacity, server secrecy, and upload cost. The strong converse bound is derived concisely without using any secrecy condition. We also prove that the capacity of multi-round QPIR is 1.
Quantum private information retrieval (QPIR) is a protocol that a user retrieves one of f files from non-communicating n servers by downloading quantum systems without revealing the identity of the target file. As variants of the QPIR with stronger security requirements, the symmetric QPIR is that the files except for the target file are not leaked to the user, and the t-private QPIR is that the identity of the target file is kept secret even if at most t servers may collude to reveal the identity. The QPIR capacity is the maximum ratio of the one file size to the size of downloaded quantum systems, and we prove that the symmetric t-private QPIR capacity is min {1, 2(n - t)/n} for any 1 ≤ t <; n. We construct a capacity-achieving QPIR protocol by the stabilizer formalism and prove the optimality of our protocol. The proposed capacity is greater than the classical counterpart.