![](data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAA1IAAAAYCAIAAAB/b1vHAAAACXBIWXMAABYlAAAWJQFJUiTwAAAEx0lEQVR42u3df0yUdRzA8Y/SJIURu5JzMu/GqRxNgboSFBFysRnmj8wwS/MPnJVOncP+SqZbc2VSjvwjLCeIWf7YaE5OGOZGU4SBysLLBceGcXqLO/L2eDsh2A7640vPHoGpS13G3q+/nuf7PPd5bp/nn8++3+f5POPy8vIEAAAAY924wcFBsgAAADDmjScFAAAAlH0AAACg7AMAAABlHwAAACj7AAAAQNkHAAAAyj4AAABQ9j0awcCdC5WuYYOtzR6P20dyAAAAZd/YUVxQcerbumGDrvrrBUtKwuEB8gMAACj7xgK/V7ta37Hmo5xh49krUkWkvuraY7166e7q4oIK7gIAAKDse+ycZQ2xk6NTM6cPG4+Lj03JsI2cBXy0goEebgEAAKDse+z6evurjjQuemdORMQoaVm19ZXONl9rs4dEAQCA/6OnSIHu9KEGEVm2ft6oR5McFqvdfHL/zzsPrxORcHig/LOaNdtfjZw4QZ3gcfuuNXXmrk1T2z8eqBOReNtzyRkJCc9PUaf19faX7KjUY2YtT5mRPDXGFCUi1Uebfm28LiLFBRUvLUxcsDRZvVmyYGmyfn7p7uq3NmXFmKL0+KMyhgUAAFCY7RsSDg/UHLu0eF26XsaN9Mb7mVfrO/xeTURudQWrjjTeNizLdrb5D31SpbZ7Qn1qo+bYpcLVpZ9vPK52bwd66pyuG+1+tfvphu/z5xapgH/8fktEtO6QHvBKrftKrdv4B6qONLZc7FDXqnO6goE7avxGu7/O6VJVox5WPwoAACDM9uludQW17lDOKseoR1ubPZOiI9Ny7CLS1nwjLj723tGSHJYkh0VtX6h0fbW9wu/V9F/tPfWBWkd+be2cL7acdJY15Bfm5hfmqmf7tu1b+SB/OCXDpuYdRcTv1TYtLN5Z9p4l0ayHrfnhct7mbO4sAABQmO0b8oxpkog0nm0d9ahq4OL+5aaIWO1xDxjT79X8Xi11vk0Vi/q4/uxgksMyOz3h373JMXIN9+moSGNYb8ef3FYAAKBjtm9I5MQJb29deGJ/7bL180au8y569+UT+2t/u+yx2s1qRu3eqo82VZScN67YAgAA/LeY7burthORpnNtIw/FmKIylySfPX55y94V943j92rqIb99zo1f1277+OAacgsAACj7niCqtivfUzPq1zhezJqhdYf+6u2/bxxnWYOIfHO+wJJojouPdWTPJLcAAICy78ny5oeZWneoveXmsPG+3v7vin6yJJoP7jqjRp6dEpOSYTuw4/TIF2ZfWDBDDJ/0ePBPutkd0+qcLr01YNbyFOMun4YDAAAPg2f77mJJNFvt5oO7znxZudE4fvpQg9Yd2rDr9aLNJ9Q7uRER47ftW5k/t6hgacns9AQR0funzEqzxk6OLt9To9qv6O1a7mtWmlVECleXrt+5OHdtmiN75uJ16YWrS1MybDGmKBqyAACAhzFucHCQLBgFA3daLnYYmyTLPw1c4qdPrq+6ZndM01uxeNy+zrahqq6rMzA9eapa0g2HB9pbbnZ7b+sRUufbYkxRfb39TefajME9bl9PqE/v9uJx+xrPtkbHTlRtn8PhAX3WsKszMMVqUnH8Xi3gC+q/Uqel5diNvaONYQEAAP4G9FzWXlQIU8AAAAAASUVORK5CYII=)
[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