# Generalized parity-oblivious communication games powered by quantum
preparation contextuality

Prabuddha Roy<EMAIL_ADDRESS>Department of Mathematical Sciences,
Indian Institute of Science, Education $\&$ Research (IISER) Berhampur,
Transit Campus, Govt. ITI, NH 59, Berhampur 760 010, Ganjam, Odisha, India  A.
K. Pan<EMAIL_ADDRESS>Department of Physics, Indian Institute of
Technology Hyderabad, Telengana-502284, India

###### Abstract

The parity-oblivious random-access-code (PORAC) is a class of communication
games involving a sender (Alice) and a receiver (Bob). In such games, Alice’s
amount of communication to Bob is constraint by the parity-oblivious (PO)
conditions, so that the parity information of her inputs remains oblivious to
Bob. The PO condition in an operational theory is equivalently represented in
an ontological model that satisfies the preparation noncontextuality. In this
paper, we provide a nontrivial generalization of the existing two-level PORAC
and derive the winning probability of the game in the preparation
noncontextual ontological model. We demonstrate that the quantum theory
outperforms the preparation noncontextual model by predicting higher winning
probability in our generalized PORAC.

##  I Introduction

One of the major objectives of quantum information theory is to find novel
tasks for which quantum theory showcases its supremacy over the classical
theory in terms of communication, computational efficiency, and secrecy.
Communication games [1, 2, 3, 4, 5, 6, 8, 7, 9] are such information
processing tasks involving two or more parties who collaborate to perform a
given task with the highest possible efficiency with bounded amount of
communication.

Consider a scenario where two parties, Alice and Bob, collaborate to perform a
common task through one-way communication. In quantum theory, such a game can
be played in entanglement-assisted scenario[10, 11, 18, 19, 12, 14, 16, 22,
13, 17, 20, 21, 15, 23, 24, 25, 26] prepare-and-measure scenario [27, 31, 32,
33, 38, 39, 40, 44, 35, 36, 29, 34, 28, 30, 37, 41, 42, 43, 45, 46], and in
hybrid scenario, i.e., entanglement-assisted prepare-measure scenario[47]. To
exhibit the nontrivial quantum advantage in such a game, well-defined
constraints on the communication have been imposed, leading to two broad
classes of games. i) The communication game with bounded classical or quantum
dimension [4, 3, 5, 31, 22]. ii) The oblivious communication game [30, 17, 41,
42, 37, 13, 43, 21, 48, 46, 23], where one puts no restriction on the amount
of communication or dimension but imposes constraints so that the information
of a particular property of the inputs is not transmitted due to the
communication. However, there exist other communication games with energy
constraints [38] and information content constraints [44] to the inputs. It
has already been demonstrated in a plethora of works that the tasks played
with quantum resources can outperform its classical counterpart[10, 11, 18,
19, 12, 14, 16, 22, 13, 17, 20, 21, 27, 31, 32, 33, 38, 39, 40, 44, 35, 36,
29, 34, 28, 30, 37, 41, 42, 43, 9].

We focus here on a specific two-party communication game - the PORAC game [30,
17, 41, 42, 37, 13, 43, 21]. In a two-level $n$-bit PORAC, Alice receives
length-$n$ bit strings as inputs, randomly sampled from $\\{0,1\\}^{n}$. Bob
randomly receives index $y\in[n]$. They win the game when Bob outputs the
$y^{\text{th}}$ bit of Alice’s input, i.e., $b=x_{y}$. They collaborate to
optimize the winning probability of the game. Alice may communicate some bits
of information to Bob to help him. However, there is a constraint so that
Alice’s communication must not allow Bob to extract the parity information of
her inputs. Such a game was first put forward by Spekkens _et. al.,_ [30] for
two-level PORAC and later generalized for an arbittrary $d$-level case in
[34]. It has been argued [30, 34, 37, 42] that the satisfaction of the PO
condition in quantum theory can be equivalently represented in a preparation
noncontextual ontological model of quantum theory. It was shown [30, 37, 20,
22] that in two-level $n$-bit PORAC the optimal quantum success probability
exceeds the success probability for a preparation noncontextual model.
Therefore, any quantum advantage in PORAC reveals the preparation
contextuality.

We note here that in Spekkens _et. al.,_ [30] (followed by others [17, 41, 42,
20, 37, 13, 43]), the PO conditions in the two-level $n$-bit PORAC game are
defined with reference to a specific parity-set, say, $\mathbb{G}_{n,2}$. The
details will be specified soon. However, there is a scope for generalizing the
parity-set, and if so, then each of such sets can lead to a new PORAC game.

In this paper, we introduce a generalized parity-set $\mathbb{G}_{n,g_{n}}$
where $g_{n}\in\\{2,n-1\\}$ in the two-level $n$-bit PORAC game. For
$g_{n}=2$, we recover the standard scenario of Spekkens _et. al._ [30]. For a
given $n$, we then have $n-1$ numbers of different PORAC games. We derive the
maximum success probabilities of our generalized PORAC in a preparation
noncontextual model. Further, we demonstrate the quantum supremacy over the
preparation noncontextual model. Note that for $2$-bit PORAC there is only one
game and hence no generalization is possible.

We first demonstrate the quantum advantage over the preparation noncontextual
model for $3$-bit PORAC in the prepare-and-measure scenario. Instead of one
parity-set in Spekkens _et. al._ [30], we have two parity-sets in our $3$-bit
PORAC thereby leading to two different PORAC game. One of them is the same as
in [30]. We propose an experimental setup for testing $3$-bit generalized
PORAC. We also provide a sketch of the entanglement-assisted version of our
generalized $3$-bit PORAC, exhibiting the same optimal quantum advantage. We
extend our study for $4$-bit generalized PORAC where we have three different
games corresponding to the four different parity sets. Further, we demonstrate
the optimal quantum advantage over preparation noncontextual model for an
arbitrary $n$-bit PORAC corresponding to a specific parity-set.

The paper is organized as follows. In Sec. II, we briefly recapitulate the
essence of the two-level $n$-bit PORAC and corresponding preparation
noncontextual model. In Sec. III, we provide our generalized version of two-
level $n$-bit PORAC and derive the optimal success probability in a
preparation noncontextual model. In Sec. IV, we provide explicit encoding and
decoding schemes to derive the optimal quantum success probability for $3$-bit
PORAC game. In Sec. V. we derive the optimal quantum success probabilities for
$4$-bit PORAC and further generalization for an arbitrary $n$ in Sec. VI.
Finally, we summarize and discuss our work in Sec. VII.

##  II Preliminaries

Let us first briefly summarize the notion of preparation noncontextuality in
an ontological model of operational quantum theory and the standard PORAC
[30].

###  II.1 Ontological model of an operational theory and the notion of
noncontextuality

The modern framework of the ontological model of an operational theory was
introduced in [49, 50]. Given a preparation procedure $P$ and a measurement
procedure $M$, an operational theory provides the probability $p(k|P,M)$ of
obtaining a particular outcome $k$. If the operational theory is quantum
theory, then a preparation procedure $(P)$ produces a density matrix $\rho$,
and the measurement procedure $(M)$, in general, realizes positive-operator-
valued measure $E_{k}$. The probability of obtaining the outcome $k$ is given
by the Born rule, i.e., $p(k|P,M)=Tr[\rho E_{k}]$.

The ontological model of quantum theory can be described as follows [49, 50].
Whenever the density matrix $\rho$ is prepared by the preparation procedure
$P$, it is assumed that in an ontological model a probability distribution
$\mu_{P}(\lambda|\rho)$ of the ontic state $\lambda\in\Lambda$ is prepared.
Here, $\Lambda$ is the ontic state space. The probability distribution is
normalized, i.e., $\int_{\Lambda}\mu_{P}(\lambda|\rho)d\lambda=1$. Now, when
the measurement of $E_{k}$ is performed through a measurement procedure $M$,
the ontic state assigns the probability of obtaining the outcome $k$ known as
response function $\xi_{M}(k|\lambda,E_{k})$, satisfying
$\sum_{k}\xi_{M}(k|\lambda,E_{k})=1$. A viable ontological model must
reproduce the quantum probabilities. Hence, $\forall\rho$, $\forall E_{k}$ and
$\forall k$,
$\int_{\Lambda}\mu_{P}(\lambda|\rho)\xi_{M}(k|\lambda,E_{k})d\lambda=Tr[\rho
E_{k}]$.

Now, the notion of noncontextuality in an ontological model arises from the
equivalence class of experimental procedures. As argued in [50] that
operationally equivalent experimental procedures can be equivalently
represented in an ontological model. For example, if two preparation
procedures $P$ and $P^{\prime}$ prepare the same density matrix $\rho$, then
no measurement can operationally distinguish the context by which $\rho$ is
prepared. This leads to the notion of preparation noncontextuality in an
ontological model of quantum theory, i.e.,

$\displaystyle\forall M,\ k:\ \
p(k|P,M)=p(k|P^{\prime},M)\Rightarrow\mu_{P}(\lambda|\rho)=\mu_{P^{\prime}}(\lambda|\rho)$
(1)

which implies that the distribution of ontic states are equivalent
irrespective of the contexts $P$ and $P^{\prime}$ [50, 51]. Below we argue
that in a preparation noncontextual ontological model the parity-oblivious
constraint in a communication game implies an equivalent obliviousness
condition at the level of ontic states.

###  II.2 Parity-oblivious communication game

Let in an operational theory, Alice prepares the inputs $x$ by the preparation
procedures $P_{x}$, and upon receiving the input $y$, Bob performs the
measurement of $M_{y}$. Consider that there are $L$ subsets having equal
number of elements of the input $P_{l}\subset P_{x}$ with $l=1,2,3....L$. Let
us now impose a constraint in the preparation procedures in terms of
obliviousness condition. Such a restriction demands that given an input is not
distinguishable by any measurement whether it has come from $P_{l}\subset
P_{x}$ or from $P_{l^{\prime}}\subset P_{x}$. This holds even when Alice’s
amount of communication is not restricted. For our purpose, it will be enough
to consider the inputs of Alice are uniformly distributed, so that
$p_{A}(x)=1/|P_{x}|$ where $|P_{x}|$ is the cardinality of the set. Then,
$\forall\ l,l^{\prime},y,b$, the oblivious condition implies

$\displaystyle\sum\limits_{P_{x}\in
P_{l}}p(P_{x}|b,M_{y})=\sum\limits_{P_{x}\in P_{l^{\prime}}}p(P_{x}|b,M_{y})$
(2)

Using the Bayes rule
$p(P_{x}|b,M_{y})=p(b|P_{x},M_{y})p(P_{x}|M_{y})/p(b|M_{y})$, Eq. (2) can be
written as

$\displaystyle\forall b,y:\ \ \sum\limits_{P_{x}\in
P_{l}}p(b|P_{x},M_{y})=\sum\limits_{P_{x}\in P_{l^{\prime}}}p(b|P_{x},M_{y})$
(3)

This then implies that in an operational theory the two preparation procedures
$P_{l}$ and $P_{l^{\prime}}$ cannot be distinguishable for any outcome $b$ and
the measurement $M_{y}$ of Bob. As argued by Spekkens [50], that the
operationally equivalent experimental procedures can be equivalently
represented in an ontological model of the said operational theory. Such an
equivalence introduces the notion of noncontextuality in an ontological model.

Hence, for an ontological model of the operational theory satisfying the
assumption of preparation non-conextuality [50, 51, 52, 17] we can write

$\displaystyle\sum\limits_{{P_{x}}\in
P_{l}}\mu(\lambda|P_{x})=\sum\limits_{{P_{x}}\in
P_{l^{\prime}}}\mu(\lambda|P_{x})$ (4)

where $\lambda\in\Lambda$ is the ontic state and $\Lambda$ is the ontic state
space. Using Bayes theorem and noting the uniform distributon of $P_{x}$, we
have

$\displaystyle\sum\limits_{P_{x}\in
P_{l}}\mu(P_{x}|\lambda)=\sum\limits_{P_{x}\in
P_{l^{\prime}}}\mu(P_{x}|\lambda)$ (5)

This implies that the obliviousness condition must also be satisfied at the
level of ontic states $\lambda$ for the preparation noncontextual model. In
this work, we specifically focus on the PORAC in which no parity information
of the inputs will be transmitted to Bob due to Alice’s communication.

###  II.3 $n$-bit two-level PORAC

In a standard $2$-level $n$-bit RAC, Alice receives length-$n$ strings
randomly sampled from $x\in\\{0,1\\}^{n}$. Bob receives, uniformly at random,
the numbers $y\in[n]$. Bob’s task is to recover $y^{\text{th}}$ bit of Alice’s
input string $x$, which is the winning condition of the game. Throughout this
paper, we restrict ourselves in a $2$-level RAC.

In an arbitrary operational theory, Alice encodes her input string $x$ in a
physical state by preparation procedure $P_{x}$, and send it to Bob. After
receiving the state Bob performs a binary outcome measurement $M_{y}$ for
every $y=\\{1,2,...,n\\}$ and reports outcome $b$ as his output. Given the
winning condition $b=x_{y}$, the success probability of the RAC is given by

$\displaystyle\mathcal{P}_{n}=\dfrac{1}{2^{n}n}\sum_{y=1}^{n}\sum_{x\in\\{0,1\\}^{n}}p(b=x_{y}|P_{x},M_{y}).$
(6)

Since its a collaborative game, Alice communicates some bits of information to
Bob to help him. However, in PORAC we impose the parity-oblivious restriction
on Alice’s inputs so that her communication to Bob must not reveal the parity
information of her inputs. In [30] the parity-oblivious condition is defined
corresponding to a particular parity-set as

$\displaystyle\mathbb{G}_{n,2}=\\{x|x\in\\{0,1\\}^{n},\sum_{r=1}^{n}x_{r}\geq
2\\}$ (7)

The parity-oblivious condition demands that for every element
$s\in\mathbb{G}_{n,2}$, no information about $s.x=\oplus_{r}s_{r}x_{r}$ is to
be transmitted to Bob ($\oplus_{r}$ denotes sum modulo $2$), and every element
$s$ introduces a constraint on the inputs. For every $s$, the input strings
will be divided to $s$-parity 0 and $s$-parity 1 sets corresponding to $s.x=0$
and $s.x=1$ respectively. From Alice’s communication, Bob should not be able
to determine in which set a specific bit string belongs. Average success
probability in classical PORAC is [30]

$\displaystyle(\mathcal{P}_{n})_{cl}\leq\frac{(n+1)}{2n}.$ (8)

The detailed derivation of this bound can be found in [30]. We note here that
the way the parity-set in Eq. (7) is defined, _at most_ one bit can be
communicated. Else, it will reveal the parity information. Intuitively, if
Alice agrees beforehand to reveal the first bit ($x_{1}$), then for $y=1$,
occurring with probability $1/n$, Bob can predict $b=x_{y}$ with certainty.
For $y\neq 1$, occurring with probability $(n-1)/n$, Bob at best guesses the
bit $x_{y}$ with probability $1/2$. Then average success probability is
$1/n+(n-1)/2n$, saturating the above bound in Eq. (8).

###  II.4 $n$-bit two-level quantum PORAC

In a quantum RAC, Alice encodes her input string $x$ into density matrix
$\rho_{x}$, prepared by a procedure $P_{x}$. Bob performs a binary measurement
$\\{E_{y}^{b}\\}$ (with $\sum_{b}E_{y}^{b}=\mathbb{I}$ and $b=0,1$) for every
bit of $x$ he wants to decode. The quantum success probability can then be
written as

$(\mathcal{P}_{n})_{Q}=\dfrac{1}{2^{n}n}\sum_{y=1}^{n}\sum_{x\in\\{0,1\\}^{n}}\mathrm{tr}\hskip
2.0pt[\rho_{x}E_{y}^{b}].$ (9)

Here $\rho_{x}$ are the density matrices prepared by procedure $P_{x}$ by
performing local measurement on Alice’s set of observables.

Analogously, in quantum PORAC the parity-oblivious condition demands

$\displaystyle\forall s:\
\dfrac{1}{2^{n-1}}\sum\limits_{x|x.s=0}\rho_{x}=\dfrac{1}{2^{n-1}}\sum\limits_{x|x.s=1}\rho_{x}$
(10)

to be satisfied. This is then within the premise of the preparation
noncontextuality in an ontological model [50] of operational quantum theory.
Assuming preparation noncontextuality in an ontological model, the parity-
oblivious condition can be equivalently represented in an ontological model,
so that

$\displaystyle\forall s:\
\dfrac{1}{2^{n-1}}\sum\limits_{x|x.s=0}\mu(\lambda|\rho_{x})=\dfrac{1}{2^{n-1}}\sum\limits_{x|x.s=1}\mu(\lambda|\rho_{x}),$
(11)

where $\lambda\in\Lambda$ is the ontic state and $\Lambda$ is the ontic state
space. Following earlier discussions, by using Bayes rule it can be shown that

$\displaystyle\forall s:\
\dfrac{1}{2^{n-1}}\sum\limits_{x|x.s=0}\mu(\rho_{x}|\lambda)=\dfrac{1}{2^{n-1}}\sum\limits_{x|x.s=1}\mu(\rho_{x}|\lambda),$
(12)

implying that for preparation noncontextual models, the satisfaction of
parity-obliviousness condition in an operational theory provides equivalent
representation at the level of the ontic state $\lambda$ and it cannot contain
any information about the parity. Owing to the above discussion, Spekkens _et.
al._ [30] argued that the bound on the average success probability for a PORAC
given in Eq. (8) can also be said preparation noncontextual bound
$(\mathcal{P}_{n})_{pnc}$. Moreover, the optimal quantum success probability
of a $n$-bit standard PORAC from Eq. (9) is derived as
$(\mathcal{P}_{n})_{Q}^{opt}=(1/2)(1+1/\sqrt{n})>(\mathcal{P}_{n})_{pnc}$
[20]. Interestingly, the success probability decreases monotonically with
increasing $n$.

In this work, we propose a nontrivial generalization of the $n$-bit PORAC by
introducing a generalized parity-set. We derive the optimal success
probability of that generalized PORAC in a preparation noncontextual
ontological model for any arbitrary $n$. Further, we demonstrate the quantum
supremacy over preparation noncontextual model in a prepare-and-measure
scenario of the communication game.

##  III Generalized PORAC and preparation noncontextual bound

We note again that in Spekkens _et al._ [30], the PO condition (in Eq. (7))
imposed on Alice’s inputs is based on a particular parity-set where each
element $s\in\mathbb{G}_{n,2}$ gives a different constraint on the inputs. We
propose a nontrivial generalization of the standard PORAC [30] by introducing
the parity-set

$\displaystyle\mathbb{G}_{n,g_{n}}=\\{x|x\in\\{0,1\\}^{n},\sum_{r=1}^{n}x_{r}\geq
g_{n}\\}$ (13)

where $g_{n}\in\\{2,3...,n\\}$. The PO condition demands that for every
element $s\in\mathbb{G}_{n,g_{n}}$, no information about
$s.x=\oplus_{r}s_{r}x_{r}$ is to be transmitted to Bob ($\oplus_{r}$ denotes
sum modulo $2$), and every element $s$ introduces a constraint on the inputs.
For every $s$, the input strings will be divided to $s$-parity 0 and
$s$-parity 1 sets corresponding to $s.x=0$ and $s.x=1$ respectively. For
$g_{n}=2$, one recovers Eq. (7) the standard PORAC in Spekkens _et. al._ [30].

In a $n$-bit PORAC, the PO condition demands that the classical message $m$
sent from Alice to Bob must satisfy

$\forall s\in\mathbb{G}_{n,g_{n}}\
:\sum_{x|x.s=0}p(P_{x}|m)=\sum_{x|x.s=1}p(P_{x}|m).$ (14)

By noting the fact that in a preparation noncontextual ontological model, the
PO condition is equivalently represented, We propose the following theorem.

_Theorem 1: For any arbitrary $n$ and $g_{n}$ the optimal success probability
in a preparation noncontextual model is_

$\displaystyle(\mathcal{P}_{n}^{g_{n}})_{pnc}=\frac{(g_{n}+n-1)}{2n}.$ (15)

The proof of the above Theorem 1 is quite technical. We provide detailed
proofs for $n=3$ in Appendix A, and for arbitrary $n$ in Appendix B. We also
provide a simple strategy that reproduces the optimal value in Eq. (15) for
arbitrary $n$.

An intuitive argument for the simplest case of $3$-bit game could be useful
here. As defined in Eq. (15), for $g_{3}=3$ the relevant parity-set
$\mathbb{G}_{3,3}$ contains only one element $s=111$. Then, the $s$-parity $0$
and $s$-parity $1$ sets are $\\{000,011,101,110\\}$ and
$\\{001,010,100,111\\}$. It is proved in Appendix A that Alice is allowed to
communicate at most two bits to Bob. Considering the pre-decided strategy,
Alice communicates the first two bits of her input. It can be checked that
this will not reveal the parity information of her input. Then for both the
first and second bits appearing with the probability $1/3$, Bob is certain
about the bit, but for the third bit, he guesses randomly, i.e., with
probability $1/2$. Thus, the success probability in a preparation
noncontextual bound is derived as $(\mathcal{P}_{3}^{g_{3}=3})_{pnc}=5/6$. A
similar argument holds for any arbitrary two bits. It remains to explicitly
prove that Alice’s communication of two bits of information is required to
obtain the optimal preparation noncontextual value which we have provided in
Appendix A along with the preparation noncontextual bound for $n=3$.

We argue that for any arbitrary $n$ and $g_{n}$, Alice can communicate
$(g_{n}-1)$ bits without revealing the parity information. Then, for
$y=\\{1,2,...,g_{n}-1\\}$, each occurring with probability $1/n$, Bob can
predict the outcome $b=x_{y}$ with certainty, and for rest of the bits
$(n-g_{n}+1)$, Bob can only randomly guess the bit with probability $1/2$.
Thus, the average success probability in the preparation noncontextual becomes
is $(g_{n}-1)/n+(n-g_{n}+1)/2$, as claimed in Eq. (15). For $g_{n}=2$, the
preparation noncontextual bound in [30] is recovered.

We show that for any arbitrary $n$-bit PORAC corresponding to the parity-set
$\mathbb{G}_{n,g_{n}}$, quantum theory outperforms the classical noncontextual
model. Given the $g_{n}$, in a quantum PORAC Alice encodes her $n$-bit strings
into density matrices $\rho_{x}\in 2^{\otimes(g_{n}-1)}$. We shortly show that
$\rho_{x}$s have to be pure states to get an optimal quantum advantage.

_Results: The optimal quantum success probability violates the preparation
noncontextual bound of the generalized PORAC corresponding to the parity-set
$\mathbb{G}_{n,g_{n}}$ for any arbitrary $n$, i.e.,
$(\mathcal{P}_{n}^{g_{n}})_{Q}>(\mathcal{P}_{n}^{g_{n}})_{pnc}$_ .

Before proving the general results for any arbitrary $n$ and $g_{n}$, for the
sake of better understanding, we explicitly derive the quantum advantage of
our generalized PORAC for $g_{3}=3$ and $g_{4}=3,4$. Further, we demonstrate
the quantum advantage for the generalized quantum PORAC for $g_{n}=n$ when
$n>4$. Note that, those derivations are fully analytical, but for the higher
values of $n$ for arbitrary $g_{n}$ one requires computational work.

##  IV $3$-bit generalized quantum PORAC

For $3$-bit PORAC, we have two games corresponding to the two parity sets,
$\mathbb{G}_{3,2}$ (the standard one) and $\mathbb{G}_{3,3}$ for $g_{3}=2$ and
$3$ respectively. The case of $\mathbb{G}_{3,2}$ is already considered in
[30]. We explicitly demonstrate the PORAC corresponding to $\mathbb{G}_{3,3}$
where the preparation noncontextual bound is
$(\mathcal{P}_{3}^{g_{3}=3})_{pnc}=5/6$. Also, Alice is allowed to communicate
at most two bits of information to Bob to satisfy the PO condition, i.e.,
without revealing the parity information of her input.

Note that, for the parity-set $\mathbb{G}_{3,3}$ in Eq. (15), we have only one
parity element $s=111$, leading to the $s$-parity $0$ set is
$\\{000,011,101,110\\}$ and the $s$-parity $1$ set is $\\{001,010,100,111\\}$.
The PO condition in an operational theory needs to satisfy the following
condition.

$\displaystyle p(P_{000}|b,M_{y})+p(P_{110}|b,M_{y})+p(P_{011}|b,M_{y})$ (16)
$\displaystyle+$ $\displaystyle
p(P_{101}|b,M_{y})=p(P_{100}|b,M_{y})+p(P_{010}|b,M_{y})$ $\displaystyle+$
$\displaystyle p(P_{001}|b,M_{y})+p(P_{111}|b,M_{y})$

In quantum theory, Alice encodes her inputs $x\in\\{0,1\\}^{3}$ into eight
quantum states $\rho_{x}\in\mathbb{C}^{2}\otimes\mathbb{C}^{2}$ and sends them
to Bob. The PO condition corresponding to the parity element $s=111$ then
provides

$\displaystyle\rho_{000}+\rho_{011}+\rho_{110}+\rho_{101}=\rho_{001}+\rho_{010}+\rho_{100}+\rho_{111}$
(17)

i.e., the mixture of the four states corresponding to the even parity is
identical to the mixture of the four states corresponding to odd parity. After
receiving the particles, Bob performs three projective measurements
$\\{\Pi_{3,y}^{0},\Pi_{3,y}^{1}\\}$ with $y=1,2,3$, with
$b=x_{y}\in\\{0,1\\}$. The quantum success probability from Eq. (9) can be
explicitly written as

$\displaystyle(\mathcal{P}_{3})_{Q}=\dfrac{1}{24}$ $\displaystyle\mathrm{tr}$
$\displaystyle\Big{[}p(0|\rho_{000},\Pi_{3,1}^{0})+p(0|\rho_{000},\Pi_{3,2}^{0})+p(0|\rho_{000},\Pi_{3,3}^{0})+p(1|\rho_{111},\Pi_{3,1}^{1})+p(1|\rho_{111},\Pi_{3,2}^{1})+p(1|\rho_{111},\Pi_{3,3}^{1})$
$\displaystyle+$ $\displaystyle
p(0|\rho_{010},\Pi_{3,1}^{0})+p(1|\rho_{010},\Pi_{3,2}^{1})+p(0|\rho_{010},\Pi_{3,3}^{0})+p(1|\rho_{101},\Pi_{3,1}^{1})+p(0|\rho_{101}\Pi_{3,2}^{0})+p(1|\rho_{101},\Pi_{3,3}^{1})$
$\displaystyle+$ $\displaystyle
p(0|\rho_{001},\Pi_{3,1}^{0})+p(0|\rho_{001},\Pi_{3,2}^{0})+p(1|\rho_{001},\Pi_{3,3}^{1})+p(1|\rho_{110},\Pi_{3,1}^{1})+p(1|\rho_{110},\Pi_{3,2}^{1})+p(0|\rho_{110},\Pi_{3,3}^{0})$
$\displaystyle+$ $\displaystyle
p(0|\rho_{011},\Pi_{3,1}^{0})+p(1|\rho_{011},\Pi_{3,2}^{1})+p(1|\rho_{011},\Pi_{3,3}^{1})+p(1|\rho_{100},\Pi_{3,1}^{1})+p(0|\rho_{100},\Pi_{3,2}^{0})+p(0|\rho_{100},\Pi_{3,3}^{0})\Big{]}$

Using $\Pi_{3,y}^{0}+\Pi_{3,y}^{1}=\mathbb{I}$ with $y=1,2,3$, Eq. (IV) can be
re-written as

$\displaystyle(\mathcal{P}_{3})_{Q}=\dfrac{1}{2}+\dfrac{1}{24}$
$\displaystyle\mathrm{tr}$
$\displaystyle\Big{[}(\rho_{000}-\rho_{111})(\Pi_{3,1}^{0}+\Pi_{3,2}^{0}+\Pi_{3,3}^{0})$
$\displaystyle+$
$\displaystyle(\rho_{010}-\rho_{101})(\Pi_{3,1}^{0}-\Pi_{3,2}^{0}+\Pi_{3,3}^{0})$
$\displaystyle+$
$\displaystyle(\rho_{001}-\rho_{110})(\Pi_{3,1}^{0}+\Pi_{3,2}^{0}-\Pi_{3,3}^{0})$
$\displaystyle+$
$\displaystyle(\rho_{011}-\rho_{100})(\Pi_{3,1}^{0}-\Pi_{3,2}^{0}-\Pi_{3,3}^{0})\Big{]}$

which can be further simplified by using
$\Pi_{3,y}^{b}=(\mathbb{I}+(-1)^{b}B_{3,y})/{2}$ where $b\in\\{0,1\\}$ and by
suitably rearranging as

$\displaystyle(\mathcal{P}_{3})_{Q}=\dfrac{1}{2}$ $\displaystyle+$
$\displaystyle\dfrac{1}{48}\mathrm{tr}\Big{[}(\rho_{000}-\rho_{110}+\rho_{011}-\rho_{101})B_{3,1}$
$\displaystyle+$
$\displaystyle(\rho_{000}-\rho_{110}-\rho_{011}+\rho_{101})B_{3,2}$
$\displaystyle+$
$\displaystyle(\rho_{000}+\rho_{110}-\rho_{011}-\rho_{101})B_{3,3}$
$\displaystyle+$
$\displaystyle(\rho_{001}+\rho_{010}-\rho_{111}-\rho_{100})B_{3,1}$
$\displaystyle+$
$\displaystyle(\rho_{001}-\rho_{010}-\rho_{111}+\rho_{100})B_{3,2}$
$\displaystyle-$
$\displaystyle(\rho_{001}-\rho_{010}+\rho_{111}-\rho_{100})B_{3,3}\Big{]}.$

To obtain optimal quantum success probability, let us first analyze the term
$\mathrm{tr}[(\rho_{000}-\rho_{110}+\rho_{011}-\rho_{101})B_{3,1}]$. Note that
to get maximum value $\rho_{000}$ and $\rho_{011}$ have to be the eigenstates
of $B_{1}$ with eigenvalue $+1$, and $\rho_{110}$ and $\rho_{101}$ have to be
eigenstates of $B_{1}$ with eigenvalue $-1$. Since we consider two-qubit
system, $\rho_{000},\rho_{011},\rho_{110}$ and $\rho_{101}$ has to be
orthogonal pure states implying
$\rho_{000}+\rho_{110}+\rho_{011}+\rho_{101}=\mathrm{I}\otimes\mathrm{I}$.
Similar argument can be made for the second and third terms. Now, if we
consider $\mathrm{tr}[(\rho_{001}+\rho_{010}-\rho_{111}-\rho_{100})B_{3,2}]$,
maximization criteria gives $\rho_{001},\rho_{010},\rho_{111}$ and
$\rho_{100}$ to beorthogonal pure states, ie.,
$\rho_{001}+\rho_{010}+\rho_{111}+\rho_{100}=\mathrm{I}\otimes\mathrm{I}$ .
This in turn satisfies the PO condition in Eq. (17). The same argument holds
for last two terms.

Above argument leads us to define three two-qubit observables of the form

$\displaystyle A_{3,1}=\rho_{000}+\rho_{011}-\rho_{110}-\rho_{101}$
$\displaystyle A^{\prime}_{3,1}=\rho_{000}-\rho_{011}+\rho_{110}-\rho_{101}$
(21)
$\displaystyle\tilde{A}_{3,1}=\rho_{000}-\rho_{011}+\rho_{110}-\rho_{101}$

By construction
$[A_{3,1},A^{\prime}_{3,1}]=[A^{\prime}_{3,1},\tilde{A}_{3,1}]=[A_{3,1},\tilde{A}_{3,1}]=0$,
as $A_{3,1},A^{\prime}_{3,1}$ and $\tilde{A}_{3,1}$ have common eigenstates.

Similarly, we can construct three more two-qubit observables corresponding to
the other four states $\rho_{x}$ for which $x|x.s=1$, are given by

$\displaystyle A_{3,2}=\rho_{001}+\rho_{010}-\rho_{100}-\rho_{111}$ (22)
$\displaystyle A^{\prime}_{3,2}=\rho_{001}-\rho_{010}+\rho_{100}-\rho_{111}$
$\displaystyle\tilde{A}_{3,2}=\rho_{001}-\rho_{010}-\rho_{100}+\rho_{111}$

where the observables satisfies
$[A_{3,2},A^{\prime}_{3,2}]=[A^{\prime}_{3,2},\tilde{A}_{3,2}]=[A_{3,2},\tilde{A}_{3,2}]=0$.

Note here that, since in two-qubit system there exists at most three mutually
commuting observables, the following relations must be satisfied

$\displaystyle A_{3,1}A^{\prime}_{3,1}=\pm{\tilde{A}}_{3,1};$ $\displaystyle
A_{3,2}A^{\prime}_{3,2}=\pm{\tilde{A}}_{3,2}.$ (23)

This is due to the fact that the product of any two observables has to return
the third one with $\pm$.

Thus, the quantum success probability from Eq. (IV) can be written as

$(\mathcal{P}_{3}^{g_{3}=3})_{Q}=\dfrac{1}{2}+\dfrac{\mathrm{tr}[\Delta_{3}^{g_{3}=3}]}{48}$
(24)

where $\Delta_{3}^{g_{3}=3}$ is the correlation function of the form

$\displaystyle\Delta_{3}^{g_{3}=3}$ $\displaystyle=$
$\displaystyle(A_{3,1}+A_{3,2})B_{3,1}$ $\displaystyle+$
$\displaystyle({\tilde{A}}_{3,1}-{\tilde{A}}_{3,2})B_{3,3}+(A^{\prime}_{3,1}+A^{\prime}_{3,2})B_{3,2}.$

For deriving the quantum bound, without loss of generality we can impose one
of the three conditions $A_{3,1}=A_{3,2}$, $A^{\prime}_{3,1}=A^{\prime}_{3,2}$
and ${\tilde{A}}_{3,1}=-{\tilde{A}}_{3,2}$. This is due to the fact that if we
choose, say, $A^{\prime}_{3,1}=A^{\prime}_{3,2}\equiv A^{\prime}_{3}$ so that
both sets $\\{\rho_{x}|_{s.x=1}\\}$ and $\\{\rho_{x}|_{s.x=0}\\}$ are the
eigenstates of $A^{\prime}_{3}$. It can be simply checked that this does not
affect the preparation noncontextual bound. Such choice of observables are
available in two-qubit system.

Optimal value is achieved when $B_{3,1}=(A_{3,1}+A_{3,2})/\sqrt{2}$ ,
$B_{3,2}=A^{\prime}_{3}$ and
$B_{3,3}=(\tilde{A}_{3,1}-{\tilde{A}}_{3,2})/\sqrt{2}$. Thus, the optimal
quantum value of the correlation function $\Delta_{3}^{g_{3}=3}$ in Eq. (IV)
is derived as

$\displaystyle\mathrm{tr}[\Delta_{3}^{g_{3}=3}]_{Q}^{opt}=8+8\sqrt{2}.$ (26)

which in turn provides the optimal quantum success probability

$(\mathcal{P}_{3}^{g_{3}=3})_{Q}^{opt}=\dfrac{1}{2}+\dfrac{1+\sqrt{2}}{6}\approx
0.902$ (27)

i.e., outperforming the preparation noncontextual bound $5/6\approx 0.833$.

One of such the choices of Alice’s observables are

$\displaystyle A_{3,1}=\sigma_{x}\otimes\sigma_{x}$ $\displaystyle,\ \ \ \
\tilde{A}_{3,1}=\mathbb{I}\otimes\sigma_{x};\ \
A^{\prime}_{3}=\sigma_{x}\otimes\mathbb{I};$ $\displaystyle
A_{3,2}=\sigma_{x}\otimes\sigma_{z}$ $\displaystyle,\ \ \ \
\tilde{A}_{3,2}=\mathbb{I}\otimes\sigma_{z},$ (28)

satisfying the required mutual commutation relation of the sets
$\\{A_{3,1},A^{\prime}_{3},{\tilde{A}}_{3,1}\\}$ and
$\\{A_{3,2},A^{\prime}_{3},{\tilde{A}}_{3,2}\\}$. Hence, the encoding density
matrices can be easily constructed from the commuting observables as
$\rho_{000}=|+0\rangle\langle 0+|$, $\rho_{110}=|+1\rangle\langle 1+|$,
$\rho_{001}=|++\rangle\langle++|$, $\rho_{100}=|-+\rangle\langle+-|$ and so
on.

Note that maximum quantum value of the sequential correlation, say,
$\mathrm{tr}[A_{3,1}B_{3,1}]$ is $4$, as $A_{3,1}$ and $B_{3,1}$ are two-qubit
observables. By keeping this in mind while deriving the bound in preparation
noncontextual model, one may surmise that $\mathrm{tr}[\Delta_{3}^{g_{3}=3}]$
has the classical upper bound $24$. But, in a preparation noncontextual model,
$\mathrm{tr}[\Delta_{3}^{g_{3}=3}]_{pnc}\leq 16$. Consequently, we have
$\left(\mathcal{P}_{3}^{g_{3}=3}\right)_{pnc}\leq 5/6\approx 0.833$, as
claimed in Eq. (15). This is due to the fact that to satisfy the PO condition,
the relations in Eq. (IV) has to be satisfied. Owing to this notion of
equivalent representation of quantum theory in a preparation noncontextual
ontological model,
$\xi(k|A_{3,1},\lambda)\xi(k|A^{\prime}_{3,1},\lambda)=\pm\xi(k|{\tilde{A}}_{3,1},\lambda)$
and
$\xi(k|A_{3,2},\lambda)\xi(k|A^{\prime}_{3,2},\lambda)=\pm\xi(k|{\tilde{A}}_{3,2},\lambda)$.
This restriction ensures $\mathrm{tr}[\Delta_{3}^{g_{3}=3}]_{pnc}\leq 16$.

In order to test our proposed $3$-bit PORAC game in the prepare-and-measure
scenario, we provide an experimental setup. We consider joint spin
(polarization) and path degrees of freedom of a single particle and suitable
Mach-Zehender interferometer along with phase shifters and beam splitters for
implementing our protocol. The details of the setup with necessary
illustration are placed in Appendix F.

###  IV.1 $3$-bit generalized PORAC in entanglement-assisted scenario

Our proposed prepare-and-measure scenario can also be played in an
entanglement-assisted scenario as shown in Appendix E. Note that satisfying
the PO condition, Alice can at most communicate two bits of classical
information to Bob. In Appendix E, we provide a detailed encoding scheme using
sequential degeneracy-breaking measurement of two commuting observables as
well as the decoding scheme where Bob performs projective measurement for the
optimal quantum success probability in $3$-bit PORAC game.

We demonstrate that the optimal quantum success probability remains the same
as in the prepare-and-measure scenario. We note here that, in the
entanglement-assisted scenario, although we consider two-qubit system to
demonstrate quantum supremacy, the quantum success probability of $3$-bit
PORAC game can be derived without considering the dimension of the system.
This feature enables a device-independent self-testing based on our
generalized PORAC game. We also provide an encoding-decoding strategy that can
reestablish the optimal quantum success probability in terms of the optimal
quantum violation of a suitably derived Bell expression
$\mathcal{B}_{3}^{g_{3}=3}$ in Appendix E.

##  V $4$-bit generalized quantum PORAC

Before generalizing for arbitrary $n$ and $g_{n}$, we consider $4$-bit PORAC
where we have three different games corresponding to the parity sets
$\mathbb{G}_{4,2}$ (standard one), $\mathbb{G}_{4,3}$ and $\mathbb{G}_{4,4}$.
The game corresponding to $\mathbb{G}_{4,2}$ is the standard one which has
already been explored in [30, 20].

###  V.1 Optimal quantum advantage for $\mathbb{G}_{4,4}$

We start by noting that for $\mathbb{G}_{4,4}$, the parity-set contains only
one element $s=1111$. In such a case, Alice is allowed to communicate three
bits of information to Bob without revealing the parity information of her
input. The preparation noncontextual bound is already calculated as
$(\mathcal{P}_{4}^{g_{4}=4})_{pnc}=7/8$.

In quantum theory, Alice encodes the inputs in sixteen quantum states
$\rho_{x}\in\mathbb{C}^{2}\otimes\mathbb{C}^{2}\otimes\mathbb{C}^{2}$. The PO
condition corresponding to the parity element $s=1111$ requires
$\sum_{x|s.x=0}\rho_{x}=\sum_{x|s.x=1}\rho_{x}$ to be satisfied. Now,
employing a similar strategy as in the case of $3$-bit PORAC game we obtain
the optimal quantum success probability. The detailed derivation is provided
in Appendix C.

We again argue that the maximum value requires $\rho_{x}$’s with $s.x=0$ to be
orthogonal eigenstates of $B_{4,1}$ which in turn satisfies
$\sum_{x|s.x=0}\rho_{x}=\mathrm{I}\otimes\mathrm{I}\otimes\mathrm{I}$. This
leads us to define four three-qubit observables having common eigenstates
$A_{4,1},A^{\prime}_{4,1},A^{\prime\prime}_{4,1}$ and $\tilde{A}_{4,1}$
satisfying
$[A_{4,1},A^{\prime}_{4,1}]=[A^{\prime}_{4,1},A^{\prime\prime}_{4,1}]=[A^{\prime\prime}_{4,1},\tilde{A}_{4,1}]=[A_{4,1},\tilde{A}_{4,1}]=0$
and so on. Similar argument holds good for $\rho_{x}$ with $s.x=1$ where
$\sum_{x|s.x=1}\rho_{x}=\mathrm{I}\otimes\mathrm{I}\otimes\mathrm{I}$ will
satisfy such that four three-qubit observables having common eigenstates
$A_{4,2},A^{\prime}_{4,2},A^{\prime\prime}_{4,2}$ and $\tilde{A}_{4,2}$ can be
defined.

The decoding scheme is also similar to $3$-bit case. As derived in Appendix C,
the quantum success probability is given by

$(\mathcal{P}_{4}^{g_{4}=4})_{Q}=\dfrac{1}{2}+\dfrac{\mathrm{tr}[\Delta_{4}^{g_{4}=4}]_{Q}}{128}$
(29)

where the expression $\Delta_{4}^{g_{4}=4}$ is derived as

$\displaystyle\Delta_{4}^{g_{4}=4}$ $\displaystyle=$
$\displaystyle(A_{4,1}+A_{4,2})B_{4,1}+(\tilde{A}_{4,1}-\tilde{A}_{4,2})B_{4,4}$
(30) $\displaystyle+$
$\displaystyle(A^{\prime}_{4,1}+A^{\prime}_{4,2})B_{4,2}+(A^{\prime\prime}_{4,1}+A^{\prime\prime}_{4,2})B_{4,3}.$

Here $\tilde{A}_{4,1}$ is commuting with $A_{4,1},A^{\prime}_{4,1}$ and
$A^{\prime\prime}_{4,1}$ and hence
$A_{4,1}A^{\prime}_{4,1}A^{\prime\prime}_{4,1}=\pm\tilde{A}_{4,1}$. This comes
from the fact that in a three-qubit system there are at most four mutually
commuting observables. Similarly, we have
$A_{4,2}A^{\prime}_{4,2}A^{\prime\prime}_{4,2}=\pm\tilde{A}_{4,2}$. In an
ontological model of quantum theory this implies
$\xi(k|A_{4,1},\lambda)\xi(k|A^{\prime}_{4,1},\lambda)\xi(k|A^{\prime\prime}_{4,1},\lambda)=\pm\xi(k|{\tilde{A}}_{4,1},\lambda)$
and
$\xi(k|A_{4,2},\lambda)\xi(k|A^{\prime}_{4,2},\lambda)\xi(k|A^{\prime\prime}_{4,2},\lambda)=\pm\xi(k|{\tilde{A}}_{4,2},\lambda)$.
Using them in Eq. (30), we derive $\mathrm{tr}[\Delta_{4}^{g_{4}=4}]_{pnc}\leq
48$ and consequently from Eq. (29)
$(\mathcal{P}_{4}^{g_{4}=4})_{pnc}=7/8\approx 0.875$. This eventually
certifies the bound calculated for $g_{4}=4$ in Eq. (15).

Now, by keeping in mind that we are dealing with a three-qubit system and with
the aim of optimization of the correlation function Eq. (30), without loss of
generality, we can always choose
$A^{\prime}_{4,1}=A^{\prime}_{4,2}=A^{\prime}_{4}$ and
$A^{\prime\prime}_{4,1}=A^{\prime\prime}_{4,2}=A^{\prime\prime}_{4}$ for
deriving the quantum optimal bound. This is due to the fact that if we choose,
say, $A^{\prime}_{4,1}=A^{\prime}_{4,2}\equiv A^{\prime}_{4}$ so that both
sets $\\{\rho_{x}|_{s.x=1}\\}$ and $\\{\rho_{x}|_{s.x=0}\\}$ are the
eigenstates of $A^{\prime}_{4}$. Similarly, we can choose
$A^{\prime\prime}_{4,1}=A^{\prime\prime}_{4,2}\equiv A^{\prime\prime}_{4}$.
This means we have two sets of commuting observables
$\\{A_{4,1},\tilde{A}_{4,1},A^{\prime}_{4},A^{\prime\prime}_{4}\\}$ and
$\\{A_{4,2},\tilde{A}_{4,2},A^{\prime}_{4},A^{\prime\prime}_{4}\\}$. It can be
simply checked that the preparation noncontextual bound remains unchanged.

With the above choices of observables, we can rewrite the correlation function
in Eq. (30) as

$\displaystyle\Delta_{4}^{g_{4}=4}=$
$\displaystyle(A_{4,1}+A_{4,2})B_{4,1}+(\tilde{A}_{4,1}-\tilde{A}_{4,2})B_{4,4}$
(31) $\displaystyle+$ $\displaystyle
2A^{\prime}_{4}B_{4,2}+2A^{\prime\prime}_{4}B_{4,3}.$

whose optimal quantum value is derived as

$\mathrm{tr}[\Delta_{4}^{g_{4}=4}]_{Q}^{opt}=32+16\sqrt{2}$ (32)

This is obtained when Bob’s choices of observables are
$B_{4,1}=(A_{4,1}+A_{4,2})/\sqrt{2}$ , $B_{4,2}=A^{\prime}_{4}$,
$B_{4,3}=A^{\prime\prime}_{4}$ and
$B_{4,4}=({\tilde{A}}_{4,1}-{\tilde{A}}_{4,2})/\sqrt{2}$. Consequently, the
optimal quantum success probability from Eq. (29) is given by

$\displaystyle\left(\mathcal{P}_{4}^{g_{4}=4}\right)_{Q}^{opt}=\dfrac{1}{2}+\dfrac{2+\sqrt{2}}{8}\approx
0.926.$ (33)

which is greater than the preparation noncontextual bound $0.875$. One of the
possible choices of Alice’s observables providing the optimal quantum value is
the following.

$\displaystyle A_{4,1}=\sigma_{x}\ \otimes\ \sigma_{x}\ \otimes\ \sigma_{x},\
\ {\tilde{A}}_{4,1}=\mathbb{I}\ \otimes\ \sigma_{x}\ \otimes\ \mathbb{I};$
$\displaystyle A^{\prime}_{4}=\sigma_{x}\ \otimes\ \mathbb{I}\
\otimes\mathbb{I};\ \ A^{\prime\prime}_{4}=\mathbb{I}\ \otimes\mathbb{I}\
\otimes\ \sigma_{x},$ (34) $\displaystyle A_{4,2}=\sigma_{x}\ \otimes\
\sigma_{z}\otimes\ \sigma_{x},\ \ {\tilde{A}}_{4,2}=\mathbb{I}\ \otimes\
\sigma_{z}\ \otimes\mathbb{I},$

and Bob’s observables can be fixed accordingly.

###  V.2 Optimal quantum advantage for $\mathbb{G}_{4,3}$

In the $4$-bit PORAC, the parity-set corresponding to $\mathbb{G}_{4,3}$
contains five elements, $s=1110,1101,1011,0111$ and $1111$. The PO condition
has to be satisfied for all of them. For such a parity-set, Alice is allowed
to communicate two bits without revealing the parity information and
consequently the preparation noncontextual bound is
$(\mathcal{P}_{4}^{g_{4}=3})_{pnc}=3/4$.

In quantum theory, Alice encodes her inputs $x\in\\{0,1\\}^{4}$ into sixteen
quantum states $\rho_{x}\in\mathbb{C}^{2}\otimes\mathbb{C}^{2}$ and sends to
Bob. As explicitly shown in the Appendix D, the quantum success probability
can be cast as

$(\mathcal{P}_{4}^{g_{4}=3})_{Q}=\dfrac{1}{2}+\dfrac{\mathrm{tr}[\Delta_{4}^{g_{4}=3}]_{Q}}{128}$
(35)

where $\Delta_{4}^{g_{4}=3}$ has the form

$\displaystyle\Delta_{4}^{g_{4}=3}$ $\displaystyle=$
$\displaystyle\Big{[}(A_{4,1}+A_{4,2}+A_{4,3}+A_{4,4})B_{4,1}$
$\displaystyle+$ $\displaystyle(A_{4,1}-A_{4,2}+A_{4,3}-A_{4,4}))B_{4,2}$
$\displaystyle+$
$\displaystyle(A^{\prime}_{4,1}+A^{\prime}_{4,2}+A^{\prime}_{4,3}+A^{\prime}_{4,4})B_{4,3}$
$\displaystyle+$
$\displaystyle(A^{\prime}_{4,1}-A^{\prime}_{4,2}-A^{\prime}_{4,3}+A^{\prime}_{4,4})B_{4,4}\Big{]}$

For the element $s=1111$, parity conditions
$\sum_{x|s.x=0}\rho_{x}=\sum_{x|s.x=1}\rho_{x}=\mathrm{I}\otimes\mathrm{I}$ is
trivially satisfied. But for the elements, $s=1110,1101,1011$ and $0111$, four
different nontrivial relations between Alice’s observables are derived as
follows.

$\displaystyle A_{4,1}^{\prime}+A_{4,2}^{\prime}+A_{4,3}-A_{4,4}^{\prime}=0;\
\ A_{4,1}-A_{4,2}-A_{4,3}^{\prime}-A_{4,4}=0;$ $\displaystyle
A_{4,1}^{\prime}-A_{4,2}^{\prime}-A_{4,3}-A_{4,4}^{\prime}=0;\ \
A_{4,1}+A_{4,2}-A_{4,3}^{\prime}+A_{4,4}=0$

The above functional relations between Alice’s observables impose the
constraint relations

$A_{4,1}=A_{4,3}^{\prime};\ \ \ \ \ \ A_{4,1}^{\prime}=A_{4,4}^{\prime}.$ (38)

Using Eq. (38), the correlation function $\Delta_{4}^{g_{4}=3}$ in Eq. (V.2)
can be re-written as

$\displaystyle\Delta_{4}^{g_{4}=3}=(A_{4,1}+A_{4,2}+A_{4,3}+A_{4,4})B_{4,1}$
$\displaystyle+$ $\displaystyle(A_{4,1}-A_{4,2}+A_{4,3}-A_{4,4})B_{4,2}$
$\displaystyle+$
$\displaystyle(2A^{\prime}_{4,1}+A^{\prime}_{4,2}+A_{4,1})B_{4,3}+(2A^{\prime}_{4,1}-A^{\prime}_{4,2}-A_{4,1})B_{4,4}.$

It is then straightforward to check that
$\mathrm{tr}[\Delta_{4}^{g_{4}=3}]_{pnc}=32$, leading to
$\left(\mathcal{P}_{4}^{g_{4}=3}\right)_{pnc}=3/4$. The optimal quantum
success probability is derived as $(\mathcal{P}_{4}^{g_{4}=3})_{Q}\approx
0.819>3/4$, thereby revealing quantum advantage over preparation noncontextual
bound. The details of the derivation is placed in Appendix D.

##  VI $n$-bit generalized quantum PORAC

In an $n$-bit PORAC the generalized parity-set is
$\mathbb{G}_{n,g_{n}}=\\{x|x\in\\{0,1\\}^{n},\sum_{r}x_{r}\geq g_{n}\\}$. We
demonstrate the quantum advantage for the case $g_{n}=n$. For such a case only
one parity element $s=111....11$, is allowed such that $(n-1)$ bits can be
communicated to Bob without revealing the parity information.

Alice encodes her inputs $\\{0,1\\}^{n}$ into $2^{n}$ quantum states
$\rho_{x}$ following the same strategy as showcased for $3$ and $4$-bit PORAC.
Note here that, for such encoding in quantum theory, the PO condition
$\sum_{x|s.x=0}\rho_{x}=\sum_{x|s.x=1}\rho_{x}=\mathrm{I}^{\otimes(n-1)}$ is
satisfied. Following the same argument as for $3$ and $4$-bit case, Alice’s
generalised observables can be constructed.

Bob’s decoding strategy remains same as earlier who performs projective
measurements $\\{\Pi_{n,y}^{0},\Pi_{n,y}^{1}\\}$ with $y=1,2,...,n$. Using Eq.
(9), the success probability in quantum theory for $n$-bit PORAC with
$g_{n}=n$ can be written as

$(\mathcal{P}_{n}^{g_{n}=n})_{Q}=\dfrac{1}{2}+\dfrac{\mathrm{tr}[\Delta_{n}^{g_{n}=n}]_{Q}}{2^{n+1}n}.$
(40)

where the correlation function $\Delta_{n}^{g_{n}=n}$ is derived as

$\displaystyle\Delta_{n}^{g_{n}=n}$ $\displaystyle=$
$\displaystyle(A_{n,1}+A_{n,2})B_{n,1}+(\tilde{A}_{n,1}-\tilde{A}_{n,2})B_{n,n}$
(41) $\displaystyle+$ $\displaystyle 2\sum_{k=1}^{n-2}A_{n}^{k}B_{n,k+1}.$

The preparation noncontextual bound
$\mathrm{tr}[\Delta_{n}^{g_{n}=n}]_{pnc}\leq 2^{n}(n-1)$ and consequently,
$(\mathcal{P}_{n}^{g_{n}=n})_{pnc}\leq(2n-1)/2n$.

Given Bob’s choices of observables as $B_{n,1}=(A_{n,1}+A_{n,2})/\sqrt{2}$ and
$B_{n,n}=(\tilde{A}_{n,1}-\tilde{A}_{n,2})/\sqrt{2}$ ,but
$B_{n,k+1}=A_{n}^{k}$ with $k\in\\{1,...,n-2\\}$, the optimal quantum success
probability is derived as

$\displaystyle(\mathcal{P}_{n}^{g_{n}=n})_{Q}\leq\dfrac{1}{2}+\dfrac{(n-2)+\sqrt{2}}{2n}>(\mathcal{P}_{n}^{g_{n}=n})_{pnc}$
(42)

thereby providing the quantum advantage for the generalized PORAC.

By using the observables required for $n=3,4$ cases, we can recursively fix
Alice’s observables for $n\geq 5$ as follows.

$\displaystyle A_{n,1}=A_{n-1,1}\otimes\sigma_{x},\ \ \
A_{n,2}=A_{n-1,2}\otimes\sigma_{x},$ $\displaystyle
A_{n}^{k}=\left\\{\begin{aligned} &\mathbb{I}\otimes A_{n-1}^{k-1},&&\ \
\text{for}\ \ k=n-2,\\\ &A_{n-1}^{k}\otimes\mathbb{I},&&\ \ \text{for}\ \ \
k=1\ \ \text{to}\ \ n-3,\end{aligned}\right.$ (43)
$\displaystyle\tilde{A}_{n,1}=A_{n,1}\prod\limits_{k=1}^{n-2}{A}_{n}^{k}\ \
\text{and}\ \ \tilde{A}_{n,2}=A_{n,2}\prod\limits_{k=1}^{n-2}{A}_{n}^{k}.$

Similarly, Bob’s observables can also be fixed.

##  VII Summary and Discussion

In summary, we proposed a nontrivial generalization of standard $n$-bit two-
level PORAC by introducing a generalized parity-set $\mathbb{G}_{n,g_{n}}$
where $g_{n}\in\\{2,3..n\\}$. Thus, for a given $n$ there exists $n-1$
different PORAC games. For $g_{n}=2$, the standard PORAC in [30] can be
recovered. As argued in [30], the PO condition in an operational theory is
equivalently represented in an ontological model of the said operational
theory satisfying preparation non-contextuality. We explicitly derived the
classical preparation noncontextual bound on the success probability in our
generalized PORAC for any arbitrary $n$ and $g_{n}$. Further, we demonstrated
the quantum supremacy over the preparation noncontextual model.

By considering the prepare-and-measure version of PORAC, we explicitly derived
the optimal quantum advantage for $3$-bit PORAC with $g_{3}=3$, and for
$4$-bit cases with $g_{4}=3$ and $g_{4}=4$. For arbitrary $n\geq 5$ we
provided the explicit derivation of optimal quantum success probability for
the class of PORAC when $g_{n}=n$. However, following the procedure developed
for $n=3$ and $4$, quantum supremacy can be demonstrated for any arbitrary
$g_{n}>2$ for any given $n$. This requires a lengthy analytical calculation or
considerably high computational resources. This calls for further study.

We conclude by stating a couple of open questions in connection to our work.
Our generalized PORAC $\mathbb{G}_{n,g_{n}}$ with $n\geq 3$ and $g_{n}\geq 3$
can serve as device-independent dimension witness of Hilbert space. For
example, in the PORAC $\mathbb{G}_{3,3}$, the optimal quantum value of the
success probability is obtained when Alice and Bob share a pair of two-qubit
entangled states. If they use a two-qubit entangled state, then there will be
an upper bound on the quantum success probability, and any value that exceeds
that upper bound certifies the dimension of the Hilbert space. This could be
an interesting line of study. Our work can be further generalized for
$d$-level PORAC [17]. Such a generalization could be an exciting avenue for
future research.

##  Appendix A Proof of Theorem 1 for $n=3$

Here we provide the detailed derivation of _Theorem 1_. The proof is built
upon the approach developed in [30]. Let us first consider the $3$-bit PORAC
with $g_{3}=3$ and provide a detailed derivation of the average success
probability in a preparation noncontextual model corresponding to the parity-
set $\mathbb{G}_{3,3}$.

By using Bayes’ theorem, and by noting that the distribution over inputs $x$
is uniform, Eq. (14) in the main text can be expressed as a constraint on
$p(m|P_{x})$ so that

$\forall s\in\mathbb{G}_{3,3}\
:\sum_{x|x.s=0}p(m|P_{x})=\sum_{x|x.s=1}p(m|P_{x}).$ (44)

Our aim is to show that $p(m|P_{x})$ can be expanded in the following form

$p(m|P_{x})=p(0)\alpha^{0}(m)+\sum_{\begin{subarray}{c}q_{i},q_{j}=1\\\
q_{i}\neq
q_{j}\end{subarray}}^{3}p(q_{i}q_{j})\sum_{l,l^{\prime}=0}^{1}\Big{[}\alpha^{1}_{q_{i},l,q_{j},l^{\prime}}\
\delta_{x_{q_{i}},l}\ \delta_{x_{q_{j}},l^{\prime}}\Big{]}$ (45)

where we lebel the Fourier coefficient $\alpha^{0}(m)$ for the all-zero
string, and for the string with entry $1$ at position $q_{i}$ and/or $q_{j}$,
we label the Fourier coefficient as $\alpha^{1}_{q_{i},q_{j}}(m)$. The
quantity $p(q_{i}q_{j})$ signifies the normalised probability distribution
over $q_{i},q_{j}\in\\{0,...,3\\}$ with $q_{i}\neq q_{j}$. If $q_{i}=q_{j}=0$,
Alice sends a message from the distribution function $\alpha^{0}(m)$. On the
other hand, upon obtaining $q_{i}(q_{j})\in_{\begin{subarray}{c}q_{i}\neq
q_{j}\end{subarray}}\\{1,2,3\\}$, she sends the message from the distributions
$\alpha^{1}_{q_{i},l,q_{j},l^{\prime}}$ with $l,l^{\prime}=\\{0,1\\}$
depending on the values of the $q_{i}^{th}$ and $q_{j}^{th}$ bits of $x$.

In optimal decoding, Bob gets no information about $x$ if $q_{i},q_{j}=0$,
hence $p(0)=0$. In order to optimize the amount of information, Bob should be
able to distinguish the distributions $\alpha^{1}_{q_{i},l,q_{j},l^{\prime}}$,
i.e., their mutual supports need to be disjoint. Given the message $m$, Bob
must determine from which distribution it was sampled. Therefore, when
$q_{i}=y$ and $q_{j}=y^{\prime}$ where $y\neq y^{\prime}$ with
$y,y^{\prime}\in\\{1,2,3\\}$, Bob always finds winning condition $b=x_{q_{i}}$
and $b=x_{q_{j}}$ respectively. However, if either $q_{i}\neq y$ or $q_{j}\neq
y^{\prime}$, or both, Bob knows nothing about $x_{q_{i}}$ or $x_{q_{j}}$ and
thus he only randomly guesses the bit with probability $1/2$.

For the parity-set $\mathbb{G}_{3,3}$, let Alice and Bob agree beforehand that
Alice will communicate the first $2$-bits. Then, for $y,y^{\prime}=\\{1,2\\}$,
each occurring with probability $1/3$, Bob can predict the outcome with
certainty. For the third bit, Bob can only randomly guess it with the
probability of $1/2$. The average success probability in a preparation
noncontextual model can then be derived as
$(\mathcal{P}_{3}^{3})_{pnc}=\frac{1}{3}\times
2+\frac{1}{3}\times\frac{1}{2}=\frac{5}{6}$. Instead of the first $2$-bits,
Alice can send any two random bits, but the success probability remains
unchanged.

To prove Alice can at most send two bits of information, we now provide the
detailed derivation of Eq. (45). Let us consider $\delta\in\\{0,1\\}^{3}$ and
define a function $\eta_{\delta}(x)=(-1)^{x.\delta}$ which maps
$\\{0,1\\}^{3}$ to $\\{1,-1\\}$. The function obeys
$\sum_{x}\bar{\eta}_{\delta^{\prime}}(x)\eta_{\delta}(x)=2^{3}\delta_{\delta^{\prime},\delta}$,
where $\\{\eta_{\delta}(x)\\}$ forms a complete set of orthogonal vectors.
Using Fourier expansion of $p(m|P_{x})$, we can write

$p(m|P_{x})=\sum_{\delta\in\\{0,1\\}^{3}}\alpha_{\delta}(m)\eta_{\delta}(x)$
(46)

where $\alpha_{\delta}(m)$ are the Fourier coefficients can be written as

$\alpha_{\delta}(m)=\frac{1}{2^{3}}\sum_{x\in\\{0,1\\}^{3}}\left[\sum_{x|x.s=0}p(m|P_{x})-\sum_{x|x.s=1}p(m|P_{x})\right].$
(47)

Combining the parity-oblivous condition in Eq. (44), we find

$\forall s\ \in\ \mathbb{G}_{3,3}:\alpha_{s}(m)=0.$ (48)

The parity-set $\mathbb{G}_{3,3}$ contain only one element $s=111$. Now, the
strings with hamming weight $0$ to $2$ in turn leads to strings $r$ for which
$\alpha_{\delta}(m)\neq 0$. Among them, one is the all-zero string. For the
rest of the strings, $1$ appears at position $q_{i},q_{j}\in\\{1,...,3\\}$
with $q_{i}\neq q_{j}$ and all other entries of $\delta$ are zero. For the
all-zero string we lebel the Fourier coefficient $\alpha^{0}(m)$, and for the
string with entry $1$ at position $q_{i}$ and/or $q_{j}$, we label the Fourier
coefficient as $\alpha^{1}_{q_{i},q_{j}}(m)$. Hence, under the parity-
oblivious constraint, Eq. (46) reduces to

$\displaystyle
p(m|P_{x})=\alpha^{0}(m)+\sum_{\begin{subarray}{c}q_{i},q_{j}=1\\\
{q_{i}}\neq{q_{j}}\end{subarray}}^{3}\alpha^{1}_{q_{i},q_{j}}(m)(-1)^{x_{q_{i}}+x_{q_{j}}}$
(49)

where $\alpha^{1}_{{q_{i}},{q_{j}}}=\alpha^{1}_{{q_{i}}}\alpha^{1}_{{q_{j}}}$
as $q_{i}^{\text{th}}$ bit and $q_{j}^{\text{th}}$ bit are independent in the
bit string $x$.

Next, inserting
$(-1)^{x_{q_{i}}+x_{q_{j}}}=\sum_{l^{\prime},l=0}^{1}(-1)^{l+l^{\prime}}\delta_{x_{q_{i}},l}\delta_{x_{q_{j}},l^{\prime}}$
and
$1=\sum_{l^{\prime},l=0}^{1}\delta_{x_{q_{i}},l}\delta_{x_{q_{j}},l^{\prime}}$
into Eq. (49), we can write

$\displaystyle p(m|P_{x})=a_{0}(m)$ $\displaystyle+$
$\displaystyle\sum_{\begin{subarray}{c}q_{i},q_{j}=1\\\ q_{i}\neq
q_{j}\end{subarray}}^{3}\Big{[}a_{q_{i},0,q_{j},0}\delta_{x_{q_{i}},0}\delta_{x_{q_{j}},0}+a_{q_{i},0,q_{j},1}\delta_{x_{q_{i}},0}\delta_{x_{{q_{j}}},1}$
(50) $\displaystyle+$ $\displaystyle
a_{{q_{i}},1,{q_{j}},0}\delta_{x_{q_{i}},1}\delta_{x_{{q_{j}}},0}+a_{{q_{i}},1,{q_{j}},1}\delta_{x_{q_{i}},1}\delta_{x_{q_{j}},1}\Big{]}.$

where we have defined nonnegative coefficients as

$\displaystyle a_{q_{i},0,{q_{j}},0}=2\alpha^{1}_{q_{i},0,q_{j},0}(m),\ \ $
$\displaystyle\text{if sgn}(\alpha^{1}_{q_{i},0}(m))\geq 0\ ,\text{
sgn}(\alpha^{1}_{q_{j},0}(m))\geq 0$ $\displaystyle
a_{q_{i},1,{q_{j},1}}=2\alpha^{1}_{q_{i},1,q_{j},1}(m),\ \ $
$\displaystyle\text{if sgn}(\alpha^{1}_{q_{i},1}(m))<0\ ,\text{
sgn}(\alpha^{1}_{q_{j},1}(m))<0$ $\displaystyle
a_{q_{i},0,{q_{j}},1}=-2\alpha^{1}_{q_{i},0,q_{j},1}(m),\ \ $
$\displaystyle\text{if sgn}(\alpha^{1}_{q_{i},0}(m))\geq 0\ ,\text{
sgn}(\alpha^{1}_{q_{j},1}(m))<0$ $\displaystyle
a_{q_{i},1,{q_{j}},0}=-2\alpha^{1}_{q_{i},1,q_{j},0}(m),\ \ $
$\displaystyle\text{if sgn}(\alpha^{1}_{q_{i},1}(m))<0\ ,\text{
sgn}(\alpha^{1}_{q_{j},0}(m))\geq 0.$

It remains to prove that the coefficient $a_{0}(m)$ is also positive semi-
definite. For this, we define a $3$-bit string $z(m)$ as

$z_{q_{i}}(m)z_{q_{j}}(m)\equiv\begin{cases}00\ \ \ \ \text{if
sgn}(\alpha^{1}_{q_{i},0}(m))\geq 0\ ,\text{ sgn}(\alpha^{1}_{q_{j},0}(m))\geq
0;\\\ 11\ \ \ \ \text{if sgn}(\alpha^{1}_{q_{i},1}(m))<0\ ,\text{
sgn}(\alpha^{1}_{q_{j},1}(m))<0;\ \ \ \ \ \\\ 01\ \ \ \ \text{if
sgn}(\alpha^{1}_{q_{i},0}(m))\geq 0\ ,\text{
sgn}(\alpha^{1}_{q_{j},1}(m))<0;\\\ 10\ \ \ \ \text{if
sgn}(\alpha^{1}_{q_{i},1}(m))<0\ ,\text{ sgn}(\alpha^{1}_{q_{j},0}(m))\geq
0.\end{cases}$ (52)

where $z_{q_{i}}(m)z_{q_{j}}(m)$ encodes the signs of the Fourier
coefficients. It follows from this definition that

$\displaystyle
a_{q_{i},0,q_{j},0}\delta_{z_{q_{i}}(m),0}\delta_{z_{q_{j}}(m),0}+a_{q_{i},0,q_{j},1}\delta_{z_{q_{i}}(m),0}\delta_{z_{q_{j}}(m),1}+a_{q_{i},1,q_{j},0}\delta_{z_{q_{i}}(m),1}\delta_{z_{q_{j}}(m),0}+a_{q_{i},1,q_{j},1}\delta_{z_{q_{i}}(m),1}\delta_{z_{q_{j}}(m),1}=0$

and consequently

$\forall\ q_{i},\ q_{j},\ \ \ p(m|P_{z(m)})=a_{0}(m),$ (54)

which establishes that $a_{0}(m)\geq 0$. Using normalization of $p(m|P_{x})$
together with Eq. (50) we obtain

$\forall\ x,\
\sum_{m}p(m|P_{x})=\sum_{m}a_{0}(m)+\sum_{\begin{subarray}{c}q_{i},q_{j}=1\\\
q_{i}\neq
q_{j}\end{subarray}}^{3}\sum_{m}a_{q_{i},x_{q_{i}},q_{j},x_{q_{j}}}(m)=1,$
(55)

Noting the fact that $\sum_{m}a_{{q_{i}},x_{q_{i}}q_{j},x_{q_{j}}}$ is
independent of $x_{q_{i}}$ and $x_{q_{j}}$, i.e.,
$\sum_{m}a_{{q_{i}},x_{q_{i}}q_{j},x_{q_{j}}}=\sum_{m}a_{q_{j},{q_{j}}}(m)$,
and we introduce the following re-labeling.

$\displaystyle p(0)=\sum_{m}a_{0}(m),\ \ \ \
p(q_{i},q_{j})=\sum_{m}a_{q_{j},{q_{j}}}(m),\ \ \ \ $
$\displaystyle\alpha^{0}(m)=\frac{a_{0}(m)}{p(0)},\ \ \ \
\alpha^{1}_{q_{i},l,q_{j},l^{\prime}}(m)=\frac{a_{q_{i},l,q_{j},l^{\prime}}(m)}{p(q_{i},q_{j})}$
(56)

Here, $p(q_{i},q_{j})$ is the probability distribution over
$q_{i},q_{j}\in\\{0,...,3\\}$. $\alpha^{0}(m)$ is the probability distribution
over $m$ and for each $q_{i},q_{j}\in\\{0,...,3\\}$ and
$l,l^{\prime}\in\\{0,1\\}$, $\alpha^{1}_{q_{i},l,q_{j},l^{\prime}}(m)$ is a
probability distribution over $m$. Hence, we can write Eq. (50) as

$p(m|P_{x})=p(0)\alpha^{0}(m)+\sum_{\begin{subarray}{c}q_{i},q_{j}=1\\\
q_{i}\neq
q_{j}\end{subarray}}^{3}p(q_{i}q_{j})\sum_{l,l^{\prime}=0}^{1}\alpha^{1}_{q_{i},l,q_{j},l^{\prime}}(m)\delta_{x_{q_{i}},l}\delta_{x_{q_{j}},l^{\prime}}$
(57)

which is the Eq. (45) that we promised to prove.

##  Appendix B Proof of Theorem 1 for arbitrary $n$

For $n$-bit PORAC, Alice holds $x=x_{1}x_{2}...x_{n}\in\\{0,1\\}^{n}$ with
$p_{A}(x)=1/2^{n}$, and Bob holds $y\in\\{1,2,...,n\\}$ with $p_{B}(y)=1/n$.
Parity-oblivious condition demands that the classical message $m$ sent from
Alice to Bob must satisfy

$\forall s\in\mathbb{G}_{n,g_{n}}\
:\sum_{x|x.s=0}p(P_{x}|m)=\sum_{x|x.s=1}p(P_{x}|m)$ (58)

where $g_{n}=\\{2,3,...,n\\}$ for any arbitrary $n$.

By employing Bayes’ theorem, and considering that the distribution over inputs
$x$ is uniform, Eq. (58) can be expressed as a constraint on $p(m|P_{x})$ as

$\forall s\in\mathbb{G}_{n,g_{n}}\
:\sum_{x|x.s=0}p(m|P_{x})=\sum_{x|x.s=1}p(m|P_{x}).$ (59)

The expression $p(m|P_{x})$ implies

$p(m|P_{x})=p(0)\alpha^{0}(m)+\sum_{q=1}^{n}p(q)\prod_{q=1}^{n}\sum_{l_{q}=0}^{1}\Big{[}\alpha^{1}_{q,l_{q}}\delta_{x_{q},l_{q}}\Big{]}$
(60)

where $p(q)$ signifies the normalised probability distribution over
$\\{0,...,n\\}$ with $q=(q_{1},...,q_{g_{n}-1})$. If $\forall n,\
q(q_{1},...,q_{g_{n}-1})=0$, Alice sends a message from the distribution
function $\alpha^{0}(m)$, otherwise she sends from the distributions
$\alpha^{1}_{q,l_{q}}$ upon obtaining $q\in\\{1,...,n\\}$ where $l_{q}=0\
\text{or}\ 1$.

Following the similar steps adopted for $g_{3}=3$ case, Fourier coefficients
$\alpha_{\delta}(m)$ can be written as

$\alpha_{\delta}(m)=\frac{1}{2^{n}}\sum_{x\in\\{0,1\\}^{n}}\Big{[}\sum_{x|x.s=0}p(m|P_{x})-\sum_{x|x.s=1}p(m|P_{x})\Big{]}.$
(61)

also we have

$\forall s\ \in\ \mathbb{G}_{n,g_{n}}:\alpha_{s}(m)=0.$ (62)

The strings with hamming weight $0$ to $g_{n}-1$ in turn leads to strings
$\delta$ for which $\alpha_{\delta}(m)\neq 0$. Among them, one is the all-zero
string for which we denote the Fourier coefficient as $\alpha^{0}(m)$. For the
rest of the strings, $1$ appears at position $q\in\\{1,...,n\\}$ with all
other entries of $\delta$ are zero. In such cases, we label the Fourier
coeffient as $\alpha^{1}_{q}(m)$. Hence, under the parity-oblivious
constraint, $p(m|P_{x})$ reduces to

$p(m|P_{x})=\alpha^{0}(m)+\sum_{q=1}^{n}\alpha^{1}_{q}(m)(-1)^{\oplus_{2}x_{q}}$
(63)

where in $\alpha^{1}_{q}=\prod_{q=1}^{n}\alpha^{1}_{q}$, as all bits are
independent of the bit string $x$.

Now, insurting
$(-1)^{\oplus_{2}x_{q}}=\sum_{l_{q}=0}^{1}(-1)^{\oplus_{2}l_{q}}\delta_{x_{q},l_{q}}$
and $1=\sum_{l_{q}=0}^{1}\delta_{x_{q},l_{q}}$ into Eq. (63), we can write the
expression as

$p(m|P_{x})=a_{0}(m)+\prod_{q=1}^{n}\sum_{l_{q}=0}^{1}\Big{[}a_{q,l_{q}}\delta_{x_{q},l_{q}}\Big{]}.$
(64)

where we have defined nonnegative coefficients as

$\displaystyle a_{q,l_{q}}=(-1)^{l_{q}}2\alpha^{1}_{q,l_{q}}(m)$ (65)

depending on the values of $\text{sgn}(\alpha^{1}_{q,l_{q}}(m))\geq 0\ $, or
$\text{sgn}(\alpha^{1}_{q,l_{q}}(m))<0$, and $l_{q}\in\\{0,1\\}$.

We have implicitly defined a constant $a_{0}(m)$, where it remains to prove
that $a_{0}(m)$ is positive semidefinite. To prove $a_{0}(m)$ as nonnegative,
let a $n$-bit string $z(m)$ defined as

$\displaystyle
z_{q_{1}}(m)z_{q_{2}}(m)...z_{q_{g_{n}-1}}(m)\in\\{0,1\\}^{g_{n}-1}\ \ \
\text{if sgn}(\alpha^{1}_{q,l_{q}=0}(m))\geq 0,\ \ \text{
sgn}(\alpha^{1}_{q,l_{q}=1}(m))<0,$ (66)

where $z_{q}(m)$ encodes the signs of the Fourier coefficients. Then it
follows from this definition that

$\prod_{q=1}^{n}\sum_{l_{q}=0}^{1}\Big{[}a_{q,l_{q}}\delta_{x_{q},l_{q}}\Big{]}=0$
(67)

and consequently that

$\forall\ q,\ \ \ p(m|P_{z(m)})=a_{0}(m),$ (68)

which establishes that $a_{0}(m)\geq 0$.

Using normalization together with Eq. (64) to obtain:

$\forall\ x,\
\sum_{m}p(m|P_{x})=\sum_{m}a_{0}(m)+\prod_{q=1}^{n}\sum_{l_{q}=0}^{1}\sum_{m}a_{q,l_{q}}\delta_{x_{q},l_{q}}(m)=1,$
(69)

Introducing the re-labeling as

$\displaystyle p(0)=\sum_{m}a_{0}(m),\ \ \ \ \ \ p(q)=\sum_{m}a_{q}(m);\ \ \ \
\ \ \alpha^{0}(m)=\frac{a_{0}(m)}{p(0)},\ \
\alpha^{1}_{q,l_{q}}(m)=\frac{a_{q,l_{q}}(m)}{p(q)}.$

here, $p(q)$ can be interpreted as a probability distribution over
$q\in\\{0,...,n\\}$, $\alpha^{0}(m)$ is a probability distribution over $m$
when $q\equiv(q_{1},...,q_{g_{n}-1})=0$. Also for each
$q\equiv(q_{1},...,q_{g_{n}-1})\in\\{1,...,n\\}$ (with $q_{k}\neq
q_{k^{\prime}}$, and $k,k^{\prime}=\\{1,2,...,n\\}$) and $l_{q}\in\\{0,1\\}$,
$\alpha^{1}_{q,l_{q}}(m)$ is a probability distribution over $m$. Hence, using
Eq. (B) we can write Eq. (64) as

$p(m|P_{x})=p(0)\alpha^{0}(m)+\sum_{q=1}^{n}p(q)\prod_{q=1}^{n}\sum_{l_{q}=0}^{1}\alpha^{1}_{q,l_{q}}\delta_{x_{q},l_{q}}.$
(70)

which is the Eq. (60).

Thus, the parity-oblivious task can be interpreted as follows: Alice samples
$q$ from $p(q)$, if she obtains $q=0$ she sends a message sampled from
$\alpha^{0}(m)$ whereas if she obtains $q\in\\{1,...,n\\},$ she sends a
message distributions from $\alpha^{1}_{q,l_{q}}$ depending on the value of
the $q^{\text{th}}$ bit of $x$. To achieve the optimal value of
$\mathcal{P}_{n}$ in Eq. (1), Bob gets no information about $x$ if $q=0$,
Hence $p(0)=0$. In order to optimize the amount of information the
distributions $\alpha^{1}_{q,l_{q}}$ have to be distinguishable for Bob. Given
any value of $m$, Bob can certainly determine from which distribution it was
sampled, i.e., their mutual supports need to be disjoint. Therefore, when
$q=y$, Bob always finds $b=x_{q}$. However, if $q\neq y$ Bob knows nothing
about $x_{q}$ and thus only randomly guesses the bit with probability $1/2$.

For the parity-set $\mathbb{G}_{n,g_{n}}$, let Alice and Bob agreed beforehand
that Alice will reveal the first $(g_{n}-1)$-bits. For
$y=\\{1,...,g_{n}-1\\}$, each occurring with probability $1/n$, Bob can
predict the outcome with certainty. And, for rest of $(n-g_{n}+1)$ bits, Bob
can only randomly guess the bit with probability $1/2$. The average value of
$(\mathcal{P}_{n}^{g_{n}})_{pnc}$ is then

$\displaystyle(\mathcal{P}_{n}^{g_{n}})_{pnc}=(g_{n}-1)\times\frac{1}{n}+(n-g_{n}+1)\times\frac{1}{2}=\frac{(g_{n}+n-1)}{2n}.$
(71)

which is claimed in Eq. (15).

##  Appendix C Detailed derivation of optimal quantum success probability for
$g_{4}=4$

In the $4$-bit quantum PORAC game for the parity-set $\mathbb{G}_{4,4}$, Alice
encodes her inputs into sixteen quantum states $\rho_{x}$ and sends it to Bob.
The decoding measurement for Bob is $\\{\Pi_{4,y}^{0},\Pi_{4,y}^{1}\\}$ with
$y=1,2,3,4$. The quantum success probability using Eq. (9) from the main text
can be explicitly written as

$\displaystyle(\mathcal{P}_{4}^{g_{4}=4})_{Q}=\dfrac{1}{2}+\dfrac{1}{64}$
$\displaystyle\mathrm{tr}$
$\displaystyle[\rho_{0000}(\Pi_{4,1}^{0}+\Pi_{4,2}^{0}+\Pi_{4,3}^{0}+\Pi_{4,4}^{0})-\rho_{1111}(\Pi_{4,1}^{0}+\Pi_{4,2}^{0}+\Pi_{4,3}^{0}+\Pi_{4,4}^{0})+\rho_{0011}(\Pi_{4,1}^{0}+\Pi_{4,2}^{0}-\Pi_{4,3}^{0}-\Pi_{4,4}^{0})$
(72) $\displaystyle-$
$\displaystyle\rho_{1100}(\Pi_{4,1}^{0}+\Pi_{4,2}^{0}-\Pi_{4,3}^{0}-\Pi_{4,4}^{0})+\rho_{0101}(\Pi_{4,1}^{0}-\Pi_{4,2}^{0}+\Pi_{4,3}^{0}-\Pi_{4,4}^{0})-\rho_{1010}(\Pi_{4,1}^{0}-\Pi_{4,2}^{0}+\Pi_{4,3}^{0}-\Pi_{4,4}^{0})$
$\displaystyle+$
$\displaystyle\rho_{0110}(\Pi_{4,1}^{0}-\Pi_{4,2}^{0}-\Pi_{4,3}^{0}+\Pi_{4,4}^{0})-\rho_{1001}(\Pi_{4,1}^{0}-\Pi_{4,2}^{0}-\Pi_{4,3}^{0}+\Pi_{4,4}^{0})+\rho_{0001}(\Pi_{4,1}^{0}+\Pi_{4,2}^{0}+\Pi_{4,3}^{0}-\Pi_{4,4}^{0})$
$\displaystyle-$
$\displaystyle\rho_{1110}(\Pi_{4,1}^{0}+\Pi_{4,2}^{0}+\Pi_{4,3}^{0}-\Pi_{4,4}^{0})+\rho_{0010}(\Pi_{4,1}^{0}+\Pi_{4,2}^{0}-\Pi_{4,3}^{0}+\Pi_{4,4}^{0})-\rho_{1101}(\Pi_{4,1}^{0}+\Pi_{4,2}^{0}-\Pi_{4,3}^{0}+\Pi_{4,4}^{0})$
$\displaystyle+$
$\displaystyle\rho_{0100}(\Pi_{4,1}^{0}-\Pi_{4,2}^{0}+\Pi_{4,3}^{0}+\Pi_{4,4}^{0})-\rho_{1011}(\Pi_{4,1}^{0}-\Pi_{4,2}^{0}+\Pi_{4,3}^{0}+\Pi_{4,4}^{0})+\rho_{0111}(\Pi_{4,1}^{0}-\Pi_{4,2}^{0}-\Pi_{4,3}^{0}-\Pi_{4,4}^{0})$
$\displaystyle-$
$\displaystyle\rho_{1000}(\Pi_{4,1}^{0}-\Pi_{4,2}^{0}-\Pi_{4,3}^{0}-\Pi_{4,4}^{0})].$

which can further be re-written as

$\displaystyle(\mathcal{P}_{4}^{g_{4}=4})_{Q}=\dfrac{1}{2}+\dfrac{1}{128}$
$\displaystyle\mathrm{tr}$
$\displaystyle[(\rho_{0000}-\rho_{1111}+\rho_{0011}-\rho_{1100}+\rho_{0101}-\rho_{1010}+\rho_{0110}-\rho_{1001})B_{4,1}$
$\displaystyle+$
$\displaystyle(\rho_{0000}-\rho_{1111}+\rho_{0011}-\rho_{1100}-\rho_{0101}+\rho_{1010}-\rho_{0110}+\rho_{1001})B_{4,2}$
$\displaystyle+$
$\displaystyle(\rho_{0000}-\rho_{1111}-\rho_{0011}+\rho_{1100}+\rho_{0101}-\rho_{1010}-\rho_{0110}+\rho_{1001})B_{4,3}$
$\displaystyle+$
$\displaystyle(\rho_{0000}-\rho_{1111}-\rho_{0011}+\rho_{1100}-\rho_{0101}+\rho_{1010}+\rho_{0110}-\rho_{1001})B_{4,4}$
$\displaystyle+$
$\displaystyle(\rho_{0001}-\rho_{1110}+\rho_{0010}-\rho_{1101}+\rho_{0100}-\rho_{1011}+\rho_{0111}-\rho_{1000})B_{4,1}$
$\displaystyle+$
$\displaystyle(\rho_{0001}-\rho_{1110}+\rho_{0010}-\rho_{1101}-\rho_{0100}+\rho_{1011}-\rho_{0111}+\rho_{1000})B_{4,2}$
$\displaystyle+$
$\displaystyle(\rho_{0001}-\rho_{1110}-\rho_{0010}+\rho_{1101}+\rho_{0100}-\rho_{1011}-\rho_{0111}+\rho_{1000})B_{4,3}$
$\displaystyle-$
$\displaystyle(\rho_{0001}-\rho_{1110}-\rho_{0010}+\rho_{1101}-\rho_{0100}+\rho_{1011}+\rho_{0111}-\rho_{1000})B_{4,4}]$

Similar to the case of $\mathbb{G}_{3,3}$, to obtain optimal quantum success
probability, we first analyze the term
$Tr[(\rho_{0000}-\rho_{1111}+\rho_{0011}-\rho_{1100}+\rho_{0101}-\rho_{1010}+\rho_{0110}-\rho_{1001})B_{4,1}]$.
Note that to get maximum value $\rho_{0000},\rho_{0011},\rho_{0101}$ and
$\rho_{0110}$ has to be the eigenstates of $B_{4,1}$ with eigenvalue $+1$, and
$\rho_{1100},\rho_{1010},\rho_{1001}$ and $\rho_{1111}$ has to be eigenstates
of $B_{4,1}$ with eigenvalue $-1$. Since we consider three-qubit system,
$\rho_{x}$ with $s.x=0$ are orthogonal pure states implying
$\sum_{x|s.x=0}\rho_{x}=\mathrm{I}\otimes\mathrm{I}\otimes\mathrm{I}$. Similar
arguments can be made for the second, third and forth term with $B_{4,2}$,
$B_{4,3}$ and $B_{4,4}$. Consequently, the other four terms with $s.x=1$ will
also follow same argument such that
$\rho_{0001},\rho_{1110},\rho_{0010},\rho_{1101},\rho_{0100},\rho_{1011},\rho_{0111}$
and $\rho_{1000}$ are also orthogonal pure states, i.e.,
$\sum_{x|s.x=1}\rho_{x}=\mathrm{I}\otimes\mathrm{I}\otimes\mathrm{I}$. This
satisfies the PO condition.

Hence, leading us to define three-qubit observables of the form

$\displaystyle A_{4,1}$ $\displaystyle=$
$\displaystyle\rho_{0000}-\rho_{1111}+\rho_{0011}-\rho_{1100}+\rho_{0101}-\rho_{1010}+\rho_{0110}-\rho_{1001}$
$\displaystyle A^{\prime}_{4,1}$ $\displaystyle=$
$\displaystyle\rho_{0000}-\rho_{1111}+\rho_{0011}-\rho_{1100}-\rho_{0101}+\rho_{1010}-\rho_{0110}+\rho_{1001}$
$\displaystyle A^{\prime\prime}_{4,1}$ $\displaystyle=$
$\displaystyle\rho_{0000}-\rho_{1111}-\rho_{0011}+\rho_{1100}+\rho_{0101}-\rho_{1010}-\rho_{0110}+\rho_{1001}$
$\displaystyle\tilde{A}_{4,1}$ $\displaystyle=$
$\displaystyle\rho_{0000}-\rho_{1111}-\rho_{0011}+\rho_{1100}-\rho_{0101}+\rho_{1010}+\rho_{0110}-\rho_{1001}$
$\displaystyle A_{4,2}$ $\displaystyle=$
$\displaystyle\rho_{0001}-\rho_{1110}+\rho_{0010}-\rho_{1101}+\rho_{0100}-\rho_{1011}+\rho_{0111}-\rho_{1000}$
(74) $\displaystyle A^{\prime}_{4,2}$ $\displaystyle=$
$\displaystyle\rho_{0001}-\rho_{1110}+\rho_{0010}-\rho_{1101}-\rho_{0100}+\rho_{1011}-\rho_{0111}+\rho_{1000}$
$\displaystyle A^{\prime\prime}_{4,2}$ $\displaystyle=$
$\displaystyle\rho_{0001}-\rho_{1110}-\rho_{0010}+\rho_{1101}+\rho_{0100}-\rho_{1011}-\rho_{0111}+\rho_{1000}$
$\displaystyle\tilde{A}_{4,2}$ $\displaystyle=$
$\displaystyle\rho_{0001}-\rho_{1110}-\rho_{0010}+\rho_{1101}-\rho_{0100}+\rho_{1011}+\rho_{0111}-\rho_{1000}$

Then the quantum success probability in Eq. (C) can be casted as

$\displaystyle(\mathcal{P}_{4}^{g_{4}=4})_{Q}$ $\displaystyle=$
$\displaystyle\dfrac{1}{2}+\dfrac{\mathrm{tr}[\Delta_{4}^{g_{4}=4}]_{Q}}{128}.$
(75)

where the function $\Delta_{4}^{g_{4}=4}$ is given by

$\displaystyle\Delta_{4}^{g_{4}=4}=(A_{4,1}+A_{4,2})B_{4,1}+(\tilde{A}_{4,1}-\tilde{A}_{4,2})B_{4,4}+(A^{\prime}_{4,1}+A^{\prime}_{4,2})B_{4,2}+(A^{\prime\prime}_{4,1}+A^{\prime\prime}_{4,2})B_{4,3}.$
(76)

Eq. (75) and Eq. (76) are the Eq. (29) and Eq. (30) in the main text
respectively .

##  Appendix D Detailed derivation of optimal quantum success probability for
$4$-bit PORAC with $g_{4}=3$

For $\mathbb{G}_{4,3}$, Alice prepares sixteen quantum states $\rho_{x}$ in
quantum theory and communicates to Bob. Next, after receiving the states Bob
performs projective measurements $\\{\Pi_{4,y}^{0},\Pi_{4,y}^{1}\\}$ with
$y=1,2,3,4$. The quantum success probability using Eq. (9) from the main text
can be explicitly written as

$\displaystyle(\mathcal{P}_{4}^{g_{4}=3})_{Q}=\dfrac{1}{2}$ $\displaystyle+$
$\displaystyle\dfrac{1}{64}\mathrm{tr}[\rho_{0000}(\Pi_{4,1}^{0}+\Pi_{4,2}^{0}+\Pi_{4,3}^{0}+\Pi_{4,4}^{0})-\rho_{1111}(\Pi_{4,1}^{0}+\Pi_{4,2}^{0}+\Pi_{4,3}^{0}+\Pi_{4,4}^{0})$
(77) $\displaystyle+$
$\displaystyle\rho_{0011}(\Pi_{4,1}^{0}+\Pi_{4,2}^{0}-\Pi_{4,3}^{0}-\Pi_{4,4}^{0})-\rho_{1100}(\Pi_{4,1}^{0}+\Pi_{4,2}^{0}-\Pi_{4,3}^{0}-\Pi_{4,4}^{0})$
$\displaystyle+$
$\displaystyle\rho_{0101}(\Pi_{4,1}^{0}-\Pi_{4,2}^{0}+\Pi_{4,3}^{0}-\Pi_{4,4}^{0})-\rho_{1010}(\Pi_{4,1}^{0}-\Pi_{4,2}^{0}+\Pi_{4,3}^{0}-\Pi_{4,4}^{0})$
$\displaystyle+$
$\displaystyle\rho_{0110}(\Pi_{4,1}^{0}-\Pi_{4,2}^{0}-\Pi_{4,3}^{0}+\Pi_{4,4}^{0})-\rho_{1001}(\Pi_{4,1}^{0}-\Pi_{4,2}^{0}-\Pi_{4,3}^{0}+\Pi_{4,4}^{0})$
$\displaystyle+$
$\displaystyle\rho_{0001}(\Pi_{4,1}^{0}+\Pi_{4,2}^{0}+\Pi_{4,3}^{0}-\Pi_{4,4}^{0})-\rho_{1110}(\Pi_{4,1}^{0}+\Pi_{4,2}^{0}+\Pi_{4,3}^{0}-\Pi_{4,4}^{0})$
$\displaystyle+$
$\displaystyle\rho_{0010}(\Pi_{4,1}^{0}+\Pi_{4,2}^{0}-\Pi_{4,3}^{0}+\Pi_{4,4}^{0})-\rho_{1101}(\Pi_{4,1}^{0}+\Pi_{4,2}^{0}-\Pi_{4,3}^{0}+\Pi_{4,4}^{0})$
$\displaystyle+$
$\displaystyle\rho_{0100}(\Pi_{4,1}^{0}-\Pi_{4,2}^{0}+\Pi_{4,3}^{0}+\Pi_{4,4}^{0})-\rho_{1011}(\Pi_{4,1}^{0}-\Pi_{4,2}^{0}+\Pi_{4,3}^{0}+\Pi_{4,4}^{0})$
$\displaystyle+$
$\displaystyle\rho_{0111}(\Pi_{4,1}^{0}-\Pi_{4,2}^{0}-\Pi_{4,3}^{0}-\Pi_{4,4}^{0})-\rho_{1000}(\Pi_{4,1}^{0}-\Pi_{4,2}^{0}-\Pi_{4,3}^{0}-\Pi_{4,4}^{0})].$

Considering $\Pi_{4,y}^{0}=(\textbf{1}+B_{4,y})/2$, Eq. (77) can be written as

$\displaystyle(\mathcal{P}_{4}^{g_{4}=3})_{Q}=\dfrac{1}{2}$ $\displaystyle+$
$\displaystyle\dfrac{1}{64\times
2}\mathrm{tr}[(\rho_{0000}-\rho_{1111}+\rho_{0011}-\rho_{1100})(B_{4,1}+B_{4,2})+(\rho_{0000}-\rho_{1111}-\rho_{0011}+\rho_{1100})(B_{4,3}+B_{4,4})$
(78) $\displaystyle+$
$\displaystyle(\rho_{0101}-\rho_{1010}+\rho_{0110}-\rho_{1001})(B_{4,1}-B_{4,2})+(\rho_{0101}-\rho_{1010}-\rho_{0110}+\rho_{1001})(B_{4,3}-B_{4,4})$
$\displaystyle+$
$\displaystyle(\rho_{0001}-\rho_{1110}+\rho_{0010}-\rho_{1101})(B_{4,1}+B_{4,2})+(\rho_{0001}-\rho_{1110}-\rho_{0010}+\rho_{1101})(B_{4,3}-B_{4,4})$
$\displaystyle+$
$\displaystyle(\rho_{0100}-\rho_{1011}+\rho_{0111}-\rho_{1000})(B_{4,1}-B_{4,2})+(\rho_{0100}-\rho_{1011}-\rho_{0111}+\rho_{1000})(B_{4,3}+B_{4,4})].$

Similar to the $\mathbb{G}_{3,3}$ case, let us first analyze the term
$\mathrm{tr}[(\rho_{0000}-\rho_{1111}+\rho_{0011}-\rho_{1100})B_{4,1}]$. To
get maximum value $\rho_{0000}$ and $\rho_{0011}$ has to be the eigenstates of
$B_{4,1}$ with eigenvalue $+1$, and $\rho_{1111}$ and $\rho_{1100}$ has to be
eigenstates of $B_{4,1}$ with eigenvalue $-1$. Since we consider two-qubit
system, $\rho_{0000},\rho_{0011},\rho_{1110}$ and $\rho_{1111}$ are orthogonal
pure states. Similar argument can be made for the second, third and forth
terms. Now, if we consider
$\mathrm{tr}[(\rho_{0001}-\rho_{1110}+\rho_{0010}-\rho_{1101})B_{4,1}]$,
maximization criteria gives $\rho_{0001},\rho_{0010},\rho_{1110}$ and
$\rho_{1101}$ are also orthogonal pure states. The same argument holds for
last three terms. This leads us to define two-qubit observables of the form

$\displaystyle A_{4,1}$ $\displaystyle=$
$\displaystyle\rho_{0000}-\rho_{1111}+\rho_{0011}-\rho_{1100};\ \ \
A_{4,3}=\rho_{0001}-\rho_{1110}+\rho_{0010}-\rho_{1101}$ $\displaystyle
A^{\prime}_{4,1}$ $\displaystyle=$
$\displaystyle\rho_{0000}-\rho_{1111}-\rho_{0011}+\rho_{1100};\ \ \
A^{\prime}_{4,3}=\rho_{0001}-\rho_{1110}-\rho_{0010}+\rho_{1101}$
$\displaystyle A_{4,2}$ $\displaystyle=$
$\displaystyle\rho_{0101}-\rho_{1010}+\rho_{0110}-\rho_{1001};\ \ \
A_{4,4}=\rho_{0100}-\rho_{1011}+\rho_{0111}-\rho_{1000}$ (79)
$\displaystyle{A}^{\prime}_{4,2}$ $\displaystyle=$
$\displaystyle\rho_{0101}-\rho_{1010}-\rho_{0110}+\rho_{1001};\ \ \
{A}^{\prime}_{4,4}=\rho_{0100}-\rho_{1011}-\rho_{0111}+\rho_{1000}$

satisfying
$[A_{4,1},A^{\prime}_{4,1}]=[A_{4,2},A^{\prime}_{4,2}]=[A_{4,3},A^{\prime}_{4,3}]=[A_{4,4},A^{\prime}_{4,4}]=0$.

Thus, the quantum success probability can be written in terms of observables
as

$\displaystyle(\mathcal{P}_{4}^{m_{4}=3})_{Q}=\dfrac{1}{2}+\dfrac{1}{128}$
$\displaystyle\Big{[}$
$\displaystyle(A_{4,1}+A_{4,2}+A_{4,3}+A_{4,4})B_{4,1}+(A_{4,1}-A_{4,2}+A_{4,3}-A_{4,4})B_{4,2}$
(80) $\displaystyle+$
$\displaystyle(A^{\prime}_{4,1}+A^{\prime}_{4,2}+A^{\prime}_{4,3}+A^{\prime}_{4,4})B_{4,3}+(A^{\prime}_{4,1}-A^{\prime}_{4,2}-A^{\prime}_{4,3}+A^{\prime}_{4,4})B_{4,4}\Big{]}$

Since, Alice’s observables can be represented in terms of quantum states, we
can formulate an encoding scheme solely from the construction of the
observables as follows. Let Alice, performs sequential non-selective
degeneracy-breaking measurement on her set of two commuting observables
$A_{4,1}$ and $A^{\prime}_{4,1}$ randomly. Then the quantum states
$\rho_{0000},\rho_{1111},\rho_{0011},$ and $\rho_{1100}$ can be written in
terms of Alice’s observables in the following way,

$\displaystyle\rho_{0000}$ $\displaystyle=$
$\displaystyle\frac{1}{4}(\mathrm{I}+A_{4,1}+A^{\prime}_{4,1}+\tilde{A}_{4,1});\
\ \
\rho_{0011}=\frac{1}{4}(\mathrm{I}+A_{4,1}-A^{\prime}_{4,1}-\tilde{A}_{4,1})$
$\displaystyle\rho_{1100}$ $\displaystyle=$
$\displaystyle\frac{1}{4}(\mathrm{I}-A_{4,1}+A^{\prime}_{4,1}-\tilde{A}_{4,1});\
\ \
\rho_{1111}=\frac{1}{4}(\mathrm{I}-A_{4,1}-A^{\prime}_{4,1}+\tilde{A}_{4,1})$
(81)

where $\tilde{A}_{4,1}$ occurs due to the existence of three mutually
commuting observables two-qubit system.

Similarly, using the commuting set of $A_{4,2}$ and $A^{\prime}_{4,2}$, other
four quantum states $\rho_{1010},\rho_{1001},\rho_{0110},$ and $\rho_{0101}$
can be represented as following

$\displaystyle\rho_{1010}$ $\displaystyle=$
$\displaystyle\frac{1}{4}(\mathrm{I}+A_{4,2}+A^{\prime}_{4,2}+\tilde{A}_{4,2});\
\ \
\rho_{1001}=\frac{1}{4}(\mathrm{I}+A_{4,2}-A^{\prime}_{4,2}-\tilde{A}_{4,2})$
$\displaystyle\rho_{0110}$ $\displaystyle=$
$\displaystyle\frac{1}{4}(\mathrm{I}-A_{4,2}+A^{\prime}_{4,2}-\tilde{A}_{4,2});\
\ \
\rho_{0101}=\frac{1}{4}(\mathrm{I}-A_{4,2}-A^{\prime}_{4,2}+\tilde{A}_{4,2})$
(82)

Consequently, the remaining eight quantum states can be represented in terms
of the two commuting set $[A_{4,3},A^{\prime}_{4,3}]$ and
$[A_{4,4},A^{\prime}_{4,4}]$ as

$\displaystyle\rho_{0001}$ $\displaystyle=$
$\displaystyle\frac{1}{4}(\mathrm{I}+A_{4,3}+A^{\prime}_{4,3}+\tilde{A}_{4,3});\
\ \ \ \ \ \ \
\rho_{0100}=\frac{1}{4}(\mathrm{I}+A_{4,4}+A^{\prime}_{4,4}+\tilde{A}_{4,4})$
$\displaystyle\rho_{1101}$ $\displaystyle=$
$\displaystyle\frac{1}{4}(\mathrm{I}+A_{4,3}-A^{\prime}_{4,3}-\tilde{A}_{4,3});\
\ \ \ \ \ \ \
\rho_{0111}=\frac{1}{4}(\mathrm{I}+A_{4,4}-A^{\prime}_{4,4}-\tilde{A}_{4,4})$
$\displaystyle\rho_{0010}$ $\displaystyle=$
$\displaystyle\frac{1}{4}(\mathrm{I}-A_{4,3}+A^{\prime}_{4,3}-\tilde{A}_{4,3});\
\ \ \ \ \ \ \
\rho_{1000}=\frac{1}{4}(\mathrm{I}-A_{4,4}+A^{\prime}_{4,4}-\tilde{A}_{4,4})$
(83) $\displaystyle\rho_{1110}$ $\displaystyle=$
$\displaystyle\frac{1}{4}(\mathrm{I}-A_{4,3}-A^{\prime}_{4,3}+\tilde{A}_{4,3});\
\ \ \ \ \ \ \
\rho_{1011}=\frac{1}{4}(\mathrm{I}-A_{4,4}-A^{\prime}_{4,4}+\tilde{A}_{4,4})$

such that the parity information remains intact.

Given the parity-set $\mathbb{G}_{4,3}$, from Eqs. (D) and (D), parity
condition for the even parity set of $s=1111$ is calculated as
$\sum_{x|s.x=0}\rho_{x}=\mathbb{I}\otimes\mathbb{I}$. Thus, it is easy to show
that for parity element $s=1111$:
$\sum_{x|s.x=0}\rho_{x}=\sum_{x|s.x=1}\rho_{x}=\mathbb{I}\otimes\mathbb{I}$
i.e., PO condition is naturally satisfied. But for the elements
$s=1110,1101,1011$, and $0111$, four different nontrivial relations between
Alice’s observables can be defined.

For the parity element $s=1110$ the even parity set is
$\\{0000,1100,1010,0110,0001,1101,0111,1011\\}$ and the odd parity set is
$\\{0011,1111,1001,0101,0010,1110,0100,1000\\}$. Using Eqs. (D), (D) and (D),
the observable relation for the even parity set of the element $s=1110$ can be
derived as

$\rho_{0000}+\rho_{1100}+\rho_{1010}+\rho_{0110}+\rho_{0001}+\rho_{1101}+\rho_{0111}+\rho_{1011}=4\mathrm{I}+A^{\prime}_{4,1}+A^{\prime}_{4,2}+A_{4,3}-A^{\prime}_{4,4}$
(84)

Thus, it is straightforward to show that

$s=1110:\ \ \ \ \sum_{x|s.x=0}\rho_{x}=\sum_{x|s.x=1}\rho_{x}\implies
A^{\prime}_{4,1}+A^{\prime}_{4,2}+A_{4,3}-A^{\prime}_{4,4}=0$ (85)

Similarly, from Eqs. (D), (D) and (D) the other three PO conditions are
derived as

$\displaystyle s=1101:\ \ \ \ \ A_{1}-A_{4,2}-A_{4,3}^{\prime}-A_{4,4}=0;$
$\displaystyle s=1011:\ \ \ \ \
A_{4,1}^{\prime}-A_{4,2}^{\prime}-A_{4,3}-A_{4,4}^{\prime}=0;$ $\displaystyle
s=0111:\ \ \ \ \ A_{4,1}+A_{4,2}-A_{4,3}^{\prime}+A_{4,4}=0.$ (86)

The above four nontrivial parity conditions provide the constraint relations

$A_{4,1}=A_{4,3}^{\prime},\ \ \ \ \text{and}\ \ \ \ \
A_{4,1}^{\prime}=A_{4,4}^{\prime}$ (87)

which has to be satisfied in a PO task.

Thus, imposing the PO relations from Eq. (87), the quantum success probability
can then be casted as

$\displaystyle(\mathcal{P}_{4}^{g_{4}=3})_{Q}=\dfrac{1}{2}+\dfrac{\mathrm{tr}[\Delta_{4}^{g_{4}=3}]_{Q}}{128}$
(88)

where the correlation function $\Delta_{4}^{g_{4}=3}$ is

$\displaystyle\Delta_{4}^{g_{4}=3}$ $\displaystyle=$
$\displaystyle(A_{4,1}+A_{4,2}+A_{4,3}+A_{4,4})B_{4,1}+(A_{4,1}-A_{4,2}+A_{4,3}-A_{4,4})B_{4,2}$
(89) $\displaystyle+$
$\displaystyle(2A^{\prime}_{4,1}+A^{\prime}_{4,2}+A_{4,1})B_{4,3}+(2A^{\prime}_{4,1}-A^{\prime}_{4,2}-A_{4,1})B_{4,4}.$

The expression $\Delta_{4}^{g_{4}=3}$ has the preparation noncontextual bound
$32$ which consequently provides the preparation noncontextual success
probability $(\mathcal{P}_{4}^{g_{4}=3})_{pnc}=3/4$.

To find the quantum upper bound of $\mathrm{tr}[\Delta_{4}^{g_{4}=3}]_{Q}$, we
define

$\displaystyle
B_{4,1}=\frac{(A_{4,1}+A_{4,2}+A_{4,3}+A_{4,4})}{\omega_{4,1}};\ \ \
B_{4,3}=\frac{(2A^{\prime}_{4,1}+A^{\prime}_{4,2}+A_{4,1})}{\omega_{4,3}}$
$\displaystyle
B_{4,2}=\frac{(A_{4,1}-A_{4,2}+A_{4,3}-A_{4,4})}{\omega_{4,2}};\ \ \
B_{4,4}=\frac{(2A^{\prime}_{4,1}-A^{\prime}_{4,2}-A_{4,1})}{\omega_{4,4}}$
(90)

where $\omega_{4,i}$’s are suitable positive number which can be explicitly
written as

$\displaystyle\omega_{4,1}$ $\displaystyle=$
$\displaystyle||(A_{4,1}+A_{4,2}+A_{4,3}+A_{4,4})||;\ \ \
\omega_{4,3}=||(2A^{\prime}_{4,1}+A^{\prime}_{4,2}+A_{4,1})||$
$\displaystyle\omega_{4,2}$ $\displaystyle=$
$\displaystyle||(A_{4,1}-A_{4,2}+A_{4,3}-A_{4,4})||;\ \ \
\omega_{4,4}=||(2A^{\prime}_{4,1}-A^{\prime}_{4,2}-A_{4,1})||.$ (91)

where
$||\mathcal{O}||=\sqrt{\lambda_{max}\Big{(}\mathcal{O}^{*}\mathcal{O}\Big{)}}$
is the trace norm where $\lambda_{max}$ denotes the maximum eigenvalue of
$\mathcal{O}$.

Putting Eqs. (D-D) in Eq. (89), we find

$max\left(\mathrm{tr}[\Delta_{4}^{g_{4}=3}]\right)=4\
max(\sum_{i=1}^{4}\omega_{4,i})$ (92)

where $\omega_{4,i}$’s can be written as

$\displaystyle\omega_{4,1}$ $\displaystyle=$
$\displaystyle\sqrt{\lambda_{max}\Big{(}\
4\mathbb{I}+\\{A_{4,1},A_{4,2}\\}+\\{A_{4,1},A_{4,3}\\}+\\{A_{4,1},A_{4,4}\\}+\\{A_{4,2},A_{4,3}\\}+\\{A_{4,2},A_{4,4}\\}+\\{A_{4,3},A_{4,4}\\}\Big{)}},$
$\displaystyle\omega_{4,2}$ $\displaystyle=$
$\displaystyle\sqrt{\lambda_{max}\Big{(}\
4\mathbb{I}-\\{A_{4,1},A_{4,2}\\}+\\{A_{4,1},A_{4,3}\\}-\\{A_{4,1},A_{4,4}\\}-\\{A_{4,2},A_{4,3}\\}+\\{A_{4,2},A_{4,4}\\}-\\{A_{4,3},A_{4,4}\\}\Big{)}},$
$\displaystyle\omega_{4,3}$ $\displaystyle=$
$\displaystyle\sqrt{\lambda_{max}\Big{(}\
6\mathbb{I}+2\\{A_{4,1},A_{4,1}^{\prime}\\}+2\\{A_{4,1},A_{4,2}^{\prime}\\}+2\\{A_{4,1}^{\prime},A_{4,2}^{\prime}\\}\Big{)}},$
$\displaystyle\omega_{4,4}$ $\displaystyle=$
$\displaystyle\sqrt{\lambda_{max}\Big{(}\
6\mathbb{I}-2\\{A_{4,1},A_{4,1}^{\prime}\\}+2\\{A_{4,1},A_{4,2}^{\prime}\\}-2\\{A_{4,1}^{\prime},A_{4,2}^{\prime}\\}\Big{)}}.$
(93)

The maximum value of $\left(\mathrm{tr}[\Delta_{4}^{g_{4}=3}]_{Q}\right)$ in
Eq. (92) has to be derived by considering PO condition along with the
condition $[A_{4,i},A_{4,i}^{\prime}]=0$ with $i\in\\{1,...,4\\}$. For a two-
qubit system, it is straightforward to find
$max\left(\mathrm{tr}[\Delta_{4}^{g_{4}=3}]\right)=4(\sqrt{10}+5\sqrt{2})$.
Consequently, by using Eq. (88), we find the optimal success probability
$(\mathcal{P}_{4}^{g_{4}=3})_{Q}\approx
0.819>(\mathcal{P}_{4}^{g_{4}=3})_{pnc}=0.75$.

A choice of Alice’s observables for which the above quantum bound can be
obtained is the following.

$\displaystyle A_{4,1}=A_{4,3}^{\prime}=\sigma_{x}\otimes\sigma_{x},\ \
A_{4,1}^{\prime}=A_{4,4}^{\prime}=\sigma_{y}\otimes\sigma_{y};$ (94)
$\displaystyle
A_{4,2}=\sigma_{x}\otimes\sigma_{y},A_{4,2}^{\prime}=\sigma_{y}\otimes\sigma_{x};A_{4,3}=\sigma_{z}\otimes\sigma_{y};A_{4,4}=\sigma_{z}\otimes\sigma_{x}$

##  Appendix E 3-bit entanglement-assisted PORAC

Our proposed prepare-and-measure scenario can also be converted into
entanglement-assisted scenario. In such a case, Alice and Bob share an
entangled state $\rho_{AB}\in\mathbb{C}^{4}\otimes\mathbb{C}^{4}$. Alice
encodes eight input states by performing sequential projective measurement
randomly on two pairs of commuting observables ($A_{3,i}$ and
$A^{\prime}_{3,i}$) with $i=1,2$ on her system as depicted in Figure 1. Alice
perform a non-selective degeneracy breaking measurement of an observable (say,
$A^{\prime}_{3,i}$) before the measurement of $A_{3,i}$ to encode the bits in
rank-1 density matrices. The steered (unnormalized) states $\tilde{\rho}_{x}$
can be compactly written as

$\displaystyle\tilde{\rho}_{x}\equiv\ket{\psi_{x}}\bra{\psi_{x}}=\mathrm{tr_{A}}[(P_{A_{3,i}}^{a}\otimes\mathbb{I})(P_{A^{\prime}_{3,i}}^{a^{\prime}}\otimes\mathbb{I})\hskip
2.84544pt\rho_{AB}]$ (95)

where $a,a^{\prime}=\\{+,-\\}$ and
$\rho_{x}=\tilde{\rho}_{x}/Tr[\tilde{\rho}_{x}]$.

Figure 1: The encoding scheme for PORAC $\mathbb{G}_{3,3}$ by using degeneracy
breaking non-selective sequential measurements of commuting observables

Note here that given the parity element $s=\\{111\\}$, in quantum theory the
PO condition provides

$1/4(\rho_{000}+\rho_{011}+\rho_{110}+\rho_{101})=1/4(\rho_{001}+\rho_{010}+\rho_{100}+\rho_{111})=(\mathbb{I\otimes
I})/4,$ (96)

i.e, the mixture of the four states corresponding to the even parity is
identical to the mixture of the four states corresponding to odd parity. Thus,
the parity-oblivious condition is naturally satisfied for such encoding.

In a two-qubit system at most three mutually commuting observables are
available and hence product of any two will return the third one. Moreover,
for a two-qubit system the choice of basis for doubly degenerate eigen-
subspace are not unique and can be written in infinitely many ways. Thus, to
optimize the quantum success probability, in Alice’s encoding scheme we
considered the prime observables to be same (i.e.,
$A^{\prime}_{3,1}=A^{\prime}_{3,2}=A^{\prime}_{3}$) for different set of non-
selective degeneracy breaking measurement corresponding to $A_{3,1}$ and
$A_{3,2}$ respectively. Such a encoding scheme not only satisfies the
restriction in quantum theory as given in Eq. (IV) in the main text but can
also be equivalently represented in a preparation noncontextual ontological
model of the operational quantum theory. Interestingly, this restriction in a
preparation noncontextual model further reproduces the preparation
noncontextual bound for a $3$-bit PORAC.

On the other hand, Bob performs three projective measurements
$\\{\Pi_{3,y}^{0},\Pi_{3,y}^{1}\\}$ with $y=1,2,3$, with $b=x_{y}=0,1$. Then,
using Eq. (9) from the main text, a similar derivation will give the quantum
success probability in terms of Bell expression as

$(\mathcal{P}_{3}^{g_{3}=3})_{Q}=\dfrac{1}{2}+\dfrac{\langle\mathcal{B}_{3}^{g_{3}=3}\rangle_{Q}}{12}$
(97)

where the Bell expression $\mathcal{B}_{3}^{g_{3}=3}$ can be written as

$\displaystyle\mathcal{B}_{3}^{g_{3}=3}=(A_{3,1}+A_{3,2})\otimes
B_{3,1}+({\tilde{A}}_{3,1}-{\tilde{A}}_{3,2})\otimes
B_{3,3}+2A^{\prime}_{3}\otimes B_{3,2}.$ (98)

The optimal quantum value of the Bell expression in Eq. (98) is derived as

$\displaystyle(\mathcal{B}_{3}^{g_{3}=3})_{Q}^{opt}=2+2\sqrt{2}.$ (99)

when $B_{3,1}=(A_{3,1}+A_{3,2})/\sqrt{2}$ , $B_{3,2}=A^{\prime}_{3}$ and
$B_{3,3}=(\tilde{A}_{3,1}-{\tilde{A}}_{3,2})/\sqrt{2}$, and the shared
entangled state is $\ket{\psi_{AB}}=\ket{\phi_{AB}^{+}}^{\otimes 2}$ where

$\displaystyle\ket{\phi_{AB}^{+}}=\frac{\ket{00}+\ket{11}}{\sqrt{2}}$ (100)

Thus, the optimal quantum success probability is

$(\mathcal{P}_{3}^{g_{3}=3})_{Q}^{opt}=\dfrac{1}{2}+\dfrac{1+\sqrt{2}}{6}\approx
0.902$ (101)

which remains same as in the prepare-and-measure scenario.

Let us provide a simple strategy which saturates the optimal quantum success
probability in Eq. (101). In entanglement-assisted scenario Alice is allowed
to send two bits information to Bob. Upon receiving the bits from Alice, Bob
performs projective measurements based on a prior strategy. Suppose Alice
sends $\\{00,01,10,11\\}$ to Bob. Note that, $00$ has the equal probability to
be chosen from $s$-parity $0$ and $s$-parity $1$, and same for other cases.
Hence, Alice’s communication does not reveal the parity information to Bob.
Let, Alice always sends the first two bits. If Alice communicates $00$, Bob
performs the projective measurements
$\Pi_{3,1}^{0},\Pi_{3,2}^{0},\Pi_{3,3}^{0}$ to learn about first, second and
third bit respectively. Similarly, if Alice communicates $01$, Bob performs
$\Pi_{3,1}^{0},\Pi_{3,2}^{1},\Pi_{3,3}^{1}$ on his system. Again, for Alice’s
communication of $10$ and $11$, Bob performs projective measurement
$\Pi_{3,1}^{1},\Pi_{3,2}^{0},\Pi_{3,3}^{1}$ and
$\Pi_{3,1}^{1},\Pi_{3,2}^{1},\Pi_{3,3}^{0}$ respectively. This strategy
provides the optimal quantum success probability given in Eq. (101).

Finally, we note that we have used a pair of two-qubit entangled states here
but this protocol works for a pair of entangled states in any arbitrary
dimension.

##  Appendix F Proposed experimental scheme for 3-bit PORAC

Figure 2: A schematic of the experimental setup for the PORAC
$\mathbb{G}_{3,3}$ in prepare-and-measure scenario

We provide a sketch of the experimental setup corresponding to the parity-set
$\mathbb{G}_{3,3}$ in the prepare-and-measure scenario by using a suitable
Mach-Zehender setup. For $\mathbb{G}_{3,3}$, the eight pure states for Alice’s
encoding are the following; $\rho_{000}=|+0\rangle\langle 0+|$,
$\rho_{110}=|+1\rangle\langle 1+|$, $\rho_{011}=|-0\rangle\langle 0-|$ and
$\rho_{101}=|-1\rangle\langle 1-|$ are the common eigenstates of
$A_{3,1}=\sigma_{x}\otimes\sigma_{x}$ ,
${\tilde{A}}_{3,1}=\mathbb{I}\otimes\sigma_{x}$ and
$A_{3}^{\prime}=\sigma_{x}\otimes\mathbb{I}$ are the $s$-parity $0$ set. The
$s$-parity $1$ set are given by $\rho_{001}=|++\rangle\langle++|$,
$\rho_{100}=|-+\rangle\langle+-|$, $\rho_{010}=|+-\rangle\langle-+|$ and
$\rho_{111}=|--\rangle\langle--|$ which are the common eigenstates of
$A_{3,2}=\sigma_{x}\otimes\sigma_{z}$,
$A^{\prime}_{3}=\sigma_{x}\otimes\mathbb{I}$ and
${\tilde{A}}_{3,2}=\mathbb{I}\otimes\sigma_{z}$.

The Mach-Zehender setup shared by Alice and Bob is depicted in Figure 2. The
entire setup consists of a $50:50$ beam splitter ($BS_{1}$), an asymmetric
beam-splitter $(BS_{2}$), two polarizing beam splitters ($PBS_{1}$ and
$PBS_{2}$), two polarization(spin)-rotators ($SR_{1}$ and $SR_{2}$), two
mirrors ($M_{1}$ and $M_{2}$), and two phase-shifters ($PS_{1}$ and $PS_{2}$).
Upon receiving the joint path-spin state $|\psi_{0}\rangle\otimes|0\rangle$ of
a single particle, by using $BS_{1}$, $SR_{1}$, $SR_{2}$ and $PS_{1}$, Alice
prepares the following general state

$\ket{\psi_{x}}=\dfrac{(\ket{\psi_{1}}+ie^{i\phi_{1}}\ket{\psi_{2}})}{\sqrt{2}}\otimes(cos\theta\ket{0}+sin\theta\ket{1})$
(102)

where $\ket{\psi_{1}}\equiv\ket{0}$ and $\ket{\psi_{2}}\equiv\ket{1}$ are the
path states. Two different values of $\phi_{1}\ (\pi/2$ and $3\pi/2$), and
four different values of $\theta\ (0,\pi/2,\pi/4$ and $3\pi/4)$ provide the
required eight input pure states.

Bob decodes the information by using three measurements
$B_{3,y}=B_{3,p}\otimes\sigma_{3,\theta}$ implemented by using $PS_{2}$,
$BS_{2}$, $PBS_{1}$ and $PBS_{2}$. Here $B_{3,p}$ and $\sigma_{3,\theta}$ are
the relevant path and polarization observables respectively. He implements the
relevant path measurements by using the $PS_{2}$ and $BS_{2}$ which can be
written as $B_{3,p}=P(\psi_{3})-P(\psi_{4})$, where the eigenvalues $\pm 1$ of
$B_{3,p}$ pertain to measurement in either $\ket{\psi_{3}}$ or
$\ket{\psi_{4}}$ respectively which are unitarily related to the states
$\ket{\psi_{1}}$ and $\ket{\psi_{2}}$ as

$\displaystyle\ket{\psi_{3}}=i\alpha
e^{i\phi_{2}}\ket{\psi_{1}}+\beta\ket{\psi_{2}},\ \ket{\psi_{4}}=\beta
e^{i\phi_{2}}\ket{\psi_{1}}+i\alpha\ket{\psi_{2}}$ (103)

where $\alpha(\beta)$ are reflectivity (tranmitivity) satisfying
$|\alpha|^{2}+|\beta|^{2}=1$. Taking, $\ket{\psi_{1}}=\ket{0}$ and
$\ket{\psi_{2}}=\ket{1}$ , and using the relations in Eq. (103) Bob’s path
observables $B_{3,p}$ can can be represented as

$\begin{pmatrix}\alpha^{2}-\beta^{2}&2i\alpha\beta e^{i\phi_{2}}\\\
-2i\alpha\beta e^{-i\phi_{2}}&\beta^{2}-\alpha^{2}\end{pmatrix}.$ (104)

Different values of $\alpha(\beta)$ and $\phi_{2}$ will lead to different path
observables and the polarization observables can be implemented by $PBS_{1}$
and $PBS_{2}$. This provides the required observables $B_{3,y}$ for Bob with
$y=1,2,3$.

## Aknowledgement

PR acknowledges the support from the project
DST/ICPS/QuST/Theme-2/2019/General Project Q-90. AKP acknowledges the support
from the research grant MTR/2021/000908.

## References

  * [1] S. Wiesner, “Conjugate coding,” SIGACT News, 15:78–88 (1983).
  * [2] A. Nayak, in  Proceedings of the 40th IEEE Symposium on Foundations of Computer Science (FOCS’99) (IEEE Computer society, Washington), pp. 369–376 (1999). arXiv:quant-ph/9904093v3
  * [3] R. de Wolf, “Quantum communication and complexity,” Theor. Comput. Sci. 287, 337 (2002).
  * [4] G. Brassard, “Quantum Communication Complexity,” Found. Phys. 33, 1593 (2003).
  * [5] H. Buhrman, R. Cleve, S. Massar, and R. de Wolf, “Nonlocality and communication complexity,” Rev. Mod. Phys. 82, 665 (2010).
  * [6] A. Tavakoli and M. Żukowski, “Higher-dimensional communication complexity problems: Classical protocols versus quantum ones based on Bell’s theorem or prepare-transmit-measure schemes,” Phys. Rev. A 95, 042305 (2017).
  * [7] Vaisakh M, R. k. Patra, M. Janpandit, S. Sen, M. Banik, and A. Chaturvedi, “Mutually unbiased balanced functions and generalized random access codes,” Phys. Rev. A 104, 012420 (2021).
  * [8] J. F. Doriguello and A. Montanaro, “Quantum Random Access Codes for Boolean Functions,” Quantum 5, 402 (2021).
  * [9] S. Gupta, D. Saha, Z-P Xu, A. Cabello, and A. S. Majumdar, “Quantum Contextuality Provides Communication Complexity Advantage,” Phys. Rev. Lett. 130, 080802 (2023).
  * [10] C. H. Bennett, D. P. DiVincenzo, P. W. Shor, J. A. Smolin, B. M. Terhal, and W. K. Wootters, “Remote state preparation,” Phys. Rev. Lett. 87, 077902 (2001).
  * [11] D. Gavinsky, J. Kempe, O. Regev, and R. de Wolf, “Bounded-error quantum state identification and exponential separations in communication complexity,” In Proceedings of 38th ACM STOC, 594 (2006).
  * [12] S. Muhammad, A. Tavakoli, M. Kurant, M. Pawłowski, M. Żukowski, and M. Bourennane, “Quantum Bidding in Bridge,” Phys. Rev. X 4, 021047 (2014).
  * [13] M. Banik, S. S. Bhattacharya, A. Mukherjee, A. Roy, A. Ambainis, and A. Rai, “Limited preparation contextuality in quantum theory and its relation to the Cirel’son bound,” Phys. Rev. A 92, 030103(R) (2015).
  * [14] A. Tavakoli, B. Marques, M. Pawłowski, and M. Bourennane, “ Spatial versus sequential correlations for random access coding,” Phys. Rev. A 93, 032336 (2016).
  * [15] M. Pawłowski and M. Żukowski, “Entanglement-assisted random access codes,” Phys. Rev. A 81, 042326 (2017).
  * [16] A. Hameedi, D. Saha, P. Mironowicz, M. Pawłowski, and M. Bourennane, “Complementarity between entanglement-assisted and quantum distributed random access code,” Phys. Rev. A 95, 052345 (2017).
  * [17] A. Hameedi, A. Tavakoli, B. Marques, and M. Bourennane, “Communication Games Reveal Preparation Contextuality”, Phys. Rev. Lett. 119, 220402 (2017).
  * [18] S. Laplante, M. Laurière, A. Nolin, J. Roland, and G. Senno, “Robust Bell inequalities from communication complexity,” Quantum 2, 72 (2018).
  * [19] A. Tavakoli, A. A. Abbott, M-O. Renou, N. Gisin, and N. Brunner, “Semi-device independent characterization of multipartite entanglement of states and measurements,” Phys. Rev. A 98, 052333 (2018).
  * [20] S. Ghorai and A. K. Pan, “Optimal quantum preparation contextuality in an $n$-bit parity-oblivious multiplexing task,” Phys. Rev A 98, 032110 (2018).
  * [21] A. Kumari and A. K. Pan, “Sharing nonlocality and nontrivial preparation contextuality using the same family of Bell expressions,” Phys. Rev. A 100, 062130 (2019).
  * [22] A. K. Pan and S. S. Mahato, “Device-independent certification of the Hilbert-space dimension using a family of Bell expressions,” Phys. Rev. A 102, 052221 (2020).
  * [23] A. K. Pan, “Oblivious communication game, self-testing of projective and nonprojective measurements, and certification of randomness,” Phys. Rev. A 104, 022212 (2021).
  * [24] A. Piveteau, J. Pauwels, E. Håkansson, S. Muhammad, M. Bourennane and A. Tavakoli, “Entanglement-assisted quantum communication with simple measurements,” Nature Communications 13, 7878 (2022).
  * [25] Y. Xiao, X-H Han, X. Fan, H-C Qu, and Y-J Gu, “Widening the sharpness modulation region of an entanglement-assisted sequential quantum random access code: Theory, experiment, and application,” Phys. Rev. Research 3, 023081 (2023).
  * [26] P. Roy and A. K. Pan, “Device-independent self-testing of unsharp measurements,” New J. Phys. 25 013040 (2023).
  * [27] E. F. Galvão, “Feasible quantum communication complexity protocol,” Phys. Rev. A 65, 012318 (2001).
  * [28] M. Hayashi, K. Iwama, H. Nishimura, R. Raymond, and S. Yamashita, “$(4,1)$-Quantum random access coding does not exist—one qubit is not enough to recover one of four bits,” New J. Phys. 8, 129 (2006).
  * [29] A. Ambainis, D. Leung, L. Mancinska, and M. Ozols, “Quantum Random Access Codes with Shared Randomness,” arXiv:0810.2937 (2009).
  * [30] R. W. Spekkens, D. H. Buzacott, A. J. Keehn, B. Toner, and G. J. Pryde, “Preparation Contextuality Powers Parity-Oblivious Multiplexing,” Phys. Rev. Lett. 102, 010401 (2009).
  * [31] R. Gallego, N. Brunner, C. Hadley, and A. Acín, “Device-Independent Tests of Classical and Quantum Dimensions,” Phys. Rev. Lett. 105, 230501 (2010).
  * [32] M. Pawłowski and N. Brunner, “ Semi-device-independent security of one-way quantum key distribution,” Phys. Rev. A 84, 010302(R) (2011).
  * [33] N. Brunner, M. Navascués, and T. Vértesi, “ Dimension Witnesses and Quantum State Discrimination,” Phys. Rev. Lett. 110, 150501 (2013).
  * [34] A. Tavakoli, A. Hameedi, B. Marques, and M. Bourennane, “Quantum Random Access Codes Using Single d-Level Systems,” Phys. Rev. Lett. 114, 170502 (2015).
  * [35] P. A. Guérin, A. Feix, M. Araújo, and C. Brukner, “Exponential Communication Complexity Advantage from Quantum Superposition of the Direction of Communication,” Phys. Rev. Lett. 117, 100502 (2016).
  * [36] M. Smania, A. M Elhassan, A. Tavakoli, and M. Bourennane, “Experimental quantum multiparty communication protocols,” npj Quantum Inf. 2, 16010 (2016).
  * [37] A. Chailloux, I. Kerenidis, S. Kundu, and J. Sikora, “Optimal bounds for parity-oblivious random access codes,” New J. Phys. 18, 045003 (2016).
  * [38] T. Van Himbeeck, E. Woodhead, N. J. Cerf, R. Garcia-Patron, and S. Pironio, “Semi-device-independent framework based on natural physical assumptions,” Quantum 1, 33 (2017).
  * [39] A. Tavakoli, J. Kaniewski, T. Vértesi, D. Rosset, and N. Brunner, “ Self-testing quantum states and measurements in the prepare-and-measure scenario.” Phys. Rev. A 98, 062307 (2018).
  * [40] K. Mohan, A. Tavakoli, and N. Brunner, “Sequential random access codes and self-testing of quantum measurement instruments.” New J. Phys. 21, 083034 (2019).
  * [41] D. Saha, P. Horodecki, and M. Pawlowski, “State independent contextuality advances oneway communication,” New J. Phys. 21, 093057 (2019).
  * [42] D. Saha and A. Chaturvedi, “Preparation contextuality as an essential feature underlying quantum communication advantage,” Phys. Rev. A 100, 022108 (2019).
  * [43] A. Ambainis, M. Banik, A. Chaturvedi, D. Kravchenko, and A.Rai, “Parity oblivious d-level random access codes and class of noncontextuality inequalities,” Quan. Inf. Proc. 18, 111 (2019).
  * [44] A. Tavakoli, E. Zambrini Cruzeiro, J. Bohr Brask, N. Gisin, and N. Brunner, “Informationally restricted quantum correlations,” Quantum 4, 332 (2020).
  * [45] J. Pauwels, S. Pironio, E. Woodhead, A. Tavakoli, “Almost Qudits in the Prepare-and-Measure Scenario,” Phys. Rev. Lett. 129, 250504 (2022).
  * [46] Abhyoudai S. S., S. Mukherjee, and A. K. Pan, “Robust certification of unsharp instruments through sequential quantum advantages in a prepare-measure communication game,” Phys. Rev. A 107, 012411 (2023).
  * [47] A. Tavakoli, J. Pauwels, E. Woodhead, and S. Pironio, “Correlations in Entanglement-Assisted Prepare-and-Measure Scenarios,” PRX QUANTUM 2, 040357 (2021).
  * [48] O. Liabøtrø, “Improved classical and quantum random access codes,” Phys. Rev. A 95, 052315 (2017).
  * [49] N. Harrigan and R. Spekkens, “Einstein, incompleteness, and the epistemic view of quantum states,” Found. Phys. 40, 125 (2010).
  * [50] R. W. Spekkens, “Contextuality for preparations, transformations, and unsharp measurements,” Phys. Rev. A 71, 052108 (2005).
  * [51] A. K. Pan, “Revealing universal quantum contextuality through communication games,” Sci. Rep. 9, 17631 (2019).
  * [52] R. Kunjwal and R. W. Spekkens, “From the Kochen-Specker Theorem to Noncontextuality Inequalities without Assuming Determinism,” Phys. Rev. Lett. 115, 110403 (2015).