[21] G. Foletto, L. Calderaro, G. Vallone, and P. Villoresi. Experimental demonstration of se-
quential quantum random access codes. Phys. Rev. Research, 2:033205, Aug 2020. DOI:
10.1103/PhysRevResearch.2.033205.
[22] D. Gavinsky, J. Kempe, O Regev, and R. de Wolf. Bounded-error quantum state identification
and exponential separations in communication complexity. SIAM J. Comput., 39(1):1–24,
2009. ISSN 0097-5397. DOI: 10.1137/060665798.
[23] A. Grudka, K. Horodecki, M. Horodecki, W. Kłobus, and M. Pawłowski. When are Popescu-
Rohrlich boxes and random access codes equivalent? Physical review letters, 113(10):100401,
2014. DOI: 10.1103/PhysRevLett.113.100401.
[24] A. Grudka, M. Horodecki, R. Horodecki, and A. Wójcik. Nonsignaling quantum ran-
dom access-code boxes. Physical Review A, 92(5):052312, 2015. DOI: 10.1103/Phys-
RevA.92.052312.
[25] A. Hameedi, D. Saha, P. Mironowicz, M. Pawłowski, and M. Bourennane. Complementarity
between entanglement-assisted and quantum distributed random access code. Physical Review
A, 95(5):052345, 2017. DOI: 10.1103/PhysRevA.95.052345.
[26] 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 Journal
of Physics, 8(8):129, 2006. DOI: 10.1088/1367-2630/8/8/129.
[27] M. Hayashi, K. Iwama, H. Nishimura, R. Raymond, and S. Yamashita. Quantum network
coding. In Annual Symposium on Theoretical Aspects of Computer Science, pages 610–621.
Springer, 2007. DOI: 10.1007/978-3-540-70918-3_52.
[28] C. W. Helstrom. Quantum detection and estimation theory, volume 3. Academic press New
York, 1976. DOI: 10.1007/BF01007479.
[29] A. S. Holevo. Bounds for the quantity of information transmitted by a quantum communica-
tion channel. Problemy Peredachi Informatsii, 9(3):3–11, 1973.
[30] B. D. Hughes. Random walks and random environments: random walks, volume 1. Oxford
University Press, 1995.
[31] T. Imamichi and R. Raymond. Constructions of quantum random access codes. In Asian
Quantum Information Symposium (AQIS), 2018.
[32] K. Iwama, H. Nishimura, R. Raymond, and S. Yamashita. Unbounded-error one-way clas-
sical and quantum communication complexity. In International Colloquium on Automata,
Languages, and Programming, pages 110–121. Springer, 2007. DOI: 10.1007/978-3-540-73420-
8_12.
[33] I. Kerenidis. Quantum encodings and applications to locally decodable codes and communica-
tion complexity. University of California, Berkeley, 2004.
[34] I. Kerenidis and R. de Wolf. Exponential lower bound for 2-query locally decodable codes via
a quantum argument. Journal of Computer and System Sciences, 69(3):395–420, 2004. ISSN
0022-0000. DOI: https://doi.org/10.1016/j.jcss.2004.04.007.
[35] H. Klauck. On quantum and probabilistic communication: Las Vegas and one-way protocols.
In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, pages
644–651. ACM, New York, 2000. DOI: 10.1145/335305.335396.
[36] H. Klauck. One-way communication complexity and the Nečiporuk lower bound on formula
size. SIAM Journal on Computing, 37(2):552–583, 2007. DOI: 10.1137/S009753970140004X.
[37] E. Kushilevitz and N. Nisan. Communication Complexity. Cambridge University Press, New
York, NY, USA, 1997. ISBN 0-521-56067-5. DOI: 10.1017/CBO9780511574948.
[38] H.-W. Li, Z.-Q. Yin, Y.-C. Wu, X.-B. Zou, S. Wang, W. Chen, G.-C. Guo, and Z.-F. Han.
Semi-device-independent random-number expansion without entanglement. Physical Review
A, 84(3):034301, 2011. DOI: 10.1103/PhysRevA.84.034301.
[39] O. Liabøtrø. Improved classical and quantum random access codes. Physical Review A, 95
(5):052315, 2017. DOI: 10.1103/PhysRevA.95.052315.
[40] F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes, volume 16.
Elsevier, 1977.
[41] E. Mossel and R. O’Donnell. On the noise sensitivity of monotone functions. Random Struc-
tures & Algorithms, 23(3):333–350, 2003. DOI: 10.1007/978-3-0348-8211-8_30.
Accepted in Quantum 2021-02-22, click title to verify. Published under CC-BY 4.0. 18