Simple and general bounds on quantum random access codes

Máté Farkas; Nikolai Miklin; Armin Tavakoli

doi:10.22331/q-2025-02-25-1643

Simple and general bounds on quantum random access codes

Máté Farkas¹, Nikolai Miklin², and Armin Tavakoli³

¹Department of Mathematics, University of York, Heslington, York, YO10 5DD, United Kingdom
²Institute for Quantum-Inspired and Quantum Optimization, Hamburg University of Technology, Germany
³Physics Department and NanoLund, Lund University, Box 118, 22100 Lund, Sweden.

Published:	2025-02-25, volume 9, page 1643
Editor:	Xin Wang
Eprint:	arXiv:2312.14142v3
Doi:	https://doi.org/10.22331/q-2025-02-25-1643
Citation:	Quantum 9, 1643 (2025).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

Random access codes are a type of communication task that is widely used in quantum information science. The optimal average success probability that can be achieved through classical strategies is known for any random access code. However, only a few cases are solved exactly for quantum random access codes. In this paper, we provide bounds for the fully general setting of n independent variables, each selected from a d-dimensional classical alphabet and encoded in a $D$-dimensional quantum system subject to an arbitrary quantum measurement. The bound recovers the exactly known special cases, and we demonstrate numerically that even though the bound is not tight overall, it can still yield a good approximation.

► BibTeX data

@article{Farkas2025simplegeneralbounds,
  doi = {10.22331/q-2025-02-25-1643},
  url = {https://doi.org/10.22331/q-2025-02-25-1643},
  title = {Simple and general bounds on quantum random access codes},
  author = {Farkas, M{\'{a}}t{\'{e}} and Miklin, Nikolai and Tavakoli, Armin},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {9},
  pages = {1643},
  month = feb,
  year = {2025}
}

► References

[1] Ashwin Nayak. ``Optimal lower bounds for quantum automata and random access codes''. In 40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039). Pages 369–376. (1999).
https://doi.org/10.1109/SFFCS.1999.814608

[2] Masahito Hayashi, Kazuo Iwama, Harumichi Nishimura, Rudy Raymond, and Shigeru 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, 129 (2006).
https://doi.org/10.1088/1367-2630/8/8/129

[3] Marcin Pawłowski and Marek Żukowski. ``Entanglement-assisted random access codes''. Phys. Rev. A 81, 042326 (2010).
https://doi.org/10.1103/PhysRevA.81.042326

[4] Armin Tavakoli, Breno Marques, Marcin Pawłowski, and Mohamed Bourennane. ``Spatial versus sequential correlations for random access coding''. Phys. Rev. A 93, 032336 (2016).
https://doi.org/10.1103/PhysRevA.93.032336

[5] Ola Liabøtrø. ``Improved classical and quantum random access codes''. Phys. Rev. A 95, 052315 (2017).
https://doi.org/10.1103/PhysRevA.95.052315

[6] João F. Doriguello and Ashley Montanaro. ``Quantum Random Access Codes for Boolean Functions''. Quantum 5, 402 (2021).
https://doi.org/10.22331/q-2021-03-07-402

[7] Rui-Heng Miao, Zhao-Di Liu, Yong-Nan Sun, Chen-Xi Ning, Chuan-Feng Li, and Guang-Can Guo. ``High-dimensional multi-input quantum random access codes and mutually unbiased bases''. Phys. Rev. A 106, 042418 (2022).
https://doi.org/10.1103/PhysRevA.106.042418

[8] Rafael A. da Silva and Breno Marques. ``Semidefinite-programming-based optimization of quantum random access codes over noisy channels''. Phys. Rev. A 107, 042433 (2023).
https://doi.org/10.1103/PhysRevA.107.042433

[9] Robert W. Spekkens, D. H. Buzacott, A. J. Keehn, Ben Toner, and G. J. Pryde. ``Preparation contextuality powers parity-oblivious multiplexing''. Phys. Rev. Lett. 102, 010401 (2009).
https://doi.org/10.1103/PhysRevLett.102.010401

[10] Marcin Pawłowski, Tomasz Paterek, Dagomir Kaszlikowski, Valerio Scarani, Andreas Winter, and Marek Żukowski. ``Information causality as a physical principle''. Nature 461, 1101–1104 (2009).
https://doi.org/10.1038/nature08400

[11] Nicolas Brunner, Miguel Navascués, and Tamás Vértesi. ``Dimension witnesses and quantum state discrimination''. Phys. Rev. Lett. 110, 150501 (2013).
https://doi.org/10.1103/PhysRevLett.110.150501

[12] Armin Tavakoli, Jef Pauwels, Erik Woodhead, and Stefano Pironio. ``Correlations in entanglement-assisted prepare-and-measure scenarios''. PRX Quantum 2, 040357 (2021).
https://doi.org/10.1103/PRXQuantum.2.040357

[13] Marcin Pawłowski and Nicolas Brunner. ``Semi-device-independent security of one-way quantum key distribution''. Phys. Rev. A 84, 010302 (2011).
https://doi.org/10.1103/PhysRevA.84.010302

[14] Edgar A. Aguilar, Jakub J. Borkała, Piotr Mironowicz, and Marcin Pawłowski. ``Connections between mutually unbiased bases and quantum random access codes''. Phys. Rev. Lett. 121, 050501 (2018).
https://doi.org/10.1103/PhysRevLett.121.050501

[15] Piotr Mironowicz and Marcin Pawłowski. ``Experimentally feasible semi-device-independent certification of four-outcome positive-operator-valued measurements''. Phys. Rev. A 100, 030301 (2019).
https://doi.org/10.1103/PhysRevA.100.030301

[16] Armin Tavakoli, Massimiliano Smania, Tamás Vértesi, Nicolas Brunner, and Mohamed Bourennane. ``Self-testing nonprojective quantum measurements in prepare-and-measure experiments''. Science Advances 6, eaaw6664 (2020).
https://doi.org/10.1126/sciadv.aaw6664

[17] Claudio Carmeli, Teiko Heinosaari, and Alessandro Toigo. ``Quantum random access codes and incompatibility of measurements''. Europhysics Letters 130, 50001 (2020).
https://doi.org/10.1209/0295-5075/130/50001

[18] Karthik Mohan, Armin Tavakoli, and Nicolas Brunner. ``Sequential random access codes and self-testing of quantum measurement instruments''. New Journal of Physics 21, 083034 (2019).
https://doi.org/10.1088/1367-2630/ab3773

[19] Nikolai Miklin, Jakub J. Borkała, and Marcin Pawłowski. ``Semi-device-independent self-testing of unsharp measurements''. Phys. Rev. Res. 2, 033014 (2020).
https://doi.org/10.1103/PhysRevResearch.2.033014

[20] Sadiq Muhammad, Armin Tavakoli, Maciej Kurant, Marcin Pawłowski, Marek Żukowski, and Mohamed Bourennane. ``Quantum bidding in bridge''. Phys. Rev. X 4, 021047 (2014).
https://doi.org/10.1103/PhysRevX.4.021047

[21] Armin Tavakoli, Alley Hameedi, Breno Marques, and Mohamed Bourennane. ``Quantum random access codes using single $d$-level systems''. Phys. Rev. Lett. 114, 170502 (2015).
https://doi.org/10.1103/PhysRevLett.114.170502

[22] Giulio Foletto, Luca Calderaro, Giuseppe Vallone, and Paolo Villoresi. ``Experimental demonstration of sequential quantum random access codes''. Phys. Rev. Res. 2, 033205 (2020).
https://doi.org/10.1103/PhysRevResearch.2.033205

[23] Hammad Anwer, Sadiq Muhammad, Walid Cherifi, Nikolai Miklin, Armin Tavakoli, and Mohamed Bourennane. ``Experimental characterization of unsharp qubit observables and sequential measurement incompatibility via quantum random access codes''. Phys. Rev. Lett. 125, 080403 (2020).
https://doi.org/10.1103/PhysRevLett.125.080403

[24] Ya Xiao, Xin-Hong Han, Xuan Fan, Hui-Chao Qu, and Yong-Jian Gu. ``Widening the sharpness modulation region of an entanglement-assisted sequential quantum random access code: Theory, experiment, and application''. Phys. Rev. Res. 3, 023081 (2021).
https://doi.org/10.1103/PhysRevResearch.3.023081

[25] Armin Tavakoli, Jędrzej Kaniewski, Tamás Vértesi, Denis Rosset, and Nicolas Brunner. ``Self-testing quantum states and measurements in the prepare-and-measure scenario''. Phys. Rev. A 98, 062307 (2018).
https://doi.org/10.1103/PhysRevA.98.062307

[26] Máté Farkas and Jędrzej Kaniewski. ``Self-testing mutually unbiased bases in the prepare-and-measure scenario''. Phys. Rev. A 99, 032316 (2019).
https://doi.org/10.1103/PhysRevA.99.032316

[27] Erik Woodhead and Stefano Pironio. ``Secrecy in prepare-and-measure clauser-horne-shimony-holt tests with a qubit bound''. Phys. Rev. Lett. 115, 150501 (2015).
https://doi.org/10.1103/PhysRevLett.115.150501

[28] Andris Ambainis, Dmitry Kravchenko, Sk Sazim, Joonwoo Bae, and Ashutosh Rai. ``Quantum advantages in $(n,d) \mapsto 1$ random access codes''. New Journal of Physics 26, 123023 (2024).
https://doi.org/10.1088/1367-2630/ad9bdf

[29] Debashis Saha, Debarshi Das, Arun Kumar Das, Bihalan Bhattacharya, and A. S. Majumdar. ``Measurement incompatibility and quantum advantage in communication''. Phys. Rev. A 107, 062210 (2023).
https://doi.org/10.1103/PhysRevA.107.062210

[30] Andris Ambainis, Ashwin Nayak, Ammon Ta-Shma, and Umesh Vazirani. ``Dense quantum coding and a lower bound for 1-way quantum automata''. In Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing. Page 376–383. STOC '99New York, NY, USA (1999). Association for Computing Machinery.
https://doi.org/10.1145/301250.301347

[31] Andris Ambainis, Ashwin Nayak, Amnon Ta-Shma, and Umesh Vazirani. ``Dense quantum coding and quantum finite automata''. J. ACM 49, 496–511 (2002).
https://doi.org/10.1145/581771.581773

[32] Andris Ambainis, Debbie Leung, Laura Mancinska, and Maris Ozols. ``Quantum random access codes with shared randomness'' (2009). arXiv:0810.2937.
arXiv:0810.2937

[33] Julio I de Vicente. ``A general bound for the dimension of quantum behaviours in the prepare-and-measure scenario''. Journal of Physics A: Mathematical and Theoretical 52, 095304 (2019).
https://doi.org/10.1088/1751-8121/aafde7

[34] Armin Tavakoli, Alejandro Pozas-Kerstjens, Peter Brown, and Mateus Araújo. ``Semidefinite programming relaxations for quantum correlations''. Rev. Mod. Phys. 96, 045006 (2024).
https://doi.org/10.1103/RevModPhys.96.045006

[35] Miguel Navascués, Adrien Feix, Mateus Araújo, and Tamás Vértesi. ``Characterizing finite-dimensional quantum behavior''. Phys. Rev. A 92, 042117 (2015).
https://doi.org/10.1103/PhysRevA.92.042117

[36] Armin Tavakoli, Denis Rosset, and Marc-Olivier Renou. ``Enabling computation of correlation bounds for finite-dimensional quantum systems via symmetrization''. Phys. Rev. Lett. 122, 070501 (2019).
https://doi.org/10.1103/PhysRevLett.122.070501

[37] Jef Pauwels, Stefano Pironio, Erik Woodhead, and Armin Tavakoli. ``Almost qudits in the prepare-and-measure scenario''. Phys. Rev. Lett. 129, 250504 (2022).
https://doi.org/10.1103/PhysRevLett.129.250504

[38] Dan Popovici and Zoltán Sebestyén. ``Norm estimations for finite sums of positive operators''. Journal of Operator Theory 56, 3–15 (2006). url: http://www.jstor.org/stable/24715730.
http://www.jstor.org/stable/24715730

[39] ``On-line repository: https://github.com/nikolai-miklin/qrac_bounds''.
https://github.com/nikolai-miklin/qrac_bounds

[40] Máté Farkas. ``$n$-fold unbiased bases: an extension of the MUB condition'' (2017). arXiv:1706.04446.
arXiv:1706.04446

[41] ``Qdimsum package: https://denisrosset.github.io/qdimsum/''.
https://denisrosset.github.io/qdimsum/

[42] Dariusz Chruściński and Andrzej Jamiołkowski. ``Geometric phases in classical and quantum mechanics''. Birkhäuser Boston. (2004).
https://doi.org/10.1007/978-0-8176-8176-0

[43] Charles H. Bennett and Gilles Brassard. ``Quantum cryptography: Public key distribution and coin tossing''. Theoretical Computer Science 560, 7–11 (2014).
https://doi.org/10.1016/j.tcs.2014.05.025

[44] Imre Csiszár and János Körner. ``Broadcast channels with confidential messages''. IEEE Transactions on Information Theory 24, 339–348 (1978).
https://doi.org/10.1109/TIT.1978.1055892

Cited by

[1] Joonwoo Bae, Kieran Flatt, Teiko Heinosaari, Oskari Kerppo, Karthik Mohan, Andrés Muñoz-Moller, and Ashutosh Rai, "Random exclusion codes: Quantum advantages of single-shot communication", Physical Review Research 8 1, 013171 (2026).

[2] Akarshit Baranwal, Vishnu Purushothaman, and A.K. Pan, "Discriminating quantum and beyond-quantum compositions in a communication game", Physics Letters A 580, 131528 (2026).

[3] Matilde Baroni, Eleni Diamanti, Damian Markham, and Ivan Šupić, "Translating Bell nonlocality to prepare-and-measure scenarios under dimensional constraints", Physical Review A 112 6, 062220 (2025).

[4] Elna Svegborn, Jef Pauwels, and Armin Tavakoli, "Quantum inputs in the prepare-and-measure scenario and stochastic teleportation", Quantum Science and Technology 11 2, 025001 (2026).

[5] Chao Zhang, Jia-Le Miao, Xiao-Min Hu, Jef Pauwels, Yu Guo, Chuan-Feng Li, Guang-Can Guo, Armin Tavakoli, and Bi-Heng Liu, "Quantum Stochastic Communication via High-Dimensional Entanglement", Physical Review Letters 135 12, 120802 (2025).

[6] Tong Wu, Yuqian Zhou, Qingle Wang, and Dan Li, 2025 2nd International Symposium on AI and Cybersecurity (ISAICS) 1 (2025) ISBN:979-8-3315-5490-3.

[7] Takayuki Suzuki, "Analytical construction of (n, n−1) -quantum random access codes saturating the conjectured bound", Physical Review A 114 1, 012441 (2026).

[8] Tiffany Duneau, Saskia Bruhn, Gabriel Matos, Tuomas Laakkonen, Katerina Saiti, Anna Pearson, Konstantinos Meichanetzidis, and Bob Coecke, "Scalable and interpretable quantum natural language processing: an implementation on trapped ions", arXiv:2409.08777, (2024).

[9] Andris Ambainis, Dmitry Kravchenko, Sk Sazim, Joonwoo Bae, and Ashutosh Rai, "Quantum Advantages in (n,d)->1 Random Access Codes", arXiv:1510.03045, (2015).

[10] Pharnam Bakhshinezhad, Mohammad Mehboudi, Carles Roch i. Carceller, and Armin Tavakoli, "Scalable Entanglement Certification via Quantum Communication", PRX Quantum 5 2, 020319 (2024).

[11] Gabriele Cobucci, Alexander Bernal, Martin J. Renner, and Armin Tavakoli, "Operationally classical simulation of quantum states", Nature Communications 17 1, 1104 (2026).

[12] Andris Ambainis, Dmitry Kravchenko, Sk Sazim, Joonwoo Bae, and Ashutosh Rai, "Quantum advantages in [ image ] random access codes", New Journal of Physics 26 12, 123023 (2024).

[13] Gábor Drótos, Károly F. Pál, and Tamás Vértesi, "Self-testing of semisymmetric informationally complete measurements in a qubit prepare-and-measure scenario", Physical Review A 110 3, 032427 (2024).

[14] Gábor Drótos, Károly F. Pál, Abdelmalek Taoutioui, and Tamás Vértesi, "Towards minimal self-testing of qubit states and measurements in prepare-and-measure scenarios", New Journal of Physics 26 6, 063012 (2024).

[15] Vishnu Purushothaman, Akarshit Baranwal, and A. K. Pan, "Efficacy of the information causality principle in ruling out beyond-quantum compositions", Physical Review A 112 2, 022211 (2025).

[16] Ruho Kondo, Yuki Sato, Hiroshi Yano, Yota Maeda, Kosuke Ito, and Naoki Yamamoto, "Random Access Codes: Explicit Constructions, Optimality, and Classical-Quantum Gaps", arXiv:2604.21274, (2026).

The above citations are from Crossref's cited-by service (last updated successfully 2026-08-19 09:30:19) and SAO/NASA ADS (last updated successfully 2026-08-18 21:10:21). The list may be incomplete as not all publishers provide suitable and complete citation data.

Could not fetch ADS cited-by data during last attempt 2026-08-19 09:30:19: Cannot retrieve data from ADS due to rate limitations.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.