Authors Fran{\c c}ois Le Gall,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 369–374
www.theoryofcomputing.org
NOTE
Quantum Private Information Retrieval with
Sublinear Communication Complexity
François Le Gall∗
Received: July 29, 2011; published: July 26, 2012.
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( n)-
qubit communication complexity, where n denotes the size of the database. In comparison, it
is known that any classical protocol must use Ω(n) bits of communication in this setting.
ACM Classification: F.2.3
AMS Classification: 81P68
Key words and phrases: private information retrieval, quantum communication complexity
1 Introduction
Private information retrieval deals with the design and the analysis of protocols that allow a user to
retrieve an item from a server without revealing which item it is retrieving. This field, introduced in a
seminal paper by Chor, Kushilevitz, Goldreich, and Sudan [2], has been the subject of intensive research
due to the growing ubiquity of public databases. Examples of applications include ensuring consumer
privacy in e-commerce transactions or reading webpages on the Internet without revealing the user’s
preferences.
In the case of a single server and of information-theoretical privacy, which is the focus of this note,
private information retrieval can be described as follows. The server has a database A = (a1 , a2 , · · · , a` ) ∈
Σ` , where Σ = {0, 1}r is a set of items represented as r-bit strings, and the user has an index i ∈ {1, . . . , `}.
∗ Partly supported by the JSPS, under the grant-in-aid for research activity start-up No. 22800006.
2012 François Le Gall
Licensed under a Creative Commons Attribution License DOI: 10.4086/toc.2012.v008a016
F RANÇOIS L E G ALL
A private information retrieval protocol is a (classical or quantum) communication protocol between
the server and the user such that, when the user and the server both follow the protocol, the user always
outputs the item ai and the server gets no information about the index i, in the following sense (note
that the privacy condition concerns only the user’s input). Let VS (A, i) denote the server’s view of the
communication generated by the protocol when the server has input A and the user has input i. The
privacy condition is that, for any database A ∈ Σ` and any two indexes i, j ∈ {1, . . . , `}, the views VS (A, i)
and VS (A, j) are identical. While several subtleties arise when trying to formally define the server’s view
in an arbitrary quantum protocol, the above description will be sufficient for our purpose due to the
limited interaction between the server and the user in the quantum protocols described in this note.
It is easy to show that, classically, downloading the whole database is essentially optimal: any classical
protocol must communicate a number of bits linear in the size of the database [2]. The communication
complexity of quantum protocols for private information retrieval has first been investigated by Nayak [8],
and then by Kerenidis and de Wolf [5]. These works focused on two-message quantum protocols, and
established a connection with locally decodable codes and random access codes. In particular it was
proved that, for a single server, any private two-message quantum protocol must use a linear amount
of communication. This note shows that this lower bound does not hold for quantum protocols using
more than two messages and describes how to construct a three-message quantum protocol for private
information retrieval with sublinear communication complexity, thus breaking for the first time the linear
barrier in the single-server and information-theoretical privacy setting. This is also the first example in
(quantum or classical) single-server information-theoretic private information retrieval where protocols
with more than two messages outperform protocols with one round of communication. Our main result is
the following theorem.
Theorem 1.1. Let ` and r be any positive integers. There exists a private information retrieval quantum
protocol that, for any database A ∈ Σ` with Σ = {0, 1}r , uses 2` + 2r qubits of communication.
The protocol we design to prove Theorem 1.1, described in Section 2, combines the properties of two-
party entanglement with a technique similar to the one used in the Bernstein-Vazirani algorithm [1], and
ensures the user’s privacy in the following sense: at no time the server holds any (quantum) information
about the user’s input i.
Since the overall size of the database is `r bits, Theorem 1.1 gives a quadratic
√ improvement over
classical protocols and two-message quantum protocols whenever ` + r = O( `r), for example when
` = Θ(r). The same quadratic improvement
√ can also be obtained for√other values of ` and r: the idea is to
decompose the database into about `r blocks, each of size about `r bits. The case r = 1 (i. e., binary
databases) is illustrated in the following corollary.
Corollary 1.2. There√exists a private information retrieval quantum protocol that, for any binary database
A ∈ {0, 1}` , uses O( `) qubits of communication.
Proof. Let A = (a1 , . . . , a` ) ∈ {0, 1}` be the binary database held by the server. For convenience, let us
assume that ` = s2 for some positive integer s (a similar argument works for any value of `). We construct
the database B = (b1 , . . . , bs ) such that, for each k ∈ {1, . . . , s}, the k-th block is bk = (a(k−1)s+1 , . . . , aks ) ∈
{0, 1}s . Note that the bit ai is contained in the block b j with j = di/se. By running the protocol of
Theorem 1.1 where, as inputs, the server has database B and the user has index j, the user is able to
recover the whole block b j , and thus the bit ai , using O(s) qubits of communication.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 369–374 370
Q UANTUM P RIVATE I NFORMATION R ETRIEVAL WITH S UBLINEAR C OMMUNICATION C OMPLEXITY
We stress that this note considers only the setting where the parties do not deviate from the protocol,
as often assumed in works focusing on algorithmic or complexity-theoretic aspects of private information
retrieval. While this restriction may reduce the applicability of our result, we believe that it nevertheless
illustrates the subtle interplay of interaction and quantum information in protecting privacy. Indeed, even
in this setting, a linear amount of communication is needed for classical protocols and for two-message
quantum protocols. A natural open problem is to investigate if the upper bounds in Theorem 1.1 and
Corollary 1.2 are tight and, more specifically, to prove lower bounds on the communication complexity
of quantum protocols for private information retrieval that exchange more than two messages.
Other related works Several other aspects of quantum protocols for private information retrieval
have been investigated. Jain, Radhakrishnan and Sen [4] have shown a linear lower bound on the
communication complexity of private information retrieval quantum protocols in a setting where the
user is allowed to perform superposition attacks (while our work considers only servers that follow the
protocol). Giovannetti, Lloyd and Maccone [3] studied a slightly different cryptographic primitive called
“quantum private query,” in which the user should always detect if the server has been trying to cheat to
obtain information about its input i (but, contrary to the setting of the present note, has not to prevent
leakage of information about i), and presented a cheat sensitive quantum protocol with logarithmic
communication complexity. The case of multiple servers has been studied in [5, 6], while the case of
symmetric private information retrieval, where the server’s privacy is also taken into consideration, has
also been studied in [3, 4, 6]. Privacy issues in quantum communication complexity have been studied
in [7] as well. Let us mention that quantum protocols for symmetric private information retrieval are also
studied under the name of quantum oblivious transfer protocols, especially when the server and the user
may deviate from the protocol (i. e., when considering malicious parties).
2 Proof of Theorem 1.1
We suppose that the reader is familiar with quantum computation and refer to, e. g., [9] for an introduction
to this field. Let us first describe some of our notations. Given two bits a, b ∈ {0, 1}, we write their
parity as a ⊕ b. For any two elements u = (u1 , . . . , ur ) and v = (v1 , . . . , vr ) in Σ = {0, 1}r , let us write
u · v = u1 v1 ⊕ · · · ⊕ ur vr and u ⊕ v = (u1 ⊕ v1 , . . . , ur ⊕ vr ). Note that u · v is a bit and u ⊕ v is an element
of Σ. Our protocol will use the Pauli gate
Z := ∑ (−1)z |zihz|
z∈{0,1}
acting on one qubit and the Hadamard transform
1
Hr := p ∑ (−1)y·z |yihz|
|Σ| y,z∈Σ
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 369–374 371
F RANÇOIS L E G ALL
acting on r qubits. It will also use the gates
CNOT(R1 ,R2 ) := ∑ |yiR |z ⊕ yiR hy|R hz|R
1 2 1 2
and
y,z∈Σ
(R ,Q)
Ub 1 := ∑ |yiR1 |z ⊕ b · yiQ hy|R1 hz|Q ,
y∈Σ,z∈{0,1}
where R1 and R2 denote two r-qubit registers, Q denotes a one-qubit register, and b is any element in Σ.
The gate CNOT performs a bitwise XOR of the first register into the second, while the gate Ub performs
an XOR of the inner product of the first register and b into the second register.
We now present the proof of Theorem 1.1.
Proof of Theorem 1.1. The protocol uses ` + 2 quantum registers: registers R and R0 each consisting of r
qubits, and registers Q1 , . . . , Q` each consisting of one qubit. For any database A = (a1 , . . . , a` ) ∈ Σ` , let
us denote by |ΦA i the quantum state
1
|ΦA i := √ ∑ |xiR |xiR0 |x · a1 iQ1 · · · |x · a` iQ`
2r x∈Σ
in registers (R, R0 , Q1 , . . . , Q` ). The protocol is described in Figure 1. It consists of three messages and
uses a total amount of 2` + 2r qubits of communication.
Server’s input: A = (a1 , . . . , a` ) ∈ Σ`
User’s input: i ∈ {1, . . . , `}
1. The server constructs the quantum state |ΦA i and sends registers R0 , Q1 , . . . , Q` to the user.
2. The user applies Z over register Qi and sends back registers Q1 , . . . , Q` to the server.
(R,Qk )
3. The server applies Uak , for each k ∈ {1, . . . , `}, and sends to the user register R.
0
4. The user applies CNOT(R,R ) , applies Hr over register R, and then measures R in the computational
basis.
Figure 1: Quantum private information retrieval protocol.
We first show that in this protocol the user always outputs the correct element of the database. Observe
that, at the end of Step 2, the state is
1 i
|Φi = √ ∑ (−1)x·a |xiR |xiR0 |x · a1 iQ1 · · · |x · a` iQ` .
2r x∈Σ
At Step 4, just before the user performs the measurement, the state is |ai iR |0iR0 |0iQ1 · · · |0iQ` , and
measuring register R gives the element ai with probability 1. Let us now consider the user’s privacy. The
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 369–374 372
Q UANTUM P RIVATE I NFORMATION R ETRIEVAL WITH S UBLINEAR C OMMUNICATION C OMPLEXITY
only information about i that a server following the protocol can obtain is from registers R, Q1 , . . . , Q` of
the state |Φi. Since tracing out register R0 in |ΦihΦ| gives the density matrix
1
∑ |xiR |x · a1 iQ1 · · · |x · a` iQ` hx|R hx · a1 |Q1 · · · hx · a` |Q` ,
2r x∈Σ
the server obtains no information about the user’s input.
Remark As already mentioned, in this note we only consider the case where the server follows the
protocol. This assumption is used in the analysis of the protocol of Figure 1 in order to ensure that the
server prepares the state |ΦA i at Step 1. Note that if, instead of |ΦA i, the server prepared for example the
state
1
|Φ0A i := √ ∑ |xiR |0iR0 |x · a1 iQ1 · · · |x · a` iQ` ,
2r x∈Σ
then it would be able to recover the index i with probability one at Step 3.
Acknowledgements
The author is grateful to Takeshi Koshiba, Harumichi Nishimura, and Ronald de Wolf for helpful
discussions about this work. He also thanks the anonymous reviewers for very valuable comments and
suggestions.
References
[1] E THAN B ERNSTEIN AND U MESH VAZIRANI: Quantum complexity theory. SIAM J. Comput.,
26(5):1411–1473, 1997. Preliminary version in STOC’93. [doi:10.1137/S0097539796300921] 370
[2] B ENNY C HOR , O DED G OLDREICH , E YAL K USHILEVITZ , AND M ADHU S UDAN: Private
information retrieval. J. ACM, 45(6):965–981, 1998. Preliminary version in FOCS’95.
[doi:10.1145/293347.293350] 369, 370
[3] V ITTORIO G IOVANNETTI , S ETH L LOYD , AND L ORENZO M ACCONE: Quantum private queries.
Phys. Rev. Lett., 100:230502, Jun 2008. [doi:10.1103/PhysRevLett.100.230502] 371
[4] R AHUL JAIN , JAIKUMAR R ADHAKRISHNAN , AND P RANAB S EN: A property of quantum rela-
tive entropy with an application to privacy in quantum communication. J. ACM, 56(6):33, 2009.
Preliminary version in FOCS’02. [doi:10.1145/1568318.1568323] 371
[5] I ORDANIS K ERENIDIS AND RONALD DE W OLF: Exponential lower bound for 2-query locally
decodable codes via a quantum argument. J. Comput. System Sci., 69(3):395–420, 2004. Preliminary
version in STOC’03. [doi:10.1016/j.jcss.2004.04.007] 370, 371
[6] I ORDANIS K ERENIDIS AND RONALD DE W OLF: Quantum symmetrically-private information
retrieval. Inform. Process. Lett., 90(3):109–114, 2004. [doi:10.1016/j.ipl.2004.02.003] 371
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 369–374 373
F RANÇOIS L E G ALL
[7] H ARTMUT K LAUCK: Quantum and approximate privacy. Theory of Computing Systems, 37(1):221–
246, 2004. Preliminary version in STACS’02. [doi:10.1007/s00224-003-1113-7] 371
[8] A SHWIN NAYAK: Optimal lower bounds for quantum automata and random access codes. In Proc.
40th FOCS, pp. 369–377. IEEE Comp. Soc. Press, 1999. [doi:10.1109/SFFCS.1999.814608] 370
[9] M ICHAEL N IELSEN AND I SAAC C HUANG: Quantum Computation and Quantum Information.
Cambridge University Press, 2000. 371
AUTHOR
François Le Gall
Assistant professor
Department of Computer Science
The University of Tokyo
legall is s u-tokyo ac jp
http://www.francoislegall.com
ABOUT THE AUTHOR
F RANÇOIS L E G ALL received his Ph. D. from the University of Tokyo in 2006; his advisor
was Hiroshi Imai. His research interests include quantum computation, computational
complexity, and algorithms for algebraic problems (especially the group isomorphism
problem and matrix multiplication). On weekends or holidays, he enjoys going for a hike
around Tokyo with his wife.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 369–374 374