Quantum Private Information Retrieval on Forests

Quantum Private Information Retrieval on Forests

arXiv:2611.03558v1 [cs.IT] 2 Nov 2026

Mohamed Nomeir Sennur Ulukus Department of Electrical and Computer Engineering University of Maryland, College Park, MD 20742 mnomeir@umd.edu ulukus@umd.edu Due to the abundance of data, the focus in PIR research has shifted towards relaxing the full replication requirement. One of the ways of doing this is through graph PIR. In graph PIR, the nodes of the graph represent the servers and the hyperedges represent the messages. Thus, a message is available at a subset of servers if the edge representing that message is incident to the nodes corresponding to these servers. Although the formulation of the graph version of PIR is straightforward, it remains one of the most challenging problems in the PIR literature. Many works have provided general upper bounds or specific capacities for certain graphs [10], [31]–[35]. Most recently, [36] provided a scheme for any arbitrary graph-based PIR in the classical setting. The scheme designed integrates well with the quantum setting as mentioned briefly in their abstract and a remark, thus achieving super-dense coding I. I NTRODUCTION gain. Although the scheme in [36] performs well in most quantum PIR settings, it can be inefficient in some specific Private information retrieval (PIR) has been introduced in scenarios, due to the generality of the scheme. To the best [1]. The PIR system consists of N servers with K messages of our knowledge, [36] is the only paper that mentions the replicated in their storage. The user wants to retrieve one of quantum version of PIR over graphs. In this paper, we focus the K messages without revealing the required message index on one family of graph PIR, namely, forest graphs and analyze to any of the servers. The main metric for the efficiency in its quantum setting. We design a scheme for general forest the PIR problem is the rate, which is the ratio between the graphs that achieves the rate RQ = 3/N . We then focus on the required message length and the total number of downloaded matching graph 3K2 , where there are 3 messages, 6 servers symbols. The capacity is defined as the highest possible and each message is stored in exactly two servers. We design achievable rate. In [2], it was shown that the capacity of a specialized scheme for this graph that has a rate RQ = 4 . 6 such a setting with N servers and K replicated messages We show that the achieved rate for G = 3K2 is the highest
−1 1 is C = 1 + N1 + . . . + N K−1 . Since then, many variants possible rate, thus resolving the capacity for this graph. have appeared with different threat models, see e.g., [3]–[17]. The rest of the paper is organized as follows. Section II Recently, quantum communications has gained significant provides the problem formulation and the background needed focus in the research community due to their potential to for the N -sum box framework. In Section III, we provide provide higher gains in general compared to their classical the main results and comparisons with both the classical and counterparts. It was shown in [18] that a qubit can carry quantum PIR results available in the literature. In Section IV, two bits of information from the transmitter to the receiver we provide the scheme for the general forest graphs. We provide if they share an entangled state prior to the scheme initiation. an illustrative example in Section V. Finally, in Section VI, we This was coined as super-dense coding gain. Another variant provide the achievable scheme and the upper-bound derivation for multi-transmitter communication systems was developed for G = 3K2 , establishing the capacity for this case. that analyzes the setting with the transmitters sharing an Notations: The symbol Fp is used to denote the finite field entangled state without sharing with the receiver. In this setting with p elements, where p is a prime. The set {1, 2, . . . , N } it was shown that at most N bits can be recovered from N is denoted by [N ] and the set {a, a + 1, . . . , b} is denoted entangled transmitters due to Holevo’s bound [19]. However, by [a : b], where a and b are positive integers with b > a. most recently, it was shown that for specific applications the GLm (Fp ) is the group of the generalized linear operators of rate of the quantum setting can achieve super-dense coding size m × m with elements from Fp . 1N is the all-ones column gains in some cases [20]–[23]. In addition, it was shown that vector with length N . KN is used to denote the complete graph for the quantum version of PIR (QPIR), the super-dense coding with N nodes. We use ⊔ to denote the union of disjoint sets. gain is achievable for certain regimes [24]–[30]. We denote the rate of the extended quantum scheme based on

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 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 = 3K2 , which is equal to 4/6. G = 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/6 and provide the corresponding matching upper bound, establishing it as the capacity.

with |V (Tj )| ≥ 2, j ∈ [c]. Thus, there are no isolated vertices, N ≥ 4, and K = N − c ≥ 2. II. P ROBLEM F ORMULATION Prior to the scheme initiation, we orient every edge publicly Let G = (V, E) be a simple graph where the vertices V and fix this orientation before retrieval, i.e., the notation e = represent the servers and the edges E represent the messages. (ue , ve ) specifies its tail and head. We make use of the N -sum box abstraction in [38]. The Thus, an edge e ∈ E that is incident to the two servers u, v represents the presence of the message We in both the uth main theorem that we make use of is stated as follows. and the vth server. We denote the messages as W(u,v) when Theorem 1 (Theorem 1 in [38]). Let G be a2N × N SSO necessary. Note that the number of servers is N = |V | and 0 IN t , and let H be the number of messages is K = |E|. Each message We has L matrix, i.e., G JG = 0, where J = −I 0 N symbols that are generated uniformly at random from FL , i.e., p a 2N × N matrix with full column rank. If [G H] is a full-rank X X matrix, then M = [0N IN ][G H]−1 is a feasible N -sum box H(W[K] ) = H(Wi ) = H(We ) = KL. (1) transfer matrix. the work by Liu-Jia-Jia [36] as RLJJ,Q .

e∈E

i∈[K]

A user who chooses Θ = θ uniformly at random from [K] wants to retrieve Wθ without revealing the required message [θ] index θ to any server. To do that, the user sends queries Qn to the nth server. Since the user has no prior knowledge about the message contents, we have [Θ]

I(W[K] ; Θ, Q[N ] ) = 0.

(2)

In addition, to ensure user privacy I(Θ; Wn , Q[Θ] n ) = 0,

n ∈ [N ],

(3)

where Wn is the storage at the nth server. Once the nth server [θ] [θ] receives the query Qn , it generates an answer An that is a deterministic function of the storage and the received query, i.e., [Θ] H(A[Θ] n |Wn , Qn ) = 0,

n ∈ [N ].

(4)

In the quantum setting, we assume that the servers share an entangled state represented by the density matrix ρ in the Hilbert space H, with log dim(H) = N . The nth server encodes the answer over its share of the entangled state ρn = tri∈[N ]\n (ρ) and transmits to the user over a noise-free quantum channel ρ′n = Encn (ρn , A[Θ] n ).

(5)

Once the user receives all the quantum states ρ′[N ] and applies a POVM to get the classical information YΘ , the user must be able to decode the required message, i.e., [Θ]

H(WΘ |YΘ , Q[N ] ) = 0.

(6)

III. M AIN R ESULTS Theorem 2. For every forest satisfying (7) and every prime p > N , there is a one-round, zero-error PIR scheme with one fixed N -party GHZ state, and exactly one p-dimensional qudit transmitted by each server, that achieves a rate 3 . N The scheme is given in Section IV. RQ =

(8)

Theorem 3. For G = 3K2 , the quantum PIR capacity is given by 4 . (9) 6 The scheme and the converse are given in Section VI. CQ =

Corollary 1 (Comparison with the graph-based quantum extension in [36]). Specialize [36, Thm. 1, Eqn. (15), and Remark 3] to two replicas, uncoded replication ηm = 1, X = 0, and T = 1. Its rate is RLJJ,Q = N2 . Thus, for every graph in Theorem 2, RQ 3 = . RLJJ,Q 2

(10)

Proof: Using the same notation as in the original paper [36], for a message group stored at the two endpoints {u, v}, the oneelement-subset constraints in the cited achievable region require both classical normalized downloads to satisfy du ≥ 1 and dv ≥ 1. Every vertex is incident to an edge, thus the minimum total normalized classical download within this region is N . [36, Remark 3] gives the corresponding quantum normalized download N/2. ■

The rate is defined as the ratio between the size of the required message and the number of received qudits. Since there are N received qudits and the message lengths are equal L, the Corollary 2. For a matching G = mK2 with m ≥ 2 and L rate is given by RQ = N . Thus, the goal is to maximize L in N = 2m, classical PIR capacity is CC (G) = 1/m = 2/N . Theorem 2 achieves the quantum rate 3/N , exceeding that order to increase the rate. In this paper, we focus on forest graphs only. We use standard classical capacity by a factor of 3/2. In addition, for m = 3, graph terminology [37]. A forest is a disjoint union of trees. Theorem 3 achieves super-dense coding gain, i.e., gain by a A nontrivial tree has at least two vertices. Thus, a forest graph factor of 2. G can be written as a union of disjoint trees, i.e., Proof: Label the messages (edges) of G = mK2 as ei = G = T1 ⊔ · · · ⊔ Tc , c ≥ 2, (7) {2i − 1, 2i}, i ∈ [m], and let W be the file stored at the i

two endpoints of ei . Thus, servers 2i − 1 and 2i store Wi . In addition, no other server stores this file. Converse: Consider an arbitrary classical PIR scheme. From [i ] the individual server privacy, we know that H(An1 ) = [i2 ] [iK ] H(An ) = . . . = H(An ). Thus, we can define dn = H(A[i] n ),

n ∈ [N ],

(11)

using any desired index i. In particular, the same vector (d1 , . . . , dN ) describes the server-answer entropies for every desired file. We now apply the argument of [39, Lemma 3] to edge ei . Let Pi = {2i − 1, 2i}, and W−i = (Wj )j∈[m]\{i} . Independence of the files and queries gives [i]

H(Wi | W−i , Q[N ] ) = L.

(12)

Every answer outside Pi is a deterministic function of its local query and a file contained in W−i . Therefore,   [i] [i] (13) H A[N ]\Pi | W−i , Q[N ] = 0. [i]

Thus, given W−i and Q[N ] , the user can reconstruct all answers outside Pi . Zero-error correctness then implies   [i] [i] H Wi | APi , W−i , Q[N ] = 0. (14) Combining (12) and (14), we obtain   [i] [i] L = I Wi ; APi | W−i , Q[N ]   [i] [i] ≤ H APi | W−i , Q[N ] [i]

[i]

(15) (16)

≤ H(A2i−1 ) + H(A2i )

(17)

= d2i−1 + d2i .

(18)

Although equality in (18) is derived by considering retrieval of Wi , privacy expresses every such inequality using the same quantities dn . Moreover, the m edges are vertex-disjoint and cover all N = 2m servers. Summing over i ∈ [m] gives N X n=1

dn =

m X (d2i−1 + d2i ) ≥ mL.

(19)

i=1

Hence, every classical PIR scheme satisfies 1 ≤ . RC = PN m n=1 dn L

(20)

This is precisely the matching-number converse CC (G) ≤ 1/ν(G) in [39], specialized to ν(G) = m. Achievability: Choose an even file length L and split every file into two equal-length parts, Wi = (Wi,L , Wi,R ), with each having length L2 . For every desired index, send the same fixed queries: server 2i − 1 returns Wi,L , and server 2i returns Wi,R , for every i ∈ [m]. The user consequently recovers all m files, including the desired file. Privacy holds because the queries do not depend on the desired index. Each server returns L/2 symbols, therefore the achieved rate is 1/m, showing CC (mK2 ) =

1 2 = , m N

(21)

and completing the proof. ■ Remark 1. Since the path graph PN is a tree (note that K2 is also a path), we can have a disjoint union of paths as a forest graph, i.e., G = mPN is a forest. It was shown in for this setting is C(mPN ) = P[40] that the capacity −1 2 −1 = mN , which coincides with the above i∈[m] C(PN ) proof for mK2 . Remark 2. A star graph with one main hub and N leaves, denoted K1,N , is also considered as a tree graph. In [10], it 5 was shown that C(K1,4 ) = 12 . Thus, for G = 2K1,4 , we have 5 C(G) = 24 . In comparison with Theorem 2, the rate gain is RQ /RC = 1.44. IV. S CHEME FOR T HEOREM 2 We use the generalized Pauli operators X(b)|t⟩ = |t + b⟩,

(22)

at

Z(a)|t⟩ = ω |t⟩,

(23)

where ω = exp(2πi/p) and p is a prime [19]. The following lemma provides the main quantum encoding and measurements used in the forest graph. We show the explicit N -sum box abstraction [38] afterwards. Lemma 1. Suppose server n knows two scalars an , bn ∈ Fp and has one qudit from the GHZ state represented by 1 X ⊗N |t⟩ . (24) |GHZN,p ⟩ = √ p t∈Fp

The user can recover N X S= an , ∆i = bi − bN ,

i ∈ [N − 1],

(25)

n=1

by receiving exactly one qudit from each server. Proof: Server n applies X(bn )Z(an ) to its own qudit and sends that qudit to the user. The received pure state is 1 X St ω |t + b1 , . . . , t + bN ⟩. (26) √ p t Set z = t+bN and ∆i = bi −bN . Up to a global phase ω −SbN , this is 1 X Sz ω |z + ∆1 , . . . , z + ∆N −1 , z⟩. (27) |ΨS,∆ ⟩ = √ p z Different ∆ = (∆1 , . . . , ∆N −1 ) values give disjoint computational basis supports. For a fixed inner product for P ∆, the ′ two phase labels S, S ′ is p−1 z ω (S−S )z , which is one if S = S ′ and zero otherwise. Thus, the pN states in (27) form an orthonormal basis for the N -qudit space. Measuring in that fixed basis recovers every label in (25) with certainty. ■ For mapping this to the N -sum box abstraction [38], let the input order be (a1 , . . . , aN , b1 , . . . , bN ), where the ith transmitter has the pair (ai , bi ), the transfer matrix is  ⊤  1N 0 MN = , (28) 0 DN

where DN = [IN −1 , −1N −1 ]. It has rank N . To see that it is a valid N -sum box, we make use of Theorem 1. Define   0    ..  IN −1 . eN =   , EN = . (29) 01×(N −1) 0

For e ̸= θ, the contributions of its endpoints to (an , bn ) are (Ae , Be )

Noe that G has rank N , and  0 t G JN G = −DN 1N

 ⊤ 1⊤ N DN = 0, 0

because DN 1N = 0. Moreover, [G H] is invertible, with   01×N −e⊤ N ⊤  −1  EN 0(N −1)×N  . G H =  1⊤ 01×N  N 0(N −1)×N DN

(−Ae , −Be ).

(39)

(Cθ , Aθ ).

(40)

For e = θ, they are (Aθ , Bθ )

1 Then, G and H are given as follows   ⊤ 0N ×1 DN G= , −1N 0N ×(N −1)   eN 0N ×(N −1) H= . 0N ×1 EN

and

and

Thus, S = Aθ + Cθ . (30) (31)

(32)

B. Decoding It is clear that deleting the edge θ from G splits its tree into two vertex sets Aθ and Bθ , containing uθ and vθ , respectively. The user chooses any other original tree component, we can denote its vertex set by C. Note that such a component always exists because c ≥ 2. These three sets are known to the user since the storage graph G is known. Lemma 2. The inputs in (38) satisfy X bn = 0,

(41)

n∈C

(33)

X

bn = Bθ ,

(42)

bn = Aθ .

(43)

n∈Aθ

X

Thus, (28) is a valid N -sum box.

n∈Bθ

A. Queries and Encoding Independently for each edge e, the user samples the matrix Re ∈ GL3 (Fp ) uniformly at random. It can be written as   re,1 Re = re,2  . (34) re,3 Write the transformed coordinates as Re We = [Ae , Be , Ce ]t .

Proof: Every undesired edge internal to a vertex set contributes Be − Be = 0 by (39). No edge crosses an original component C. The only edge crossing either component of the tree with θ removed is θ itself: a second crossing edge would create a cycle. Thus, the only uncancelled contribution in Aθ is Bθ at its tail, and the only one in Bθ is Aθ at its head. ■ Set ∆N = 0 in addition to the measured differences, and let ζ = bN . For every server,

(35)

bn = ∆n + ζ. (44) The user knows Re but does not know these coordinate values. A server computes only the linear forms specified in its query. Note that (41) determines the unknown common shift Let the desired edge be θ = (uθ , vθ ). For every oriented X ζ = −|C|−1 ∆n . (45) edge e = (ue , ve ), the user sends the tail of the two row vectors     n∈C αue ,e r = e,1 , (36) The inverse exists because 1 ≤ |C| ≤ N < p. The user can βue ,e re,2 now compute every bn . and sends its head the following two row vectors The three desired coordinates are recovered explicitly as " #  r X  e,3 , e = θ,    Aθ = bn , (46)  r αve ,e " e,1 # n∈Bθ (37) X βve ,e   −re,1  , e ̸= θ. Bθ = bn , (47)   −r e,2

n∈Aθ

Server n receives just these two coefficient rows for each of its stored files, then computes two scalars from its stored files X X an = αn,e We , bn = βn,e We . (38) e∋n

e∋n

It applies X(bn )Z(an ) to its single qudit of (24). The user applies Lemma 1 and obtains (25).

Cθ = S − Aθ .

(48)

Finally, Wθ = Rθ−1 (Aθ , Bθ , Cθ )t . It is clear that privacy is guaranteed from each server since Re is generated uniformly at random and independently of t t t t t t t t t Θ. Thus, each of [re,1 , re,2 ] , [re,3 , re,1 ] and [−re,1 , −re,2 ] is independent of Θ and has rank 2.

where Γ is symmetric and recall that   Let G = K2 ⊔K2 , with W1 at servers 1, 2 and W2 at servers 0 I6 J = . (57) 6 3, 4. Every file has three independent Fp symbols, where p > 4. −I6 0 Let the user draw R1 , R2 independently and uniformly from In addition GL3 (Fp ), and let    −1 0 I6     G H = . (58) a d I6 Γ     R1 W1 = b , R2 W2 = e . (49) Now, to design the queries, for each e ∈ [3], generate Re ∈ c f GL4 (F7 ) uniformly at random. Denote the ith row of Re as Every server receives only its coefficient rows. Table I shows re,i and define the symbols transmitted per server. Re We = [ae , be , ce , de ]t . (59) V. I LLUSTRATIVE E XAMPLE

Server 1 2 3 4

Stored file W1 W1 W2 W2

Desired W1 (a, b) (c, a) (d, e) (−d, −e)

Desired W2 (a, b) (−a, −b) (d, e) (f, d)

Table II provides the queries sent to each server for each required message index. It is clear that privacy is guaranteed since the scalar multiplication/division is done over a finite field.

TABLE I: Inputs (an , bn ) for G = K2 ⊔ K2 . The user receives the outputs of the transfer matrix   1 1 1 1 0 0 0 0  0 0 0 0 1 0 0 −1   M4 =   0 0 0 0 0 1 0 −1  . 0 0 0 0 0 0 1 −1

(50)

Request W1 (r1,1 , r1,3 ) (r1,2 , r1,4 ) ( 12 r2,2 , r2,1 ) (r2,1 , r2,2 ) (r3,2 , r3,1 ) (2r3,1 , r3,2 )

(51)

Request W3 (r1,1 , r1,2 ) (r1,2 , 12 r1,1 ) (2r2,1 , r2,2 ) ( 12 r2,2 , 2r2,1 ) (r3,1 , r3,3 ) (r3,2 , r3,4 )

Now, once each server receives these queries, they apply the dot product for each of ri,j on its stored message. Let θ = 1, then each server produces the following answers [1]

The user computes e = ∆3 /2, a = ∆2 − e, b = ∆1 − e, c = S − a. The user then recovers W1 = R1−1 (a, b, c)t . In the case of retrieving W2 , the measured labels become (S, ∆1 , ∆2 , ∆3 ) = (d + f, b − d, −b − d, e − d).

Request W2 ( 12 r1,1 , r1,2 ) (2r1,2 , 12 r1,1 ) (r2,1 , r2,3 ) (r2,2 , r2,4 ) (2r3,2 , r3,1 ) (r3,1 , r3,2 )

TABLE II: Queries for the 3K2 scheme.

Recall that this matrix and the shared GHZ state and the measurements provided in Lemma 1 are the same. If W1 is being retrieved, the measured labels are (S, ∆1 , ∆2 , ∆3 ) = (a + c, b + e, a + e, 2e).

Server S1 S2 S3 S4 S5 S6

(52)

2 Hence, d = − ∆1 +∆ , e = ∆3 + d, f = S − d, and the user 2 −1 obtains W2 = R2 (d, e, f )t .

VI. P ROOF OF T HEOREM 3 We first choose the field size p = 7 and appropriate N -sum box as follows. Define     0 I2 B 0 1 B= , Γ =  I2 0 I2  . (53) 2 0 B t I2 0

A1 = (a1 , c1 ), 1 [1] A3 = ( b2 , a2 ), 2 [1] A5 = (b3 , a3 ),

[1]

(60)

[1]

(61)

[1]

(62)

A2 = (b1 , d1 ), A4 = (a2 , b2 ), A6 = (2a3 , b3 ).

The received classical bits upon measurement are given by    [1]  a1 + a2 + b3 A1    [1]   b1 + b12 + 2a3  A2  c1 + b2 + a3  2    Y =M (63)  ..  =  d1 + a2 + b3  .   .   2d1 + a2 + b3  [1] A6 c1 + b2 + 2a3 Now, to retrieve a1 , b1 , c1 , d1 , we apply the following linear decoding

Using the representation of the N -sum box matrix M = [0N IN ][G H]−1 , we choose     Γ I G= , H= 6 . (54) I6 06

a1 = y1 − 2y4 + y5 ,

It can be verified that M satisfies the N -sum box required properties as follows    t  I6 t −Γ I G J6 G = (55) 6 Γ

In general, the decoding for each required message index is given in Table III. Since the scheme can retrieve 4 symbols using 6 qudits, then the scheme achieves the rate RQ = 46 . The converse follows from the non-signaling principle and the cut-set bound [23, Lemma 1]. Fix a message Wi , stored at servers i, i + 3 and put these two servers storing Wi on one

= Γt − Γ = 0,

(56)

(64)

b1 = y2 + 2y3 − 2y6 ,

(65)

c1 = 2y3 − y6 ,

(66)

d1 = y5 − y4 .

(67)

Coordinate aθ bθ cθ dθ

Request W1 y1 − 2y4 + y5 y2 + 2y3 − 2y6 2y3 − y6 y5 − y 4

Request W2 y3 + y 6 − y 2 y4 + y 1 − y 5 2y1 − y5 2y6 − y2

Request W3 y5 + 2y4 − 2y1 y6 + y2 − 2y3 y2 − y 3 2y4 − y1

TABLE III: Scalar decoding for the 3K2 scheme. side of the cut and the user along with other servers on the other side of the cut. Let Di be the number of downloaded qudits from the ith server. For decodability, we have L ≤ 2Di + 2Di+3 . Thus, summing over the three messages, we have X 3L ≤ 2 Di ,

(68)

(69)

i∈[6]

showing that the rate is upper bounded as R ≤ 23 as required. R EFERENCES [1] B. Chor, E. Kushilevitz, O. Goldreich, and M. Sudan. Private information retrieval. Jour. of the ACM, 45(6):965–981, November 1998. [2] H. Sun and S. A. Jafar. The capacity of private information retrieval. IEEE Trans. Info. Theory, 63(7):4075–4088, July 2017. [3] Q. Wang and M. Skoglund. On PIR and symmetric PIR from colluding databases with adversaries and eavesdroppers. IEEE Transactions on Information Theory, 65(5), October 2019. [4] C. Tian, H. Sun, and J. Chen. Capacity-achieving private information retrieval codes with optimal message size and upload cost. IEEE Trans. Info. Theory, 65(11):7613–7627, November 2019. [5] Z. Jia, H. Sun, and S. A. Jafar. Cross subspace alignment and the asymptotic capacity of X-secure T -private information retrieval. IEEE Trans. Info. Theory, 65(9):5783–5798, May 2019. [6] K. Banawan and S. Ulukus. The capacity of private information retrieval from Byzantine and colluding databases. IEEE Trans. Info. Theory, 65(2):1206–1219, September 2018. [7] Z. Wang and S. Ulukus. Symmetric private information retrieval at the private information retrieval rate. IEEE Jour. on Selected Areas in Info. Theory, 3(2):350–361, June 2022. [8] S. Ulukus, S. Avestimehr, M. Gastpar, S. A. Jafar, R. Tandon, and C. Tian. Private retrieval, computing, and learning: Recent progress and future challenges. IEEE Journal on Selected Areas in Communications, 40(3):729–748, March 2022. [9] R. Tajeddine, O. Gnilke, and S. El Rouayheb. Private information retrieval from MDS coded data in distributed storage systems. IEEE Trans. Info. Theory, 64(11):7081–7093, March 2018. [10] Y. Yao and S. Jafar. The capacity of 4-star-graph PIR. In IEEE ISIT, June 2023. [11] O. Makkonen, D. Karpuk, and C. Hollanti. Secret sharing for secure and private information retrieval: A construction using algebraic geometry codes. IEEE Trans. Info. Theory, 2026. To appear. Also available online at arxiv:2408.00542. [12] M. Nomeir, S. Meel, and S. Ulukus. Private information retrieval with arbitrary privacy requirements for graph-based storage. In IEEE ITW, 2026. To appear, also available online at arXiv:2605.10879. [13] M. Nomeir, S. Meel, and S. Ulukus. Private information retrieval with arbitrary privacy requirements: Introduction and capacity results, 2026. Available online at arXiv:2609.15875. [14] S. Meel, M. Nomeir, and S. Ulukus. Local private information retrieval: A new privacy perspective for graph-based replicated systems. In IEEE ITW, 2026. To appear, also available online at arXiv:2605.10872. [15] S. Meel, M. Nomeir, and S. Ulukus. Local private information retrieval for graph-based replicated systems, 2026. Available online at arXiv:2608.31150. [16] M. Nomeir, S. Vithana, and S. Ulukus. Asymmetric X-secure T -private information retrieval: More databases is not always better. In CISS, March 2024.

[17] M. Nomeir, A. Aytekin, and S. Ulukus. The asymptotic capacity of Byzantine symmetric private information retrieval and its consequences. In IEEE ISIT, June 2025. [18] C. Bennett and S. Wiesner. Communication via one- and two-particle operators on Einstein-Podolsky-Rosen states. Physical Review Letters, 69(20):2881–2884, November 1992. [19] M. Nielsen and I. Chuang. Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press, 2010. [20] L. Hu, M. Nomeir, A. Aytekin, Y. Shi, S. Ulukus, and S. Guha. Entanglement-assisted coding for arbitrary linear computations over a quantum MAC. arXiv:2501.16296, 2025. Version 1, January 27, 2025. [21] Y. Yao and S. Jafar. The inverted 3-sum box: General formulation and quantum information theoretic optimality. 2024. Available online at arxiv:2407.01498. [22] Y. Yao and S. Jafar. The capacity of classical summation over a quantum MAC with arbitrarily distributed inputs and entanglements. IEEE Trans. Info. Theory, 70(9):6350–6370, May 2024. [23] L. Hu, M. Nomeir, A. Aytekin, and S. Ulukus. Distributed storage systems with quantum entanglement assistance, 2026. Available online at https://user.eng.umd.edu/∼ulukus/papers/journal/quantumregenerating-codes.pdf. [24] Y. Lu and S. Jafar. A coding scheme for straggler resilient quantum X-secure T -private information retrieval. 2023. Available online at arXiv:2311.07829. [25] S. Song and M. Hayashi. Capacity of quantum private information retrieval with colluding servers. IEEE Transactions on Information Theory, 67(8):5491–5508, May 2021. [26] M. Allaix, S. Song, L. Holzbaur, T. Pllaha, M. Hayashi, and C. Hollanti. On the capacity of quantum private information retrieval from MDS-coded and colluding servers. IEEE Jour. Sel. Areas Commun., 40(3):885–898, January 2022. [27] M. Nomeir, A. Aytekin, and S. Ulukus. Quantum X-secure B-Byzantine T -colluding private information retrieval. In IEEE ITW, November 2024. [28] A. Aytekin, M. Nomeir, and S. Ulukus. Quantum X-secure B-Byzantine T -colluding private information retrieval. 2024. Available online at https://user.eng.umd.edu/ ulukus/papers/journal/QXBTPIR.pdf. [29] A. Aytekin, M. Nomeir, S. Vithana, and S. Ulukus. Quantum symmetric private information retrieval with secure storage and eavesdroppers. In IEEE Globecom, December 2023. [30] A. Aytekin, M. Nomeir, S. Vithana, and S. Ulukus. Quantum X-Secure E-Eavesdropped T -Colluding Symmetric Private Information Retrieval. IEEE Trans. Info. Theory, 71(5):3974–3988, May 2025. [31] G. Ge, H. Wang, Z. Xu, and Y. Zhang. Private information retrieval over graphs, 2025. Available online at arXiv:2509.26512. [32] N. Raviv, I. Tamo, and E. Yaakobi. Private information retrieval in graphbased replication systems. IEEE Trans. Info. Theory, 66(6):3590–3602, November 2019. [33] S. Meel and S. Ulukus. Effect of full common randomness replication in symmetric PIR on graph-based replicated systems. In IEEE ICC, May 2026. [34] S. Meel, X. Kong, T. Maranzatto, I. Tamo, and S. Ulukus. Private information retrieval on multigraph-based replicated storage. In IEEE ISIT, June 2025. [35] S. Meel and S. Ulukus. The role of common randomness replication in symmetric PIR on graph-based replicated systems. IEEE Trans. Info. Theory. To appear, also available online at arXiv:2602.16700. [36] Y. Liu, H. Jia, and Z. Jia. On the storage–communication trade-off in graph-based X-secure T -private linear computation. Entropy, 27(9):975, 2025. [37] J. van Lint and R. Wilson. A Course in Combinatorics. Cambridge University Press, Cambridge, UK, 2nd edition, 2001. [38] M. Allaix, Y. Lu, Y. Yao, T. Pllaha, C. Hollanti, and S. A. Jafar. N -sum box: An abstraction for linear computation over many-to-one quantum networks. IEEE Trans. Info. Theory, 71(2):1121–1139, December 2025. [39] B. Sadeh, Y. Gu, and I. Tamo. Bounds on the capacity of PIR over graphs. In IEEE ISIT, July 2021. [40] X. Kong, S. Meel, T. Maranzatto, I. Tamo, and S. Ulukus. New capacity bounds for PIR on graph and multigraph-based replicated storage. IEEE Trans. Info. Theory, 72(1):691–709, January 2026.

Related documents

• Pulsation of quantum walk on finite graph#1217143
• Laziness of Quantum Walks on Graphs#659293
• Laziness of Quantum Walks on Graphs#657157
• Optimal quantum locally differentially private mechanisms in the high-privacy regime#927326
• Quantum mind#1179911