Random Exclusion Codes: Quantum Advantages of Single-Shot Communication

Joonwoo Bae, Kieran Flatt, Teiko Heinosaari, Oskari Kerppo, Karthik Mohan, Andrés Muñoz-Moller, Ashutosh Rai · 2025

Read Random Exclusion Codes: Quantum Advantages of Single-Shot Communication by Joonwoo Bae, Kieran Flatt, Teiko Heinosaari, Oskari Kerppo, Karthik Mohan, Andrés Muñoz-Moller, Ashutosh Rai (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-07701.txt.

Introduction

Joonwoo Bae and co-authors design a communication game where quantum tools beat classical ones in two separate ways. In their random exclusion code, a sender squeezes a random message into a shorter string, and the receiver wins by ruling out one letter that the message did not contain. The task is one-shot: prepare, send, measure.

Quantum strategies name the excluded letter more often than any classical plan. The team also shows the quantum gear needed can live in a smaller space of states than its classical rival, a dimension edge. Curiously, the mirror task of guessing the letter outright, the random access code, shows no such dimension edge. The contrast sharpens where quantum advantage truly lives in two-party talk.

Catalog record

CREATORJoonwoo Bae, Kieran Flatt, Teiko Heinosaari, Oskari Kerppo, Karthik Mohan, Andrés Muñoz-Moller, Ashutosh Rai
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE50 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-07701

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Random Exclusion Codes: Quantum Advantages of Single-Shot Communication Joonwoo Bae, Kieran Flatt, Teiko Heinosaari, Oskari Kerppo, Karthik Mohan, Andrés Muñoz-Moller, Ashutosh Rai Abstract Identifying information tasks that offer advantages over their classical counterparts by exploiting quantum resources finds the usefulness of quantum information technologies. In this work, we introduce a two-party communication primitive, random exclusion code (REC), which is a single-shot prepare-and-measure protocol where a sender encodes a random message into a shorter sequence and a receiver attempts to exclude a randomly chosen letter in the original message. We present quantum advantages in RECs in two ways: probability and dimension . We show that RECs with quantum resources achieve higher success probabilities than classical strategies. We verify that the quantum resources required to describe detection events of RECs have a smaller dimension than classical ones. We also show that a guessing counterpart, random access codes (RACs), may not have a dimension advantage over classical resources. Our results elucidate various possibilities of achieving quantum advantages in two-party communication. One of the key challenges in Quantum Information Theory is to address information tasks that demonstrate the distinct nature of quantum and classical resources. A gap appearing from the distinction, even if it is small, may be amplified toward practical applications, namely, quantum advantages in communication Winter 2013 . It is hence of both fundamental and practical importance to identify a simplest information scenario, such as a point-to-point communication protocol, such that quantum advantages are present. The Holevo theorem is the first attempt along this line, considering a channel capacity with i.i.d. quantum states, but showing no quantum advantage Holevo 2011 ; Holevo 1998 ; Schumacher and Westmoreland 1997 . It is random access codes (RACs) that have verified the existence of quantum advantages in two-party communication Ambainis et al. 2009 ; Ambainis et al. 2024 ; Tavakoli et al. 2015 ; Carmeli et al. 2020 . We emphasize that it is a single-shot scenario in which a single outcome is obtained from a detection event, from which a receiver learns about a message. Then, the guess is correct with some probability. The quantum advantage is demonstrated by the fact that the guessing probability in RACs is higher with quantum resources than classical strategies. Although the connection is not direct, RACs are closely related to quantum state discrimination Helstrom 1969 , see also Bae and Kwek 2015 ; Barnett and Croke 2009 ; Bergou 2007 . Interestingly, quantum state anti-discrimination, which efficiently excludes a state from an ensemble, has been used as an effective tool to clarify the distinctions between quantum and classical resources in a single-shot experiment Caves et al. 2002 ; Pusey et al. 2012 ; Bandyopadhyay et al. 2014a ; Heinosaari and Kerppo 2018 . Quantum advantages can be obtained in terms of a success probability Uola et al. 2020 ; Ducuara et al. 2020 , and a quantum-classical gap is also present in detection events. For instance, the Pusey-Barrett-Rudolph (PBR) theorem Pusey et al. 2012 rules out an impossible interpretation of quantum states by deriving a detection event that cannot happen with quantum resources. Upon examining the fundamental tasks closely, it becomes clear that discrimination and exclusion are distinct in nature. Perfect discrimination of states achieves perfect exclusion by assigning an item from perfect guessing to another one. The converse does not generally hold. Thus, quantum state exclusion is operationally more general. Then, state exclusion may lead to even greater possibilities of quantum advantages. As discussed above, efforts to distinguish quantum and classical resources in a single-shot scenario take one of the approaches. One is comparing the success probability for a single detection event; the probability with quantum resources is higher than that of classical ones, e.g., RACs. The other is to take into account the detection events. For instance, the PBR theorem signifies a detection event that is impossible to occur with quantum resources but is possible with independent ontic preparations Pusey et al. 2012 ; Harrigan and Spekkens 2010 . Note that the Bell theorem is comparable to the latter in that it also rules out an ontic interpretation of quantum states; in contrast to the PBR result, two parties repeat a Bell experiment for estimating joint probabilities Bell 1964 ; Brunner et al. 2014 . Then, it is worth mentioning that the quantum-classical gap from the Bell theorem has been developed as a practical tool for device-independent quantum information processing, such as randomness extraction Pironio et al. 2010 , quantum key distribution Acín et al. 2007 , state certification Šupić and Bowles 2020 ; Šupić et al. 2021 , etc. In this work, we present random exclusion codes (RECs) that leverage quantum state anti-discrimination to a communication primitive. Throughout, an (n,m) REC of interest is a single-shot and prepare-and-measure protocol where a sender, Alice, encodes a random message of length n using a set of m letters into a d -dimensional system and transmits it. Bob, a receiver, realizes a decoding to exclude a chosen letter in the original message. We show quantum advantages of RECs in two ways: one is the probability advantage for a single detection event, and the other is the dimension advantage for a collection of possible detection events. Firstly, a higher success probability in the exclusion task of a REC can be achieved with quantum resources than with classical ones. Secondly, quantum resources in a smaller Hilbert space achieve RECs that can be realized only in a larger classical dimension. Note that a classical dimension denotes the minimal number of distinguishable letters of an alphabet. The importance of the results is twofold. On the one hand, we relate state exclusion, a fundamental tool for verifying distinctions between the elements of quantum and classical theories Caves et al. 2002 ; Bandyopadhyay et al. 2014b ; Crickmore 2020 ; Pusey et al. 2012 , to a communication primitive that may find practical applications. On the other hand, we demonstrate the quantum-classical gap within a single-shot framework by highlighting the differences between quantum and classical supports for detection events, see also Pusey et al. 2012 . We also find that a RAC may not have a dimension advantage. We begin with notations for an (n,m) REC. A message of Alice is written by a=a_{1}...a_{n} where each is chosen from a set of m distinguishable letters, a_{i}\in\{0,\cdots,m-1\} . An encoding prepares a d -dimensional system, and let b_{j} denote Bob’s decoding of a_{j} once he decides to read out a_{j} , see also Fig. 1 . With an REC, Bob wants to find b_{j} that is not equal to a_{j} . In this case, the probability of successfully excluding a correct value on average is given, \displaystyle{p}^{\mathrm{(REC)}}=\frac{1}{nm^{n}}\sum_{a}\sum_{i=1}^{n}\penalty\ \mathrm{Prob}[b_{i}\neq a_{i}]. (1) A quantum realization signifies a preparation of a d -dimensional quantum state and m -outcome measurements for Bob to obtain b_{j} . In contrast to RECs, Bob for RACs wants to guess Alice’s message. The average success probability is found, \displaystyle{p}^{\mathrm{(RAC)}}=\frac{1}{nm^{n}}\sum_{a}\sum_{i=1}^{n}\penalty\ \mathrm{Prob}[b_{i}=a_{i}]. (2) In both cases above in Eqs. ( 1 ) and ( 2 ), parties aim to maximize the success probability in all strategies with given resources. Note that state discrimination and state exclusion are equivalent for an alphabet of two letters: guessing

Read the complete text