Quantum Random Access Codes for Boolean Func-
tions
João F. Doriguello
1,2
and Ashley Montanaro
2,3
1
Quantum Engineering Centre for Doctoral Training, University of Bristol, United Kingdom
2
School of Mathematics, University of Bristol, United Kingdom
3
Phasecraft Ltd.
An n
p
7→ m random access code (RAC) is an encoding of n bits into m bits such that
any initial bit can be recovered with probability at least p, while in a quantum RAC
(QRAC), the n bits are encoded into m qubits. Since its proposal, the idea of RACs
was generalized in many different ways, e.g. allowing the use of shared entanglement
(called entanglement-assisted random access code, or simply EARAC) or recovering
multiple bits instead of one. In this paper we generalize the idea of RACs to recovering
the value of a given Boolean function f on any subset of fixed size of the initial bits,
which we call f-random access codes. We study and give protocols for f -random access
codes with classical (f-RAC) and quantum (f-QRAC) encoding, together with many
different resources, e.g. private or shared randomness, shared entanglement (f-EARAC)
and Popescu-Rohrlich boxes (f -PRRAC). The success probability of our protocols is
characterized by the noise stability of the Boolean function f. Moreover, we give
an upper bound on the success probability of any f-QRAC with shared randomness
that matches its success probability up to a multiplicative constant (and f-RACs by
extension), meaning that quantum protocols can only achieve a limited advantage over
their classical counterparts.
1 Introduction
One of the possible origins of quantum computers’ power is the exponential size of the Hilbert
space: a n-qubit quantum state is a unit vector in a 2
n
dimensional complex vector space. On the
other hand, one of the fundamental results in quantum information theory – Holevo’s theorem [29]
– states that no more than n bits of classical information can be transmitted by n qubits without
entanglement. Nonetheless, interesting scenarios arise when allowing a small chance of transmitting
the wrong message or/and obtaining partial information at the expense of losing information about
the rest of the system. One of these scenarios is the concept of quantum random access codes
(QRACs), where a number of bits are encoded into a smaller number of qubits such that any
one of the initial bits can be recovered with some probability of success. A QRAC is normally
denoted by n
p
7→ m, meaning that n bits are encoded into m qubits such that any initial bit can
be recovered with probability at least p > 1/2 (greater than 1/2 since p = 1/2 can be achieved
by pure guessing), and a classical version, called simply random access code (RAC), is similarly
defined, with the encoding message being m bits. The idea of QRACs first appeared in a paper
by Stephen Wiesner [64] in 1983 under the name of conjugate coding, and was later rediscovered
by Ambainis et al. in 1999 [4].
Quantum random access codes found application in many different contexts, e.g. quantum
finite automata [4, 43], network coding [26, 27], quantum communication complexity [10, 22, 35],
locally decodable codes [8, 33, 34, 62], non-local games [42, 60], cryptography [47], quantum state
learning [1], device-independent dimension witnessing [2, 3, 63], self-testing measurements [19, 20],
João F. Doriguello: joaof.doriguello@gmail.com, http://joaodoriguello.com
Accepted in Quantum 2021-02-22, click title to verify. Published under CC-BY 4.0. 1
arXiv:2011.06535v4 [quant-ph] 4 Mar 2021
randomness expansion [38], studies of no-signaling resources [23], and characterization of quantum
correlations from information theory [49]. The 2 7→ 1 and 3 7→ 1 QRACs were first experimentally
demonstrated in [56]. See [21, 25, 42, 59, 61] for subsequent demonstrations.
In this paper we further generalize the idea of (quantum) random access codes to recovering
not just an initial bit, but the value of a fixed Boolean function on any subset of the initial bits
with fixed size. We call them f-random access codes. The case of the Parity function was already
considered in [8], and here we generalize to arbitrary Boolean functions f : {−1, 1}
k
→ {−1, 1}.
1.1 Related Work
An n
p
7→ m (Q)RAC is an encoding of n bits into m (qu)bits such that any initial bit can be
recovered with probability at least p. This probability is the worst case success probability over
all possible pairs (x, i) of input string x ∈ {−1, 1}
n
and recoverable bit i ∈ {1, . . . , n}. Many
different resources can be used during the encoding and decoding, e.g. private randomness (PR),
shared randomness (SR), shared entanglement, and even super-quantum correlations like Popescu-
Rohrlich boxes [50].
Regarding the classical RAC, Ambainis et al. [4] proved that there is no 2
p
7→ 1 RAC (and
2
m
p
7→ m RAC by extension) with PR and worst case success probability p > 1/2. On the other
hand, Ambainis et al. [5] showed that RACs with SR can achieve success probability p > 1/2.
Theorem 1 ([5, Equation (25)]). The optimal n
p
7→ 1 RAC with SR has success probability
p =
1
2
+
1
2
n
n − 1
b
n−1
2
c
=
1
2
+
1
√
2πn
− O
1
n
3/2
.
For a general number of encoded bits, Ambainis et al. [4] developed a RAC with PR using a
specific code from [14] which matches their classical lower bound m ≥ (1−H(p))n up to an additive
logarithmic term, where H(p) = −p log
2
p − (1 − p) log
2
(1 − p) is the binary entropy function.
Theorem 2 ([4, Theorem 2.2]). There is an n
p
7→ m RAC with PR and m ≤ (1 −H(p))n + 7 log
2
n
for any p >
1
2
.
As for QRACs, Ambainis et al. [4] showed the existence of a 2
p
7→ 1 QRAC with PR
1
and
p =
1
2
+
1
2
√
2
≈ 0.85, and the existence of a 3
p
7→ 1 QRAC with PR and p =
1
2
+
1
2
√
3
≈ 0.79 (the
second attributed to Chuang). Later Hayashi et al. [26] showed the impossibility of a 4
p
7→ 1 QRAC
(and 4
m
p
7→ m QRAC by extension) with PR and success probability p > 1/2. Similarly to the
classical case, Ambainis et al. [5] showed that QRACs can also benefit from SR.
Theorem 3 ([5, Theorem 6]). There is an n
p
7→ 1 QRAC with SR and
2
p =
1
2
+
r
2
3πn
+ O
1
n
3/2
.
The specific case of m = 2 encoding qubits was explored in [26, 31, 39]. For the general case of
m > 1, Iwama et al. [32] constructed an (4
m
−1)
p
7→ m QRAC with PR and p =
1
2
+
1
2(2
m
−1)
√
2
m
+1
(such construction also works for all n < 4
m
). On the other hand, Ambainis et al. [4] proved that
if an n
p
7→ m QRAC with PR and p > 1/2 exists, then m = Ω(n/ log n), which was later improved
to m ≥ (1 − H(p))n by Nayak [43], thus matching the same classical lower bound from [4].
The idea of decoding a function of the initial bits instead of a single bit was already considered
by Ben-Aroya, Regev and de Wolf [8] (who also considered recovering multiple bits rather than
1
Usually private randomness is already assumed in QRACs under the encoding onto density matrices.
2
Ambainis et al. [5] do not give the high order terms, but these can be calculated by following their procedure
together with [30, Equation 2.198].
Accepted in Quantum 2021-02-22, click title to verify. Published under CC-BY 4.0. 2
just one). More specifically, they defined an n
p
7→ m XOR
k
-QRAC, where n bits are encoded
into m qubits such that the parity of any k initial bits can be recovered with success probability
at least p.
3
Using their hypercontractive inequality for matrix-valued functions, they proved the
following upper bound on the success probability.
Theorem 4 ([8, Theorem 7]). For any η > 2 ln 2 there is a constant C
η
such that, for any n
p
7→ m
XOR
k
-QRAC with SR and k = o(n),
p ≤
1
2
+ C
η
ηm
n
k/2
. (1)
They conjectured that the factor η > 2 ln 2 can be dropped from the above bound, and thus
extended to m/n > 1/(2 ln 2) ≈ 0.72, although it might require a strengthening of their hypercon-
tractive inequality.
The use of shared entanglement in random access codes was first considered by Klauck [35, 36].
Here the encoding and decoding parties are allowed to use an arbitrary amount of shared entangled
states (note that shared entanglement can be used to obtain both private and shared randomness).
The figure of merit in this generalization is the relation between n, m and p, while the amount of
shared entanglement is not taken into account. Klauck [35, 36] considered an n
p
7→ m QRAC with
shared entanglement and, by its equivalence to the quantum one-way communication complexity
for the index function, proved the lower bound m ≥ (1 − H(p))n/2, similar to Nayak’s bound.
Later Pawłowski and Żukowski [48] coined the term entanglement-assisted random access code
(EARAC), which is a RAC with shared entanglement, and studied the case when m = 1, giving
protocols with better decoding probabilities compared to the usual n
p
7→ 1 QRAC with SR. Recently
Tănăsescu et al. [58] expanded the idea of n
p
7→ 1 EARACs to recovering an initial bit under a
specific request distribution.
Theorem 5 ([48] and [58, Corollary 2 and Theorem 5]). The optimal n
p
7→ 1 EARAC with SR has
success probability
p =
1
2
+
1
2
√
n
.
The idea of (Q)RAC was generalized in other ways, e.g. parity-oblivious [7, 13, 56] and mul-
tiparty [53] versions, encoding on d-valued qubits (qudits) [6, 12, 19, 39, 59], a wider range of
information retrieval tasks [18] and a connection to Popescu-Rohrlich boxes. It was shown [66]
that a Popescu-Rohrlich box can simulate a RAC by means of just one bit of communication,
while in [23] the converse was proven. An object called racbox [23] was defined, which is a box
that implements a RAC when supported with one bit of communication, and it was shown that a
non-signaling racbox is equivalent to a Popescu-Rohrlich box. A quantum version of a racbox was
later proposed in [24]. Finally, we mention that RACs were also studied within “theories” that vi-
olate the uncertainty relation for anti-commuting observables and present stronger-than-quantum
correlations [57].
1.2 Our Results
This paper focuses on generalizing the classical, quantum and entanglement-assisted random access
codes. Instead of recovering a single bit from the initial string x ∈ {−1, 1}
n
, we are interested
in evaluating a Boolean function f : {−1, 1}
k
→ {−1, 1} on any sequence of k bits from x. We
generically call them f-random access codes. Let S
k
n
= {(S
i
)
k
i=1
∈ {1, . . . , n}
k
| S
i
6= S
j
∀i, j}
be the set of sequences of different elements from {1, . . . , n} with length k and let x
S
∈ {−1, 1}
k
denote the substring of x ∈ {−1, 1}
n
specified by S ∈ S
k
n
. Alice gets x ∈ {−1, 1}
n
and she needs to
encode her data and send it to Bob, so that he can decode f(x
S
) for any S ∈ S
k
n
with probability
p > 1/2. Such problem was already considered by Sherstov in a two-way communication complexity
3
In their definition the success probability is the average over random k-subsets and random inputs, which, in
our context, is equivalent to using SR.
Accepted in Quantum 2021-02-22, click title to verify. Published under CC-BY 4.0. 3
setting [54] and later used in his pattern matrix method [55] in order to prove other communication
complexity lower bounds. Even though our results are expressed in a random access code language,
they can also be seen as in a one-way communication complexity setting. If two-way communication
is allowed, Bob can send the identity of his sequence to Alice with O(k log n) bits of communication,
whereas (as we will see) significantly more communication may be required in the one-way scenario.
In the following, Π will refer to a sample space with some probability distribution. As before,
PR and SR stand for private and shared randomness, respectively. Moreover, since we require
the success probability to always be greater than 1/2, given that one can always guess the correct
result with probability 1/2, from now on it will be convenient to use the bias ε of the prediction,
defined as ε = 2p − 1, instead of its success probability p.
We start with n
ε
7→ m f-RAC, the f -classical random access code on m bits with bias ε.
Definition 6. An n
ε
7→ m f -RAC with PR is an encoding map E : {−1, 1}
n
× Π
A
→ {−1, 1}
m
satisfying the following: for every S ∈ S
k
n
there is a decoding map D
S
: {−1, 1}
m
×Π
B
→ {−1, 1}
such that Pr
r
A
,r
B
[D
S
(E(x, r
A
), r
B
) = f(x
S
)] ≥
1
2
+
1
2
ε for all x ∈ {−1, 1}
n
.
Definition 7. An n
ε
7→ m f-RAC with SR is an encoding map E : {−1, 1}
n
× Π → {−1, 1}
m
satisfying the following: for every S ∈ S
k
n
there is a decoding map D
S
: {−1, 1}
m
× Π → {−1, 1}
such that Pr
r
[D
S
(E(x, r), r) = f(x
S
)] ≥
1
2
+
1
2
ε for all x ∈ {−1, 1}
n
.
We define n
ε
7→ m f-QRAC, the f -quantum random access code on m qubits with bias ε.
Definition 8. An n
ε
7→ m f-QRAC with PR is an encoding map E : {−1, 1}
n
→ C
2
m
×2
m
that
assigns an m-qubit density matrix to every x ∈ {−1, 1}
n
and satisfies the following: for every
S ∈ S
k
n
there is a POVM M
S
= {M
S
−1
, M
S
1
} such that Tr(M
S
f(x
S
)
· E(x)) ≥
1
2
+
1
2
ε for all
x ∈ {−1, 1}
n
.
Definition 9. An n
ε
7→ m f-QRAC with SR is an encoding map E : {−1, 1}
n
×Π → C
2
m
that as-
signs an m-qubit pure state to every x ∈ {−1, 1}
n
and satisfies the following: for every S ∈ S
k
n
there
is a set of POVMs {M
S
r
}
r∈Π
, with M
S
r
= {M
S
−1,r
, M
S
1,r
}, such that E
r
[E(x, r)
†
M
S
f(x
S
),r
E(x, r)] ≥
1
2
+
1
2
ε for all x ∈ {−1, 1}
n
.
Similarly, we define n
ε
7→ m f-EARAC, the f-entanglement-assisted random access code on m
bits with bias ε.
Definition 10. An n
ε
7→ m f-EARAC is an n
ε
7→ m f-RAC with SR where the encoding and
decoding parties share an unlimited amount of entangled quantum states.
Due to shared entanglement being a source of SR, we already include SR in f-EARACs. We note
that [48] focused on EARACs without SR.
Finally, we define n
ε
7→ m f-PRRAC, the f -Popescu-Rohrlich random access code on m bits
with bias ε. A Popescu-Rohrlich box [50] is a bipartite system shared by two parties with two
inputs x, y ∈ {0, 1} and two outputs a, b ∈ {0, 1} and is defined by the joint probability distribution
Pr[ab|xy] =
(
1
2
for a ⊕ b = xy,
0 otherwise.
Definition 11. An n
ε
7→ m f-PRRAC is an n
ε
7→ m f-RAC with SR where the encoding and
decoding parties share an unlimited amount of Popescu-Rohrlich boxes.
In Section 3 we devise encoding-decoding strategies for all the f-random access codes just
defined, thus deriving lower bounds on their biases given the encoding/decoding parameters n, m
and k. These f-random access codes are built based on previous ideas from [4, 5, 48]. The Boolean
function f : {−1, 1}
k
→ {−1, 1} that needs to be evaluated directly influences the final bias
and such influence in our results is captured by the single quantity called noise stability [9, 45].
Informally it is a measure of how resilient to noise a Boolean function is. Given a uniformly random
Accepted in Quantum 2021-02-22, click title to verify. Published under CC-BY 4.0. 4
input x ∈ {−1, 1}
n
, one might imagine a process that flips each bit of x independently with some
probability
1
2
−
1
2
q, where q ∈ [−1, 1], which leads to some final string y ∈ {−1, 1}
n
. The noise
stability Stab
q
[f] of f with parameter q is the correlation between f(x) and f (y) (see Section 2
for a formal definition).
Our positive results can be summarized by the following theorem.
Theorem 12. Let f : {−1, 1}
k
→ {−1, 1} be a Boolean function and Stab
q
[f] its noise stability
with parameter q.
(a) Let ` ∈ N. If m = Ω(` log n) and k = o(
√
`), there is an n
ε
7→ m f -RAC with PR and bias
ε ≥ (1 − o
n
(1)) Stab
q
[f] with q ≥
q
m
n
−
5 log
2
(n/`)
n/`
.
(b) If k = o(
√
m), there is an n
ε
7→ m f-RAC with SR and ε ≥ (1 −o
n
(1)) Stab
q
[f] with q ≥
p
m
2n
.
(c) If k = o(
√
m), there is an n
ε
7→ m f-QRAC with SR and ε ≥ (1 − o
n
(1)) Stab
q
[f] with
q ≥
q
8m
3πn
.
(d) If k = o(
√
m), there is an n
ε
7→ m f -EARAC with ε ≥ (1 − o
n
(1)) Stab
q
[f] and q =
p
m
n
.
(e) For any n ∈ N, there is an n
1
7→ 1 f -PRRAC.
Results (a), (b), (c) and (d) use an encoding scheme reminiscent of the concatenation idea
from [48, 49, 58] (and suggested to us by Ronald de Wolf). The underlying idea is to ran-
domly break the initial string x ∈ {−1, 1}
n
into different ‘blocks’ and encode them via a standard
RAC/QRAC/EARAC. Result (a) breaks x into ` blocks and employs the n/` 7→ m/` RAC from
Theorem 2 on every block, each with n/` elements, while in results (b)/(c)/(d) we employ the
n/m 7→ 1 RAC/QRAC/EARAC from Theorems 1/3/5 in order to encode m blocks, each with
n/m elements, into a single (qu)bit each, resulting in m encoded (qu)bits. With high probability
all the bits from the needed string x
S
∈ {−1, 1}
k
will be encoded into different blocks and therefore
can be decoded and f evaluated. The decoded string y ∈ {−1, 1}
k
can be viewed as a ‘noisy’ x
S
,
to which the noise stability framework can be applied. The bias of the base RAC/QRAC/EARAC
thus becomes the parameter q in the noise stability of the corresponding f-random access code.
As a quick remark, since we opted to lower-bound the parameters q in Theorem 12, in result (b)
q does not exactly equal the bias from Theorem 1. One could write, though, q ≈
q
2m
πn
.
Result (a) is our strongest bound, since it also applies to all other f -random access codes.
Moreover, there is some freedom in setting the number of blocks `, since the number of encoded
bits in Theorem 2 is not fixed to a single number (as opposed to Theorems 1, 3 and 5). The
result is a trade-off between the number of bits k of the Boolean function and the number of
encoded bits m. However, the number of encoded bits in result (a) is limited to m = Ω(log n), a
characteristic inherited from the RAC in Theorem 2. It is possible to go below this limit by using
SR, as demonstrated by results (b), (c) and (d).
The above results show that quantum resources offer a modest advantage over the classical
f-random access code. On the other hand, result (e) demonstrates that stronger-than-quantum
resources like Popescu-Rohrlich boxes can lead to extremely powerful f-random access codes.
This is a consequence of violating Information Causality [49], since one bit transfer allows the
access to any bit in a database via Popescu-Rohrlich boxes. From x ∈ {−1, 1}
n
a long bit-string
x
f
∈ {−1, 1}
t
, where t = |S
k
n
|, can be constructed with the values f (x
S
) for all S ∈ S
k
n
. All bits
from x
f
are readable with the aid of Popescu-Rohrlich boxes, with non-signaling constraining the
readout to just one bit. The protocol for f-PRRACs is taken from [49] and uses a pyramid of
Popescu-Rohrlich boxes and nests a van Dam’s protocol [16].
In Section 4 we prove an upper bound on the bias of any f-QRAC with SR (and f -RAC) using
the same method of the hypercontractive inequality for matrix-valued functions from [8].
Accepted in Quantum 2021-02-22, click title to verify. Published under CC-BY 4.0. 5
Theorem 13. Let f : {−1, 1}
k
→ {−1, 1} be a Boolean function. For any n
ε
7→ m f-QRAC with
SR and k = o(n) the following holds: for any η > 2 ln 2 there is a constant C
η
such that
ε ≤ C
η
k
X
`=0
L
1,`
(f)
ηm
n
`/2
, (2)
where L
1,`
(f) =
P
T ⊆[k]
|T |=`
b
f(T )
is the 1-norm of the `-th level of the Fourier transform of f.
One can see that the above result is a generalization of Theorem 4. Indeed, for Parity on k bits,
L
1,`
(XOR
k
) = 1 iff ` = k, and so Eq. (1) is recovered. The following corollary from Theorem 13
helps to compare the bias upper bound to the bias lower bounds from Theorem 12.
Corollary 14. Let f : {−1, 1}
k
→ {−1, 1} be a Boolean function. For any n
ε
7→ m f-QRAC with
SR and k = o(n) the following holds: for any η > 2 ln 2 there is a constant C
η
such that
ε ≤ C
η
2
deg(f)−1
Stab
q
[f],
where deg(f) = max{|S| :
b
f(S) 6= 0} is the degree of f and q =
p
ηm
n
.
Taking deg(f ) to be upper-bounded by a constant (for example, if k = O(1)), our bias upper
bound matches our bias lower bounds for f-RAC/QRAC with SR up to a global multiplicative
constant and a multiplicative constant
√
η in the parameter q. We conjecture that the parameter q
can be improved to
p
m
n
, which might require a stronger version of the hypercontractive inequality.
Other corollaries from Theorem 13 are derived in Section 4 and compared to our bias lower bounds.
Upper bound (2) does not apply to f-EARACs. Previously, it was known that for the special
case of standard EARACs (m = 1), the bias ε is upper-bounded by 1/
√
n (Theorem 5). This upper
bound can generalised to EARACs with m > 1 assuming an independence condition (Section 3.4).
The resulting bound is ε ≤
p
m/n. We view this as evidence that the bias lower bound for the
general case of f-EARACs given in Theorem 12 should actually be tight.
Regarding the quantity Stab
q
[f] itself, it can be nicely related to the Fourier coefficients of f
(see Theorem 17 in the next section). We briefly mention the noise stability for a few functions.
For Parity (XOR
k
), Stab
q
[XOR
k
] = q
k
, and, more generally, for any function χ
S
(x) =
Q
i∈S
x
i
,
Stab
q
[χ
S
] = q
|S|
. As for the Majority function (MAJ
k
), one can show that [46, Theorem 5.18]
2
π
arcsin q ≤ Stab
q
[MAJ
k
] ≤
2
π
arcsin q + O
1
√
1−q
2
√
k
. Other examples can be found in [41].
Moreover, a randomized algorithm for approximating the noise stability of monotone Boolean
functions up to relative error was proposed in [52].
In Section 3 we present protocols for all our f-random access codes, and in Section 4 we derive
an upper bound on the bias of f -QRACs with SR.
2 Preliminaries
We shall briefly revise some results from Boolean analysis that are going to be useful. For an
introduction to the analysis of Boolean functions, see O’Donnell’s book [46] or de Wolf’s paper [65].
In the following, we write [n] = {1, . . . , n} and S
n
is the set of all permutations of [n]. As before,
let S
k
n
= {(S
i
)
k
i=1
∈ [n]
k
| S
i
6= S
j
∀i, j} be the set of sequences of different elements from [n] with
length k and let x
S
∈ {−1, 1}
k
denote the substring of x ∈ {−1, 1}
n
specified by S ∈ S
k
n
.
The inner product h·, ·i on the vector space of all functions f : {−1, 1}
n
→ R is defined by
hf, gi =
1
2
n
X
x∈{−1,1}
n
f(x)g(x).
Every function f : {−1, 1}
n
→ R can be uniquely expressed as a multilinear polynomial, its Fourier
expansion, as
f(x) =
X
S⊆[n]
b
f(S)χ
S
(x),
Accepted in Quantum 2021-02-22, click title to verify. Published under CC-BY 4.0. 6
where, for S ⊆ [n], χ
S
: {−1, 1}
n
→ {−1, 1} is defined by
χ
S
(x) =
Y
i∈S
x
i
.
The real number
b
f(S) is called the Fourier coefficient of f on S and is given by
b
f(S) = hf, χ
S
i =
1
2
n
X
x∈{−1,1}
n
f(x)χ
S
(x).
An important and useful concept for Boolean functions is noise stability. As previously men-
tioned, it is a measure of how resilient to noise a Boolean function is, and is defined from the
concept of q-correlated pairs of random strings given below.
Definition 15 ([46, Definitions 2.40 and 2.41]). Let q ∈ [−1, 1]. For fixed x ∈ {−1, 1}
n
we write
y ∼ N
q
(x) to denote that the random string y is drawn as follows: for each i ∈ [n] independently,
y
i
=
(
x
i
with probability
1
2
+
1
2
q,
−x
i
with probability
1
2
−
1
2
q.
We say that y is q-correlated to x. If x ∼ {−1, 1}
n
is drawn uniformly at random and then
y ∼ N
q
(x), we say that (x, y) is a q-correlated pair of random strings.
Given these definitions, we can formally define the concept of noise stability, which measures
the correlation between f(x) and f(y) when (x, y) is a q-correlated pair.
Definition 16 ([46, Definition 2.42]). For f : {−1, 1}
n
→ R and q ∈ [−1, 1], the noise stability of
f at q is
Stab
q
[f] = E
(x,y)
q -correlated
[f(x)f (y)] .
The noise stability of f is nicely related to f’s Fourier coefficients as stated in the following
theorem.
Theorem 17 ([46, Theorem 2.49]). For f : {−1, 1}
n
→ R and q ∈ [−1, 1],
Stab
q
[f] =
n
X
k=0
q
k
W
k
[f],
where W
k
[f] =
P
S⊆[n]
|S|=k
b
f(S)
2
is the Fourier weight of f at degree k.
The above result makes it clear that Stab
q
[f] is an increasing function of q for q ≥ 0.
Theorem 17 is obtained from one of the most important operators in analysis of Boolean
functions: the noise operator T
q
.
Definition 18 ([46, Definition 2.46]). For q ∈ [−1, 1], the noise operator with parameter q is the
linear operator T
q
on functions f : {−1, 1}
n
→ R defined by
T
q
f(x) = E
y∼N
q
(x)
[f(y)].
Proposition 19 ([46, Proposition 2.47]). For f : {−1, 1}
n
→ R, the Fourier expansion of T
q
f is
T
q
f =
X
S⊆[n]
q
|S|
b
f(S)χ
S
.
Accepted in Quantum 2021-02-22, click title to verify. Published under CC-BY 4.0. 7
It is not hard to prove from the above results that Stab
q
[f] = hf, T
q
fi.
Some of the above concepts can be generalized to matrix-valued functions. The Fourier trans-
form
b
f of a matrix-valued function f : {−1, 1}
n
→ C
m×m
is defined similarly as for scalar functions:
it is the function
b
f : {−1, 1}
n
→ C
m×m
defined by
b
f(S) =
1
2
n
X
x∈{−1,1}
n
f(x)χ
S
(x).
Here the Fourier coefficients
b
f(S) are also m × m complex matrices. Moreover, given A ∈ C
m×m
with singular values σ
1
, . . . , σ
m
, its trace norm is defined as kAk
tr
= Tr |A| =
P
m
i=1
σ
i
.
We shall make use of the following result from Ben-Aroya, Regev and de Wolf [8], which stems
from their hypercontractive inequality for matrix-valued functions.
Theorem 20 ([8, Lemma 6]). For every f : {−1, 1}
n
→ C
2
m
×2
m
and δ ∈ [0, 1],
X
S⊆[n]
δ
|S|
k
b
f(S)k
2
tr
≤ 2
2δm
.
Finally, H : [0, 1] → [0, 1] given by H(p) = −p log
2
p − (1 −p) log
2
(1 − p) is the binary entropy
function. The following bounds hold.
Theorem 21 ([11, Theorem 2.2]). ∀p ∈ [0, 1], 1 − 4
p −
1
2
2
≤ H(p) ≤ 1 −
2
ln 2
p −
1
2
2
.
3 Bias Lower Bounds
3.1 f-RAC with PR
We start by studying the f-RAC with PR. The following result is based on Ambainis et al. [4] and
uses a procedure reminiscent of the concatenation idea from [48, 49, 58]: the initial string is broken
in blocks, which in turn are encoded using the code from [14]. First we state a slightly modified
version of Newman’s Theorem [44] (see also [37, Theorem 3.14] and [51, Theorem 3.5]) which is
going to be useful to us.
Theorem 22 ([44]). Let E(x, r) be an event depending on x ∈ {−1, 1}
n
×{−1, 1}
n
and r ∈ R such
that
Pr
r∼R
[E(x, r)] ≥ p
for all x ∈ {−1, 1}
n
× {−1, 1}
n
, with p ∈ (0, 1]. Let δ ∈ (0, p]. Then there is R
0
⊆ R with size at
most n/δ
2
such that
Pr
r∼R
0
[E(x, r)] ≥ p − δ
holds for all x ∈ {−1, 1}
n
× {−1, 1}
n
.
Theorem 23. Let ` ∈ N, `|n, m = Ω(` log n) and k = o(
√
`). Let f : {−1, 1}
k
→ {−1, 1} be
a Boolean function. For sufficiently large n and `, there is an n
ε
7→ m f-RAC with PR and bias
ε ≥ (1 − o
n
(1)) Stab
q
[f] with
q ≥
s
m
n
−
5 log
2
(n/`)
n/`
.
Proof. Consider a code C ⊆ {−1, 1}
n
such that, for every x ∈ {−1, 1}
n
, there is a y ∈ C within
Hamming distance (1 −p −
1
n
)n, with p > 1/2 (the extra 1/n term will be used to counterbalance
Accepted in Quantum 2021-02-22, click title to verify. Published under CC-BY 4.0. 8
the decrease in probability from Newman’s theorem). It is known [14] that there is such a code C
of size
log
2
|C| = (1 − H(p + 1/n)) n + 2 log
2
n ≤ (1 − H(p)) n + 4 log
2
n.
Let C(x) denote the closest codeword to x. Hence at least (p + 1/n)n out of n bits of C(x) are the
same as x, and the probability over a uniformly random i that x
i
= C(x)
i
is at least p + 1/n.
Let ` ∈ N such that ` divides n. Our protocol involves breaking up x ∈ {−1, 1}
n
into ` parts
and encoding each part with the above code C ⊆ {−1, 1}
n/`
. Define the map
C
(`)
(x) = C(x
1
. . . x
n/`
)C(x
n/`+1
. . . x
2n/`
) . . . C(x
(`−1)n/`+1
. . . x
n
)
that applies C to the first ` bits of x, and to next ` bits of x and so on. Hence the probability that
x
i
= C
(`)
(x)
i
over a uniformly random i is at least p+`/n. In order to consider this probability for
every bit instead of just an average over all bits, we employ the following randomization process.
Let r ∈ {−1, 1}
n
and π ∈ S
n
, both taken uniformly at random. Given x ∈ {−1, 1}
n
, denote
π(x) = x
π(1)
x
π(2)
. . . x
π(n)
. We define the encoding C
(`)
π,r
(x) = π
−1
(C
(`)
(π(x · r))) · r, where x · r
denotes the bit-wise product of x and r. Let E
S
be the event that all indices in S ∈ S
k
n
are encoded
in different codes C, i.e., in different blocks from C
(`)
. There are ` blocks, each with n/` elements.
The probability that k specific elements fall into k different blocks is
Pr
S∼S
k
n
[E
S
] =
n
`
k
`
k
n
k
=
k−1
Y
j=1
1 −
j
`
1 −
j
n
≥
k−1
Y
j=1
1 −
j
`
(a)
≥ 1 −
k−1
X
j=1
j
`
= 1 −
k(k − 1)
2`
, (3)
where inequality (a) can easily be proven by induction or the union bound.
We shall first present a protocol using shared randomness, and at the end we shall transform it
into a protocol with private randomness by using Newman’s theorem. The protocol is the following.
Select r ∈ {−1, 1}
n
and π ∈ S
n
uniformly at random. Encode x as C
(`)
π,r
(x). To decode f(x
S
), first
we check if all the indices of S were encoded into different blocks. If no, the value for f(x
S
) is
drawn uniformly at random. If yes, just consider C
(`)
π,r
(x)
S
and evaluate f(C
(`)
π,r
(x)
S
). Conditioned
on the event E
S
happening, the probability that x
S
i
= C
(`)
(x)
S
i
is at least p + `/n independently
for all i ∈ [k], meaning that
Pr
π,r
[f(x
S
) = f(C
(`)
π,r
(x)
S
)|E
S
] ≥ Pr
(x,y)
(q+
2`
n
)-correlated
[f(x) = f (y)] =
1
2
+
1
2
Stab
q+
2`
n
[f],
where q := 2p − 1, and the inequality follows from monotonicity of the noise stability of f. With
these considerations, the success probability of the protocol is
Pr
π,r
[f(x
S
) = f(C
(`)
π,r
(x)
S
)] >
1
2
k(k − 1)
2`
+
1 −
k(k − 1)
2`
1
2
+
1
2
Stab
q+
2`
n
[f]
≥
1
2
+
1
2
1 −
k(k − 1)
2`
Stab
q
[f] + Stab
2`
n
[f]
=
1
2
+
1
2
(1 − o
n
(1))
Stab
q
[f] + Stab
2`
n
[f]
,
where we used that k = o(
√
`).
We now transform the shared randomness into private randomness. By Newman’s theorem
(Theorem 22) there is a small set of permutation-string pairs (note that Alice’s input is size n bits
and Bob’s input is at most n bits) with size
t ≤
4n
(1 − o
n
(1)) Stab
2`
n
[f]
2
≤
n
2k+1
(1 − o
n
(1))2
2k−2
`
2k
(we have used that Stab
a
[f] ≥ a
k
) such that f (x
S
) = f(C
(`)
π,r
(x)
S
) continues to hold with probabil-
ity at least
1
2
+
1
2
(1−o
n
(1)) Stab
q
[f] if π, r are chosen uniformly at random from this set. Hence the
Accepted in Quantum 2021-02-22, click title to verify. Published under CC-BY 4.0. 9
randomization can be encoded together with x at the cost of a small overhead. The final protocol
chooses j ∈ [t] uniformly at random, encodes x as C
(`)
π
j
,r
j
(x)
S
and then proceeds like the protocol
with shared randomness. Fix m = log
2
(t|C
(`)
|). The result follows by using the first inequality
from Theorem 21 to observe that
m ≤
1 − H(p)
n + 4` log
2
n
`
+ log
2
n
2k+1
(1 − o
n
(1))2
2k−2
`
2k
≤ q
2
n + 4(1 + o
`
(1))` log
2
n
`
=⇒ 2p − 1 ≥
s
m
n
−
4(1 + o
`
(1)) log
2
(n/`)
n/`
for sufficiently large n, where we used k = o(
√
`) again.
Remark. The parameter ` in Theorem 23 controls the number of encoding blocks in the protocol.
By tweaking it, we can adjust the range of m and k, e.g. if ` = Θ(log n), then m = Ω(log
2
n) and
k = o(
√
log n). If ` = Θ(
√
n), then m = Ω(
√
n log n) and k = o(n
1/4
).
In the protocol from Theorem 23 we broke the initial string into ` different blocks and used `
different copies of C. This was done in order to guarantee the independence of the C(x)
S
i
’s and
hence analyse the influence of the code C on the function f. Interestingly enough, for the special
case of the Parity function this is not required and a single copy of C can be used.
Theorem 24. Let XOR
k
: {−1, 1}
k
→ {−1, 1} be the Parity function and let m = Ω(k log n).
There is an n
ε
7→ m XOR
k
-RAC with PR and bias
ε ≥
1
n
k
K
k,n
n
2
−
n
2
r
m
n
−
7k log
2
n
n
!
, (4)
where K
k,n
(x) =
P
k
j=0
(−1)
j
x
j
n−x
k−j
is the Krawtchouk polynomial.
Proof. Consider the encoding C
π,r
(x) = π
−1
(C(π(x · r))) · r, where C ⊆ {−1, 1}
n
is the code
described in Theorem 23. Let δn be the Hamming distance between x and C(x), with δ ≤ 1−p−1/n
by the properties of C. Then
Pr
S∼S
k
n
"
k
Y
i=1
x
S
i
=
k
Y
i=1
C(x)
S
i
#
=
b
k
2
c
X
`=0
(1−δ)n
k−2`
δn
2`
n
k
=
1
2
+
1
2
K
k,n
(δn)
n
k
≥
1
2
+
1
2
K
k,n
((1 − p)n)
n
k
+
1
n
k
,
where we used
P
k
`=0
(1−δ)n
k−`
δn
`
=
n
k
on the second equality and K
k,n
(δn) − K
k,n
(δn + 1) = 2
on the final inequality, which can be obtained via the recurrence relation K
k,n
(x) −K
k,n
(x −1) =
K
k−1,n
(x) − K
k−1,n
(x − 1) and K
1,n
(x) = n − 2x (see e.g. [15]).
By Newman’s theorem (Theorem 22) there is a small set of permutation-string pairs with size
t = n
n
k
2
such that
Q
k
i=1
x
S
i
=
Q
k
i=1
C(x)
S
i
continues to hold with bias at least K
k,n
((1−p)n)/
n
k
for any x and S if π, r are chosen uniformly at random from this set.
Our protocol is the following. Select j ∈ [t] uniformly at random. Encode x as C
π
j
,r
j
(x). To
decode
Q
k
i=1
x
S
i
, just consider C
π
j
,r
j
(x)
S
and evaluate
Q
k
i=1
C
π
j
,r
j
(x)
S
i
. Now fix m = log
2
(t|C|).
The result follows by using the first inequality from Theorem 21 to observe that
m ≤
1 − H(p)
n + 5 log
2
n + 2 log
2
n
k
=⇒ 1 − p ≤
1
2
−
1
2
r
m
n
−
7k log
2
n
n
.
Remark. Since K
1,n
(x) = n − 2x, we note that, for k = 1, Eq. (4) reduces to ε ≥
q
m
n
−
7 log
2
n
n
,
which is the result from Ambainis et al. [4] (see Theorem 2).
Remark. If k = O(1), then the Krawtchouk polynomial has the asymptotic limit as n → ∞ of
K
k,n
(x) ∼
2
k
n
k
k!
1
2
−
x
n
k
[17, Eq. (29)], thus the bias from Theorem 24 has the asymptotic limit
ε ∼
n
k
k!
n
k
m
n
−
7k log
2
n
n
k/2
≥
m
n
−
7k log
2
n
n
k/2
.
Accepted in Quantum 2021-02-22, click title to verify. Published under CC-BY 4.0. 10
Note that this result is very similar to the one that would follow from Theorem 23, but slightly
tighter (without the ` parameter and the multiplicative constant 1 − o
n
(1)).
3.2 f-RAC with SR
There is a lower limit of m = Ω(log n) on the number of encoded bits in Theorem 23. It is possible
to go below this limit by using SR: the blocks are now encoded via the n
ε
7→ 1 RAC with SR from
Theorem 1 instead of the code C.
Theorem 25. Let m|n and k = o(
√
m). Let f : {−1, 1}
k
→ {−1, 1} be a Boolean function. There
is an n
ε
7→ m f -RAC with SR and bias ε ≥ (1 − o
n
(1)) Stab
q
[f] with
q =
2
2
n/m
n/m − 1
b
n/m−1
2
c
≥
(
q
2m
πn
− O
1
(n/m)
3/2
,
p
m
2n
.
Proof. Consider the RAC with SR from Theorem 1. Our protocol is the following. For the encoding
of x ∈ {−1, 1}
n
, its n bits are randomly divided into m sets T
1
, . . . , T
m
, each with n/m elements.
Each set is encoded into 1 bit with the n/m
7→ 1 RAC, and the encoded string is E(x) ∈ {−1, 1}
m
.
For decoding, one checks with the help of SR if all the k indices in S were encoded into different
sets. If no, the value for f(x
S
) is drawn uniformly at random. If yes, let D
i
: {−1, 1} → {−1, 1}
be the decoding function for set T
i
, which corresponds to bit E(x)
i
. Then z
`
i
:= D
`
i
(E(x)
`
i
) is
the decoded x
S
i
, where, for all i ∈ [k], `
i
∈ [m] is such that S
i
∈ T
`
i
.
4
Write z
T
= z
`
1
. . . z
`
k
. We
output f (z
T
) for f(x
S
).
Let E
S
be the event that all indices in S ∈ S
k
n
are encoded in different sets. Similarly to Eq. (3),
Pr
S∼S
k
n
[E
S
] ≥ 1 −
k(k − 1)
2m
.
The bias of correctly recovering any of the n/m encoded bits is q =
2
2
n/m
n/m−1
b
n/m−1
2
c
by Theorem 1.
Conditioning on E
S
happening, we see that x
S
and y
T
are q-correlated according to Definition 15.
Therefore
Pr
T
1
,...,T
m
[f(x
S
) = f(z
T
)|E
S
] = Pr
(x,y)
q-correlated
[f(x) = f (y)] =
1
2
+
1
2
Stab
q
[f],
where we used an input randomization via SR. With these considerations, the success probability
of the protocol is
Pr
T
1
,...,T
m
[f(x
S
) = f(z
T
)] ≥
1
2
k(k − 1)
2m
+
1 −
k(k − 1)
2m
1
2
+
1
2
Stab
q
[f]
=
1
2
+
1
2
1 −
k(k − 1)
2m
Stab
q
[f]
=
1
2
+
1
2
(1 − o
n
(1)) Stab
q
[f],
using that k = o(
√
m), from where the result follows by noticing that
q =
2
2
n/m
n/m − 1
b
n/m−1
2
c
≥
(
q
2m
πn
− O
1
(n/m)
3/2
,
p
m
2n
,
with n! =
√
2πn(n/e)
n
(1 + O(1/n)) and
2n
n
≥ 2
2n
/(2
√
n) [40, Chapter 10, Lemma 7].
4
The decoding map of the RAC from Theorem 1 (see [5, Theorem 2]) is just the identity map, so z
`
i
= E(x)
`
i
.
Accepted in Quantum 2021-02-22, click title to verify. Published under CC-BY 4.0. 11
Remark. It is possible to use Newman’s theorem in the above theorem in order to transform SR into
PR, but then Ω(log n) encoding bits would need to be used to encode the randomization procedure,
thus leading to m = Ω(log n). Moreover, the final f-RAC would have worse bias compared to the
one from Theorem 23.
Remark. The requirement m|n can be dropped by adding extra bits into x ∈ {−1, 1}
n
until m|n
0
,
where n
0
is the final number of bits.
Remark. For m = n/2 or m = n/3, we have
2
2
n/m
n/m−1
b
n/m−1
2
c
=
1
2
, so the resulting biases have
q
m=n/2
= q
m=n/3
= 1/2. Also, by using induction,
2
2
n
n−1
b
n−1
2
c
≤
1
2
for any n ≥ 2.
3.3 f-QRAC
Exactly the same procedure from Theorem 25 holds for f-QRACs if we replace the n/m 7→ 1 RAC
from Theorem 17 with the n/m 7→ 1 QRAC from Theorem 3 when encoding the sets T
1
, . . . , T
m
.
Theorem 26. Let m|n and k = o(
√
m). Let f : {−1, 1}
k
→ {−1, 1} be a Boolean function. There
is an n
ε
7→ m f -QRAC with SR and bias ε ≥ (1 − o
n
(1)) Stab
q
[f] with
q =
r
8m
3πn
+ O
1
(n/m)
3/2
.
Proof. Replace the n/m 7→ 1 RAC in the proof of Theorem 25 with the n/m
7→ 1 QRAC from
Theorem 3 with bias =
q
8m
3πn
+ O
1
(n/m)
3/2
.
Remark. If m = n/2 or m = n/3, the usual (and optimal) 2
1/
√
2
7−→ 1 QRAC or 3
1/
√
3
7−→ 1 QRAC with
PR can be used, respectively. The resulting biases have q
m=n/2
= 1/
√
2 and q
m=n/3
= 1/
√
3.
3.4 f-EARAC
The same protocol can also be used for f-EARACs, now with the n/m 7→ 1 EARAC from Theo-
rem 5.
Theorem 27. Let m|n and k = o(
√
m). Let f : {−1, 1}
k
→ {−1, 1} be a Boolean function. There
is an n
ε
7→ m f -EARAC with bias ε ≥ (1 − o
n
(1)) Stab
q
[f] and
q =
r
m
n
.
Proof. Replace the n/m 7→ 1 RAC in the proof of Theorem 25 with the n/m
7→ 1 EARAC from
Theorem 5 with bias =
p
m/n.
Remark. We could also define an entanglement-assisted f-QRAC (f -EAQRAC) similarly to Def-
inition 10, i.e., as an f-QRAC with SR where both parties share an unlimited amount of entan-
glement. Due to super-dense coding and teleportation, an n
ε
7→ m f-EAQRAC is equivalent to
an n
ε
7→ 2m f-EARAC, meaning that there is an n
ε
7→ m f-EAQRAC with k = o(
√
m) and bias
ε ≥ (1 − o
n
(1)) Stab
q
[f] with q =
q
2m
n
.
If f : {−1, 1} → {−1, 1} is f(x) = x, i.e., when considering the usual n 7→ m EARAC, the
above result tells us that the success probability is just
p =
1
2
+
1
2
r
m
n
. (5)
Moreover, we note that the n 7→ m EARAC is formed by a grouping of n/m 7→ 1 EARACs, such
that the m outcomes, i.e., the bits of the encoding message E(x) ∈ {−1, 1}
m
, are all independent
of each other. More precisely, for each i ∈ [n], there is a unique j ∈ [m] such that Pr[x
i
|E(x)] =
Accepted in Quantum 2021-02-22, click title to verify. Published under CC-BY 4.0. 12
Pr[x
i
|E(x)
j
]. Under this assumption, we can prove that Eq. (5) is optimal by the optimality of its
parts. Consider breaking the initial string x ∈ {−1, 1}
n
into m blocks, the i-th block containing
r
i
elements. Then the success probability of the resulting n 7→ m EARAC is
m
X
i=1
r
i
n
1
2
+
1
2
√
r
i
=
1
2
+
1
2n
m
X
i=1
√
r
i
,
which is maximized by taking r
i
= n/m for all i ∈ [m]. Since the n/m 7→ 1 EARACs are optimal
by Theorem 5, so is Eq. (5) (under the assumption that the n 7→ m EARAC is formed by m
independent EARACs on 1 encoding bit).
We can use Theorem 17 to obtain the following Corollary from Theorems 23, 25, 26 and 27.
Corollary 28. Let f : {−1, 1}
k
→ {−1, 1} be a Boolean function with pure high degree h =
min{|S| :
b
f(S) 6= 0}. Let W
j
[f] =
P
S⊆[k]
|S|=j
b
f(S)
2
.
(a) Let ` ∈ N, m = Ω(` log n) and k = o(
√
`). There is an n
ε
7→ m f -RAC with PR and bias
ε ≥ (1 − o
n
(1))W
h
[f]
m
n
−
5 log
2
(n/`)
n/`
h /2
.
(b) Let k = o(
√
m). There is an n
ε
7→ m f -RAC with SR and bias ε ≥ (1 − o
n
(1))W
h
[f]
m
2n
h /2
.
(c) Let k = o(
√
m). There is an n
ε
7→ m f-QRAC with SR and bias ε ≥ (1−o
n
(1))W
h
[f]
8m
3πn
h /2
.
(d) Let k = o(
√
m). There is an n
ε
7→ m f -EARAC with bias ε ≥ (1 − o
n
(1))W
h
[f]
m
n
h /2
.
3.5 f-PRRAC
We now present a protocol for the f-PRRAC, based on reducing the problem to the standard
random access code setting, and then using a protocol defined in [49]. This protocol was used to
show the violation of information causality by means of a pyramid of Popescu-Rohrlich boxes and
nesting van Dam’s protocol [16], which allows us to decode the value of f(x
S
) for any S ∈ S
k
n
with
just one encoded bit. This procedure of pyramiding and nesting was also used in the context of
EARACs in [48, 58] under the name of concatenation.
Theorem 29. Let f : {−1, 1}
k
→ {−1, 1} be a Boolean function. For any n ∈ N, there is an
n
1
7→ 1 f -PRRAC.
Proof. To ease the notation, we shall use {0, 1} instead of {−1, 1} during the proof. We shall
also name the encoding and decoding parties Alice and Bob, respectively, and refer to a Popescu-
Rohrlich box as PR-box. Let
5
t := |S
k
n
| = k!
n
k
and define the string a ∈ {0, 1}
t
as a
S
:= f(x
S
),
where S
k
n
is arranged in lexicographic order.
6
Bob is interested in bit a
S
, whose index position
can be described by a t-bit string b =
P
t−1
i=0
b
i
2
i
, i.e., the considered function is g
t
(a, b) := a
b
.
The remainder of the argument is the same as the protocol of [49], but we include the details for
completeness. For t = 1 we have that
g
t
((a
0
, a
1
), b
0
) = a
0
⊕ b
0
(a
0
⊕ a
1
).
Alice inputs a
0
⊕a
1
into a PR-box, while Bob inputs b
0
. Alice obtains the output A and sends the
message y = a
0
⊕A to Bob, who can obtain y ⊕B = a
b
using his output B, since, by the PR-box
property, A ⊕ B = b
0
(a
0
⊕ a
1
).
For t > 1, write a = a
0
a
00
, where a
0
= a
0
. . . a
t/2−1
∈ {0, 1}
t/2
and a
00
= a
t/2
. . . a
t−1
∈ {0, 1}
t/2
.
Then one can show that
g
t
(a, b) = g
t−1
(a
0
, b
0
) ⊕ b
t−1
(g
t−1
(a
0
, b
0
) ⊕ g
t−1
(a
00
, b
0
)) ,
5
If f is symmetric, the size t can be decreased to
n
k
by ignoring all the redundant permutations of the k-sets.
6
Here we use a
S
to denote a single bit of a, whereas x
S
denotes a subsequence of x.
Accepted in Quantum 2021-02-22, click title to verify. Published under CC-BY 4.0. 13
where b
0
= b
0
. . . b
t−2
∈ {0, 1}
t−1
. Therefore we can construct a recursive protocol in t, which will
encompass all values of n. The protocol uses a pyramid of 2
t
−1 Popescu-Rohrlich boxes placed on
t levels. The case t = 1 was explained above. For t > 1, Alice and Bob use the protocol on inputs
(a
0
, b
0
) and (a
00
, b
0
), which involves 2
t/2
−1 PR-boxes in each one. Alice’s outputs of each protocol
are y
0
and y
00
, which she inputs into the last PR-box, similarly to the case t = 1, as y
0
⊕y
00
, while
Bob inputs b
t−1
. Given Alice’s final output A, she sends y = y
0
⊕ A to Bob, who uses his output
B
t−1
to obtain y
0
⊕ b
t−1
(y
0
⊕ y
00
). If b
t−1
= 0, he gets y
0
, otherwise, if b
t−1
= 1, he gets y
00
. With
these, he can recursively go up the pyramid based on the protocol for t − 1 bits, which tells him
which boxes to read. Looking at the binary decomposition of b, Bob goes (t − r) times to the left
bit, and r times to the right bit, where r =
P
t−1
i=0
b
i
. His final output will be y ⊕ B
0
⊕ ··· ⊕ B
t−1
,
where B
j
is the output for the PR-box that Bob uses at level j. Bob will only need the outputs of
t PR-boxes, while Alice uses 2
t
− 1 PR-boxes in total.
4 Bias Upper Bounds
In order to prove an upper bound on the bias of any n
ε
7→ m f-QRAC with SR, we shall use
the following equivalent version of Definition 9, which comes from input randomization, i.e., from
considering the average success probability over the inputs, and from the following fact.
Fact 30 ([28]). Let ρ be an unknown state picked from the set {ρ
0
, ρ
1
} with probability p and 1−p,
respectively. The optimal success probability of predicting which state it is by a POVM is
1
2
+
1
2
kpρ
0
− (1 − p)ρ
1
k
tr
.
Definition 31. Let f : {−1, 1}
k
→ {−1, 1} be a Boolean function. An n
ε
7→ m f -QRAC with SR is
a map ρ : {−1, 1}
n
→ C
2
m
×2
m
that assigns an m-qubit density matrix ρ(x) to every x ∈ {−1, 1}
n
and has the property that
E
S∼S
k
n
1
2
n
X
x∈{−1,1}
n
f(x
S
)ρ(x)
tr
≥ ε.
Theorem 32. Let f : {−1, 1}
k
→ {−1, 1} be a Boolean function. For any n
ε
7→ m f-QRAC with
SR and k = o(n) the following holds: for any η > 2 ln 2 there is a constant C
η
such that
ε ≤ C
η
k
X
`=0
L
1,`
(f)
ηm
n
`/2
, (6)
where L
1,`
(f) =
P
T ⊆[k]
|T |=`
b
f(T )
is the 1-norm of the `-th level of the Fourier transform of f.
Proof. We start by writing the following.
1
2
n
X
x∈{−1,1}
n
f(x
S
)ρ(x)
tr
=
1
2
n
X
V ⊆[n]
X
T ⊆[k]
b
f(T )bρ(V )
X
x∈{−1,1}
n
χ
V
(x)χ
T
(x
S
)
tr
=
X
T ⊆[k]
b
f(T )bρ(S
T
)
tr
≤
X
T ⊆[k]
b
f(T )
kbρ(S
T
)k
tr
,
where S
T
= {S
i
| i ∈ T }. Then
ε ≤
k
X
`=0
X
T ⊆[k]
|T |=`
b
f(T )
E
S∼S
k
n
kbρ(S
T
)k
tr
,
Accepted in Quantum 2021-02-22, click title to verify. Published under CC-BY 4.0. 14
but, for a given T ⊆ [k] with |T | = `,
E
S∼S
k
n
kbρ(S
T
)k
tr
1
k!
n
k
X
S∈S
k
n
kbρ(S
T
)k
tr
=
`!(k − `)!
k!
n
k
n − `
k − `
X
S∈
(
[n]
`
)
kbρ(S)k
tr
= E
S∼
(
[n]
`
)
kbρ(S)k
tr
,
and thus, using Jensen’s inequality,
ε ≤
k
X
`=0
X
T ⊆[k]
|T |=`
b
f(T )
E
S∼
(
[n]
`
)
kbρ(S)k
tr
≤
k
X
`=0
L
1,`
(f)
r
E
S∼
(
[n]
`
)
kbρ(S)k
2
tr
.
We now use Theorem 20 with δ =
`
(2 ln 2)m
, taking only the sum on S with |S| = `,
E
S∼
(
[n]
`
)
kbρ(S)k
2
tr
≤ 2
2δm
δ
−`
n
`
−1
=
(2e ln 2)m
`
`
n
`
−1
,
to finally obtain
ε ≤
k
X
`=0
n
`
−1/2
L
1,`
(f)
(2e ln 2)m
`
`/2
.
From here we can use Stirling’s approximation n! = Θ(
√
n(n/e)
n
) to obtain
n
`
= Θ
r
n
`(n − `)
n
`
`
1 +
`
n − `
n−`
!
.
We use the fact that for large enough n/` we have (1 + `/(n − `))
(n−`)/`
> (2e ln 2)/η, where
η > 2 ln 2, and that the factor
p
n/`(n − `) ≥
p
1/k can be absorbed by this approximation. Then
there is a constant C
η
such that Eq. (6) holds.
A few different bounds can be obtained from the above theorem, some with a clearer meaning.
Corollary 33. Let f : {−1, 1}
k
→ {−1, 1} be a Boolean function. Let r ∈ [0, 1]. For any n
ε
7→ m
f-QRAC with SR and k = o(n) the following holds: for any η > 2 ln 2 there is a constant C
η
such
that
ε ≤
C
η
v
u
u
t
Stab
q
2r
[f]
X
S∈supp(
b
f)
q
2(1−r)|S|
, (7a)
C
η
ˆ
kf
ˆ
k
1
ηm
n
h /2
, (7b)
C
η
2
deg(f)−1
Stab
q
[f], (7c)
where q =
p
ηm
n
, supp(
b
f) = {S ⊆ [k] |
b
f(S) 6= 0} is the support of f, h = min{|S| :
b
f(S) 6= 0} is the
pure high degree of f, deg(f) = max{|S| :
b
f(S) 6= 0} is the degree of f and
ˆ
kf
ˆ
k
1
=
P
S⊆[k]
|
b
f(S)|
is the Fourier 1-norm of f.
Proof. From Theorem 32 we know that for any η > 2 ln 2 there is a constant C
η
such that
ε ≤ C
η
k
X
`=0
L
1,`
(f)
ηm
n
`/2
. (8)
There are a couple of ways to bound the above quantity. We start by proving Eq. (7a). Define
g : {−1, 1}
k
→ R