Role of nonclassical temporal correlation in powering quantum random access codes

Random access codes (RAC) are among the most fundamental and powerful communication scenarios where a sender encodes a string of message into fewer bits and sends it to the receiver who then aims to recover any of the initial bits with some good probability of success raco1 ; raco2 ; raco3 ; Nayak99 ; Ambainis_SR . In a general $n\mapsto m$ RAC, there are $n$ number of bits (say, $x_{1},x_{2},...,x_{n}$) of message which the sender (say, Alice) sends to the receiver (say, Bob) by encoding the message in a $m$ bit string (where $m<n$). In each round, Bob picks out a random number $i$ (where $i\in\{1,2,...,n\}$) and tries to guess the $i$-th bit ($x_{i}$) of Alice. The probability with which Bob can decode the message can be increased if instead of a classical system, Alice sends a quantum system, e.g., by using either quantum communication raco3 , or communication of classical bits assisted with a shared quantum stateerac ; srac1 ; srac2 ; Das21 . Such quantum random access codes have been introduced and developed for qubit systems as well as higher dimensional quantum systems.

Historically, RAC was first proposed in order to show the enormous information carrying capabilities of a quantum system compared to a classical system of the same dimension. Although the well-known Holevo bound holevo stipulates that by using a qubit system one cannot transmit more information reliably to the receiver than one classical bit, this does not solely portray the information carrying capabilities of a quantum system. A $m$-qubit can in general be depicted by an unit vector in $2^{m}$ dimensional complex Hilbert space revealing the possibility of encoding classical information with exponentially fewer qubits. In general, Bob may not need to know the information of all $n$ bits together, but rather may choose to extract some bits of classical information out of the encoding depending on some task and therefore, may explore some degrees of freedom which otherwise were frozen. This motivates to formulate the task of RAC without contradicting Holevo’s result. Random access codes have been shown to possess wide range of applications such as quantum finite automata raco2 ; raco3 ; Nayak99 , network coding netcod1 ; netcod , locally decodable codes ldc1 ; ldc2 ; ldc3 , non-local gamesBridge , dimension witness dw ; dw2 ; dw3 ; dw4 , quantum communication complexity ccx ; Aaronson04 ; Gavinsky06 ; Buhrman01 ; Mar18 , randomness certification rangen , quantum cryptography qkd , studies of no-signaling resources Grudka , self-testing of quantum measurements Mohan , and so on.

However, there are also some surprising results such that although $n\mapsto 1$ quantum RAC with shared randomness (SR) exists Ambainis_SR , but it does not exist without SR for $n\geq 4$ netcod1 . A variant of this communication task was introduced by Spekkens et al exprac1 under a cryptographic constraint where preparation contextuality is shown to be the actual cause for achieving the quantum advantages (see also alok1 ). Recently an analytical way of finding maximal quantum bound for preparation non-contextuality inequality has been derived Sharma . Investigating the fundamental cause behind the quantum advantage of RAC is not only important from the foundational perspective, but may also escalate the way of finding new applications in information processing and communication tasks.

It is well known from the celebrated Bell theorem Bell'64 ; chsh'69 that correlations between spatially separated events are more restricted in classical theory than allowed in quantum theory. On the other hand, two fundamental no go theorems for time-like separated events involve non-contextual hidden variable models (NCVM) Bell'66 ; Kochen'67 and macro-realism LG'85 , compatible with classical theory. macro-realism (MR) was introduced by Leggett and Garg to probe quantumness of ‘macroscopic’ systems. MR is a conjunction of two assumptions, macro-realism per se and noninvasive measurability LG'85 ; LG'02 ; emary'14 ; yearsley . A variant of MR is known as non-invasive realist model where macro-realism per se is replaced by realism. Quantum theory violates consequences of both the models, i.e., KCBS inequality derivable from NCVM KCBS and Legget-Garg inequality (LGI) arising from MR LG'85 . In recent years, LGI and other temporal correlations have acquired considerable attention from both fundamental yearsley ; kofler'07 ; Naik'22 ; kofler'13 ; brukner'04 ; mal'16 ; mal'18 ; das'16 ; mal'19 ; fritz'10 ; budroni'13 ; rand'16 ; bm'14 ; brierley'19 ; usha'13 ; alok'17 ; das'18 ; ku'18 ; titas'18 ; alok2 ; urbasi1 as well as application perspectives knee'12 ; robens'15 ; knee'16 ; ku'19 ; shayan'19 ; spee'20 ; Maity21 . (For a detailed survey, see emary'14 ; yearsley ).

In the present work, we consider the framework of the prepare and measure scenario (see, for instance, Armin'21 ). We propose new inequalities for temporal correlations arising from sequential measurements and show that corresponding to every scenario of $n\mapsto 1$ RAC with SR there exists such an temporal inequality. Any quantum advantage of these communication tasks are implied by an associated violation of the derived temporal inequalities. These inequalities are asymmetric with respect to number of measurements. (For space-like separated correlations, asymmetric Bell inequalities were introduced to disprove the Peres conjecture Vertesi14 .) Moreover, as an immediate consequence of our result, maximal violation of these temporal inequalities provide the maximal success probability of the corresponding RAC with SR. In general, maximal success probability of such RAC is derived numerically for $n\geq 1$ with unproven optimality Ambainis_SR . Moving on, we find an important application of our scheme in a cryptographically primitive task, viz. randomness generation. We show that any non-zero quantum advantage of RAC can be used for certifying randomness, while all previously proposed protocols for randomness generation based on RAC do not generate genuine randomness for any arbitrary success probability. rangen ; qkd ; randomness1 .

The plan of the paper is as follows. In section II, a preliminary discussion on $n\mapsto 1$ RAC is provided. In section III, with the aim of designing operational criteria for testing RAC, temporal inequalities have been proposed for each $n\mapsto 1$ RAC. In section IV, it has been shown that any non-zero quantum advantage of $n\mapsto 1$ RAC can be used to generate genuine randomness. Finally, section V is reserved for discussion on the results obtained in this paper along with some future directions.

Let us now discuss the idea of $n\mapsto 1$ RAC in some details. Consider a prepare and measure scenario where Alice depending on the $n$-bit input string given to her uniformly at random, implements a preparation procedure by encoding the string in a qubit state $\rho_{x_{1},...,x_{n}}$. The qubit is then sent to the measurement device held by Bob, who, upon receiving an input $y\in\{1,...,n\}$, implements a binary outcome measurement $B_{y}$ and reports the outcome $\beta\in\{0,1\}$ as his output. Bob wins the game if he can perfectly guess the encoded bit sent by Alice. The average probability of winning is given by

where the coefficient $\frac{1}{n2^{n}}$ appears due to normalization. Below we discuss some particular examples of $n\mapsto 1$ RAC and their explicit forms.

$2\mapsto 1$ RAC: In a $2\mapsto 1$ RAC, Alice has an input string consisting of two bits $x_{1}x_{2}\in\{00,01,10,11\}$ which she wants to send to Bob by encoding the bits in a qubit $\rho_{x_{1}x_{2}}$. Bob’s task is to guess one of the bits (which is again chosen randomly) reliably. Therefore, after receiving an input $y\in\{1,2\}$, he performs a binary outcome measurement $B_{y}$ and reports the outcome $\beta\in\{0,1\}$ as his output. In this scenario, following Eq. (II) the average probability of perfectly guessing the bit is given by

Now consider the most general preparations and measurements as,

Here, $\hat{a_{i}}$, $\hat{b_{j}}$ are the Bloch vectors denoting Alice’s and Bob’s measurement directions respectively and $\vec{\sigma}$ are the Pauli matrices.

Clearly, $\rho_{00}+\rho_{11}=\mathbb{I}$, $\rho_{01}+\rho_{10}=\mathbb{I}$, $B_{j}^{0}+B_{j}^{1}=\mathbb{I}$ for $j=\{1,2\}$ and the notation $B_{j}^{b_{j}}$ denotes the eigenstate corresponding to the outcome $b_{j}$ of measurement $B_{j}$. The average success probability now can be written as

The maximum achievable value for the above quantity is $\frac{1}{2}(1+\frac{1}{2})$ with classical strategy, whereas it can reach up to $\frac{1}{2}(1+\frac{1}{\sqrt{2}})$ if quantum strategy is used Ambainis_SR .

$3\mapsto 1$ RAC: In a $3\mapsto 1$ RAC, a three-bit input string $x_{1}x_{2}x_{3}$ from the set $\{000,001,010,011,100,101,110,111\}$ is given to Alice uniformly at random. Alice then encodes the input string in a qubit $\rho_{x_{1}x_{2}x_{3}}$ and sends it to Bob. Bob upon receiving an input $y\in\{1,2,3\}$, implements a binary outcome measurement $B_{y}$ and reports the outcome $\beta\in\{0,1\}$ as his output. Following Eq. (II), the average probability of winning can be calculated as

Let us now consider most general preparations

and measurements as,

Clearly, $\rho_{000}+\rho_{111}=\mathbb{I}$, $\rho_{001}+\rho_{110}=\mathbb{I}$, $\rho_{010}+\rho_{101}=\mathbb{I}$, and $\rho_{011}+\rho_{100}=\mathbb{I}$. The average success probability can be written as

Here, the average success probability, $\mathbb{F}_{3\mapsto 1}$ can be achieved up to $\frac{1}{2}(1+\frac{1}{3})$ and $\frac{1}{2}(1+\frac{1}{\sqrt{3}})$, by classical and quantum strategies, respectively Ambainis_SR .

$4\mapsto 1$ RAC: In a $4\mapsto 1$ RAC, Alice has a four-bits input string $x_{1}x_{2}x_{3}x_{4}$ which is given to her uniformly at random from the set $\{0000,0001,0010,0011,0100,0101,0110,0111,1000,1001,\\ 1010,1011,1100,1101,1110,1111\}$. She then implements a preparation procedure by encoding in a qubit $\rho_{x_{1}x_{2}x_{3}x_{4}}$ and sends to Bob. Bob upon receiving an input $y\in\{1,2,3,4\}$, implements a binary outcome measurement $B_{y}$ and reports the outcome $\beta\in\{0,1\}$ as his output. The average probability of winning is given by Eq. (II) as

Let us now consider most general preparations,

and measurements

Clearly, $\rho_{0000}+\rho_{1111}=\mathbb{I}$, $\rho_{0001}+\rho_{1110}=\mathbb{I}$, $\rho_{0010}+\rho_{1101}=\mathbb{I}$, $\rho_{0011}+\rho_{1100}=\mathbb{I}$, $\rho_{0100}+\rho_{1011}=\mathbb{I}$, $\rho_{0101}+\rho_{1010}=\mathbb{I}$, $\rho_{0110}+\rho_{1001}=\mathbb{I}$, and $\rho_{0111}+\rho_{1000}=\mathbb{I}$. Therefore the explicit form of the average success probability of $4\mapsto 1$ RAC is calculated to be

For $4\mapsto 1$ RAC, the exact value of classical and quantum average success probabilities are $\frac{1}{2}(1+\frac{1}{4})$ and $\frac{1}{2}(1+\frac{1+\sqrt{3}}{4\sqrt{2}})$ respectively Ambainis_SR .

$n\mapsto 1$ RAC: In a $n\mapsto 1$ RAC, Alice has an $n$-bits input string $x_{1}x_{2}x_{3}x_{4}\dots x_{n}$ which is given to her uniformly at random. She then implements a preparation procedure by encoding this string in a qubit denoted by $\rho_{x_{1}x_{2}x_{3}x_{4}\dots x_{n}}$ and sends it to Bob. Bob upon receiving an input $y\in\{1,2,3,\dots,n\}$, implements a binary outcome measurement $B_{y}$ and reports the outcome $\beta\in\{0,1\}$ as his output. The average probability of winning is given by Eq. (II). For $n\mapsto 1$ RAC, there are $2^{n-1}$ preparations and $n$ measurements. Let us now consider the most general preparations,

and measurements

Clearly, $\rho_{m}+\rho_{\bar{m}}=\mathbb{I}$, where, $m$ are the elements of the n-bit string set. The exact form of the average success probability of $n\mapsto 1$ RAC can be calculated as

The average success probability for $n\mapsto 1$ RAC (with SR) using best classical strategy is known to be $\frac{1}{2}(1+\frac{1}{n})$ Ambainis_SR .

We would now like to present a temporal inequality corresponding to each $n\mapsto 1$ RAC. To derive such temporal inequalities, we use the assumptions of realism and noninvasive measurability. The term ‘realism’ implies “at any instant, irrespective of any measurement, a system is definitely in any one of the available states such that all its observable properties have definite values”. On the other hand, the term ‘noninvasive measurability’ assures that “it is possible, in principle, to determine which of the states the system is in, without affecting the state itself or the system’s subsequent evolution”. It can be shown that under these two assumptions the joint probability distribution get factorized at the ontological level LG'85 ; emary'14 ; yearsley ; kofler'13 . Mathematically,

with $\lambda$ being the hidden variable. Based on this macro-realistic definition of classicality, later we derive temporal inequalities corresponding to each $n\mapsto 1$ RAC and establish that violation of such inequalities implies non-classical temporal correlation. The underlying experimental setup for both the scenarios are the same, as will be clear from the following description.

In a temporal scenario, temporal correlations are obtained by measuring a single system sequentially at different instants of time. In each run of the experiment, two sequential measurements are performed on an identically prepared initial state. We assume that the first measurement is performed by Alice whereas the second one is performed by Bob. If Alice’s measurement is thought of as playing the role of preparation, then it is not very difficult to realize the similarity between RACs and macrorealistic inequalities. This observation is further substantiated by formulating the relevant inequalities which build the connection quantitatively. Suppose the measurements performed by Alice and the corresponding outcomes are denoted by $A_{i}$ and $a_{i}$ respectively. Similarly, the measurements performed by Bob are denoted by $B_{j}$ with corresponding outcome $b_{j}$. All the measurements performed by both the parties are considered to be dichotomic i.e., $a_{i},b_{j}\in\{0,1\}$.

Initially, the state on which Alice performs her measurement is denoted by $\rho_{in}$. The correlation between Alice’s and Bob’s measurement outcome depends on $\rho_{in}$. In the present analysis we took a maximally mixed state, i.e., $\rho_{in}=\mathbb{I}/2$, for reasons that will be clear later. It may be noted here that other states may be chosen for which the same maximum violation for our temporal inequalities can be achieved using different Bloch vectors ($\hat{a_{i}}$, $\hat{b_{j}}$). However, even if the directions of Alice’s and Bob’s measurements are changed, the maximum violation will remain the same.

Let the probability of obtaining outcome $a_{i}$ and $b_{j}$ be denoted by $P(a_{i},b_{j}\mid A_{i},B_{j})$, when Alice measures $A_{i}$ at time $t_{i}$ and Bob measures $B_{j}$ at some later instant $t_{j}$ respectively and $a_{i},b_{j}\in\{0,1\}$. Let us denote, $A_{i}^{a_{i}}$, $B_{j}^{b_{j}}$ as projectors so that $\sum_{a_{i}}A_{i}^{a_{i}}=\mathbb{I},\sum_{b_{j}}B_{j}^{b_{j}}=\mathbb{I}$. Now, following the standard procedure, the joint probability distribution can be obtained using Bayes’ rule as,

With this joint probability distribution, the two-time correlation is defined as,

where $\oplus$ denotes addition modulo 2. In the subsections below we present the temporal inequalities corresponding to cases of $2\mapsto 1$, $3\mapsto 1$ and $4\mapsto 1$ RACs. These inequalities are derived with a close look at the success probabilities of the corresponding RAC games. The general form of the temporal inequality for $n\mapsto 1$ RAC, i.e., $\mathcal{K}_{n\mapsto 1}$ is provided in the Appendix-(A).

As mentioned earlier, in our temporal scenario, the initially prepared state is considered to be $\mathbb{I}/2$. Since we are interested in finding the maximum violation of the temporal inequality $\mathcal{K}_{n\mapsto 1}$, without loss of generality we can stick to projective measurements only. Consider the general form of the measurements on Alice’s side to be

where $a_{i}$ represents the outcome corresponding the measurement $A_{i}$ and $\hat{a}_{i}$ represents the direction along which the $A_{i}$ measurement is being performed. On the other hand the general form of the measurements performed on Bob’s side can be considered to be

where $b_{j}$ represents the outcome corresponding to measurement $B_{j}$ and $\hat{b}_{j}$ represents the direction along which $B_{j}$ measurement is being performed. In the subsections below we state the explicit form of the quantum strategy for which maximum quantum violation of the temporal inequality $\mathcal{K}_{n\mapsto 1}$ RAC is achieved.