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:2611.03558

Quantum Private Information Retrieval on Forests

Mohamed Nomeir, Sennur Ulukus

cs.ITcs.CRcs.NIeess.SPquant-phSubmitted Nov 2, 2026• Announced Nov 3, 2026• 0 citations
arXivHTMLPDF

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 $\frac{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.

AI Summary

The paper studies quantum private information retrieval (QPIR) with graph-based storage: vertices are noncolluding servers, and each independent classical message is replicated at the two endpoints of an edge. Queries are classical, servers share entanglement before retrieval, and each server sends one qudit to the user. The objective is zero-error recovery while hiding the requested message index from every individual server. For forests consisting of at least two nontrivial tree components, with no isolated vertices, it constructs a one-round scheme achieving $R_Q=3/N$ for every prime qudit dimension $p>N$. Each file contains three field symbols. Local Pauli encodings of a shared $N$-party GHZ state allow the user to measure one sum and $N-1$ differences of server-generated quantities. Cancellation across undesired edges, cuts formed by removing the desired edge, and an additional tree component recover the three desired symbols. Random invertible transformations of each file ensure query privacy. The rate is $3/2$ times the cited general graph-based quantum construction’s $2/N$, and also exceeds classical capacity by that factor for matching graphs. For the six-server matching $G=3K_2$, a separate construction over $\mathbb F_7$, using the $N$-sum-box framework and linear decoding, retrieves four symbols from six qudits. A non-signaling cut-set converse proves capacity $C_Q=4/6=2/3$. The general forest result is an achievable rate rather than a capacity characterization; its stated scope excludes connected trees and isolated vertices.

Little sign of AI-generated textPossible error

Central claim may not hold: The abstract's forest-wide 3/N claim is broader than the proved construction, which requires at least two nontrivial tree components; the unrestricted claim fails already for K₂ by the Holevo dimension bound. The 3K₂ construction prints an incorrect block-matrix inverse, producing a transfer-matrix sign inconsistent with its outputs, although replacing Γ with −Γ in G repairs the construction.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Related papers

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•39 citations

Quantum Private Information Retrieval for Quantum Messages

Seunghoan Song, Masahito Hayashi

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.

arXiv:2101.09041•IEEE International Symposium on Information Theory (ISIT)•Jul 12, 2021•9 citations

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•4 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 containing the whole classical file set, without revealing the identity of the retrieved file to any individual server. The QPIR capacity is defined as the maximum rate of the file size over the whole dimension of the downloaded quantum systems. Assuming the preexisting entanglement among servers, we prove that the QPIR capacity with multiple servers is 1 regardless of the number of servers and files. We propose a rate-one protocol which can be implemented by using only 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 the secrecy conditions.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2019•9 citations

Capacity of Quantum Private Information Retrieval with Collusion of All But One of Servers

Seunghoan Song, Masahito Hayashi

Quantum private information retrieval (QPIR) is the problem to retrieve one of f classical files by downloading quantum systems from non-communicating n servers each of which contains the copy of f files, while the identity of the retrieved file is unknown to each server. As an extension, we consider the (n-1)-private QPIR that the identity of the retrieved file is secret even if any n-1 servers collude, and derive the QPIR capacity for this problem which is defined as the maximum rate of the retrieved file size over the download size. For an even number n of servers, we show that the capacity of the (n-1)-private QPIR is 2/n, when we assume that there are preexisting entanglements among the servers and require that no information of the nonretrieved files is downloaded. We construct an (n - 1)-private QPIR protocol of rate Γn/21-1and prove that the capacity is upper bounded by 2/n. The (n - 1)-private QPIR capacity is strictly greater than the classical counterpart. The full version of this paper is accessible at: https://arxiv.org/pdf/1903.12556.

IEEE Information Theory Workshop (ITW)•Aug 1, 2019•9 citations

On the Capacity of Quantum Private Information Retrieval From MDS-Coded and Colluding Servers

Matteo Allaix, Seunghoan Song, Lukas Holzbaur +3 more

In quantum private information retrieval (QPIR), a user retrieves a classical file from multiple servers by downloading quantum systems without revealing the identity of the file. The QPIR capacity is the maximal achievable ratio of the retrieved file size to the total download size. In this paper, the capacity of QPIR from MDS-coded and colluding servers is studied for the first time. Two general classes of QPIR, called stabilizer QPIR and dimension-squared QPIR induced from classical strongly linear PIR are defined, and the related QPIR capacities are derived. For the non-colluding case, the general QPIR capacity is derived when the number of files goes to infinity. A general statement on the converse bound for QPIR with coded and colluding servers is derived showing that the capacities of stabilizer QPIR and dimension-squared QPIR induced from any class of PIR are upper bounded by twice the classical capacity of the respective PIR class. The proposed capacity-achieving scheme combines the star-product scheme by Freij-Hollantiet al.and the stabilizer QPIR scheme by Songet al.by employing (weakly) self-dual Reed–Solomon codes.

arXiv:2106.14719•IEEE Journal on Selected Areas in Communications•Jan 26, 2022•21 citations
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 3N\frac{3}{N}N3​. 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=3K2G=3K_2G=3K2​, which is equal to 4/64/64/6. G=3K2G=3K_2G=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/64/64/6 and provide the corresponding matching upper bound, establishing it as the capacity.
The paper studies quantum private information retrieval (QPIR) with graph-based storage: vertices are noncolluding servers, and each independent classical message is replicated at the two endpoints of an edge. Queries are classical, servers share entanglement before retrieval, and each server sends one qudit to the user. The objective is zero-error recovery while hiding the requested message index from every individual server.
For forests consisting of at least two nontrivial tree components, with no isolated vertices, it constructs a one-round scheme achieving RQ=3/NR_Q=3/NRQ​=3/N for every prime qudit dimension p>Np>Np>N. Each file contains three field symbols. Local Pauli encodings of a shared NNN-party GHZ state allow the user to measure one sum and N−1N-1N−1 differences of server-generated quantities. Cancellation across undesired edges, cuts formed by removing the desired edge, and an additional tree component recover the three desired symbols. Random invertible transformations of each file ensure query privacy. The rate is 3/23/23/2 times the cited general graph-based quantum construction’s 2/N2/N2/N, and also exceeds classical capacity by that factor for matching graphs.
For the six-server matching G=3K2G=3K_2G=3K2​, a separate construction over F7\mathbb F_7F7​, using the NNN-sum-box framework and linear decoding, retrieves four symbols from six qudits. A non-signaling cut-set converse proves capacity CQ=4/6=2/3C_Q=4/6=2/3CQ​=4/6=2/3. The general forest result is an achievable rate rather than a capacity characterization; its stated scope excludes connected trees and isolated vertices.
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) 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.
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 containing the whole classical file set, without revealing the identity of the retrieved file to any individual server. The QPIR capacity is defined as the maximum rate of the file size over the whole dimension of the downloaded quantum systems. Assuming the preexisting entanglement among servers, we prove that the QPIR capacity with multiple servers is 1 regardless of the number of servers and files. We propose a rate-one protocol which can be implemented by using only 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 the secrecy conditions.
Quantum private information retrieval (QPIR) is the problem to retrieve one of f classical files by downloading quantum systems from non-communicating n servers each of which contains the copy of f files, while the identity of the retrieved file is unknown to each server. As an extension, we consider the (n-1)-private QPIR that the identity of the retrieved file is secret even if any n-1 servers collude, and derive the QPIR capacity for this problem which is defined as the maximum rate of the retrieved file size over the download size. For an even number n of servers, we show that the capacity of the (n-1)-private QPIR is 2/n, when we assume that there are preexisting entanglements among the servers and require that no information of the nonretrieved files is downloaded. We construct an (n - 1)-private QPIR protocol of rate Γn/21-1and prove that the capacity is upper bounded by 2/n. The (n - 1)-private QPIR capacity is strictly greater than the classical counterpart. The full version of this paper is accessible at: https://arxiv.org/pdf/1903.12556.
In quantum private information retrieval (QPIR), a user retrieves a classical file from multiple servers by downloading quantum systems without revealing the identity of the file. The QPIR capacity is the maximal achievable ratio of the retrieved file size to the total download size. In this paper, the capacity of QPIR from MDS-coded and colluding servers is studied for the first time. Two general classes of QPIR, called stabilizer QPIR and dimension-squared QPIR induced from classical strongly linear PIR are defined, and the related QPIR capacities are derived. For the non-colluding case, the general QPIR capacity is derived when the number of files goes to infinity. A general statement on the converse bound for QPIR with coded and colluding servers is derived showing that the capacities of stabilizer QPIR and dimension-squared QPIR induced from any class of PIR are upper bounded by twice the classical capacity of the respective PIR class. The proposed capacity-achieving scheme combines the star-product scheme by Freij-Hollantiet al.and the stabilizer QPIR scheme by Songet al.by employing (weakly) self-dual Reed–Solomon codes.