Maximal Elements of Quantum Communication

Teiko Heinosaari; Oskari Kerppo

doi:10.22331/q-2024-11-07-1515

Maximal Elements of Quantum Communication

Quantum Information and Computation, Faculty of Information Technology, University of Jyväskylä, 40014, Finland

Published:	2024-11-07, volume 8, page 1515
Eprint:	arXiv:2311.16886v2
Doi:	https://doi.org/10.22331/q-2024-11-07-1515
Citation:	Quantum 8, 1515 (2024).

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

Abstract

A prepare-and-measure scenario is naturally described by a communication matrix that collects all conditional outcome probabilities of the scenario into a row-stochastic matrix. The set of all possible communication matrices is partially ordered via the possibility to transform one matrix to another by pre- and post-processings. By considering maximal elements in this preorder for a subset of matrices implementable in a given theory, it becomes possible to identify communication matrices of maximum utility, i.e., matrices that are not majorized by any other matrices in the theory. The identity matrix of an appropriate size is the greatest element in classical theories, while the maximal elements in quantum theory have remained unknown. We completely characterize the maximal elements in quantum theory, thereby revealing the essential structure of the set of quantum communication matrices. In particular, we show that the identity matrix is the only maximal element in quantum theory but, as opposed to a classical theory, it is not the greatest element. Quantum theory can hence be seen to be distinct from classical theory by the existence of incompatible communication matrices.

Featured image: The set of communication matrices is partially ordered via the possibility to transform one matrix to another by pre- and post-processings. Here the communication matrix $G_{4,2}$ is transformed into another matrix called $A_3$.

Popular summary

This article studies the structure of operational theories. A prepare-and-measure scenario can be described by collecting all conditional outcome probabilities into a row-stochastic matrix. We call such matrices communication matrices, and each prepare-and-measure scenario is described by such a matrix. In all operational theories the set of implementable communication matrices is partially ordered via the possibility to transform one matrix to another by pre- and post-processings. By studying this binary relation between communication matrices we are able to identify maximal elements in both classical and quantum theory. Namely, we find that the identity matrix of appropriate size is a the greatest element in classical theory, while in quantum theory the identity matrix is maximal. This result allows us to conclude that there exists incompatible communication matrices in quantum theory, where compatibility is defined as the existence of a common greater element in the implementable set. Thus our result is a first step in the study of compatibility of prepare-and-measure scenarios.

► BibTeX data

@article{Heinosaari2024maximalelementsof,
  doi = {10.22331/q-2024-11-07-1515},
  url = {https://doi.org/10.22331/q-2024-11-07-1515},
  title = {Maximal {E}lements of {Q}uantum {C}ommunication},
  author = {Heinosaari, Teiko and Kerppo, Oskari},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {8},
  pages = {1515},
  month = nov,
  year = {2024}
}

► References

[1] C. H. Bennett and S. J. Wiesner. ``Communication via one- and two-particle operators on Einstein-Podolsky-Rosen states''. Phys. Rev. Lett. 69, 2881 (1992).
https://doi.org/10.1103/PhysRevLett.69.2881

[2] C. H. Bennett, G. Brassard, C. Crépeau, R. Jozsa, A. Peres, and W. K. Wootters. ``Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels''. Phys. Rev. Lett. 70, 1895 (1993).
https://doi.org/10.1103/PhysRevLett.70.1895

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

[4] S. Massar, D. Bacon, N. J. Cerf, and R. Cleve. ``Classical simulation of quantum entanglement without local hidden variables''. Phys. Rev. A 63, 052305 (2001).
https://doi.org/10.1103/PhysRevA.63.052305

[5] B. F. Toner and D. Bacon. ``Communication cost of simulating bell correlations''. Phys. Rev. Lett. 91, 187904 (2003).
https://doi.org/10.1103/PhysRevLett.91.187904

[6] M. J. Renner, A. Tavakoli, and M. T. Quintino. ``Classical cost of transmitting a qubit''. Phys. Rev. Lett. 130, 120801 (2023).
https://doi.org/10.1103/PhysRevLett.130.120801

[7] A. Ambainis, D. Leung, L. Mancinska, and M. Ozols. ``Quantum random access codes with shared randomness'' (2009). arXiv:0810.2937.
arXiv:0810.2937

[8] T. Guha, M. Alimuddin, S. Rout, A. Mukherjee, S. S. Bhattacharya, and M. Banik. ``Quantum Advantage for Shared Randomness Generation''. Quantum 5, 569 (2021).
https://doi.org/10.22331/q-2021-10-27-569

[9] R. Gallego, N. Brunner, C. Hadley, and A. Acín. ``Device-independent tests of classical and quantum dimensions''. Phys. Rev. Lett. 105, 230501 (2010).
https://doi.org/10.1103/PhysRevLett.105.230501

[10] R. Chaves, J. B. Brask, and N. Brunner. ``Device-independent tests of entropy''. Phys. Rev. Lett. 115, 110501 (2015).
https://doi.org/10.1103/PhysRevLett.115.110501

[11] S. Saha, S. S. Bhattacharya, T. Guha, S. Halder, and M. Banik. ``Advantage of quantum theory over nonclassical models of communication''. Annalen der Physik 532, 2000334 (2020).
https://doi.org/10.1002/andp.202000334

[12] H. Buhrman, R. Cleve, J. Watrous, and R. de Wolf. ``Quantum fingerprinting''. Phys. Rev. Lett. 87, 167902 (2001).
https://doi.org/10.1103/PhysRevLett.87.167902

[13] A. Ambainis, A. Nayak, A. Ta-Shma, and U. Vazirani. ``Dense quantum coding and quantum finite automata''. J. ACM 49, 496 (2002).
https://doi.org/10.1145/581771.581773

[14] C. Perry, R. Jain, and J. Oppenheim. ``Communication tasks with infinite quantum-classical separation''. Phys. Rev. Lett. 115, 030504 (2015).
https://doi.org/10.1103/PhysRevLett.115.030504

[15] P. Emeriau, M. Howard, and S. Mansfield. ``Quantum advantage in information retrieval''. PRX Quantum 3, 020307 (2022).
https://doi.org/10.1103/PRXQuantum.3.020307

[16] E. F. Galvão and L. Hardy. ``Substituting a qubit for an arbitrarily large number of classical bits''. Phys. Rev. Lett. 90, 087902 (2003).
https://doi.org/10.1103/PhysRevLett.90.087902

[17] T. Heinosaari, O. Kerppo, L. Leppäjärvi, and M. Plávala. ``Simple information-processing tasks with unbounded quantum advantage''. Phys. Rev. A 109, 032627 (2024).
https://doi.org/10.1103/PhysRevA.109.032627

[18] P. W. Shor. ``Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer''. SIAM Journal on Computing 26, 1484 (1997).
https://doi.org/10.1137/S0097539795293172

[19] F. Arute et al. ``Quantum supremacy using a programmable superconducting processor''. Nature 574, 505 (2019).
https://doi.org/10.1038/s41586-019-1666-5

[20] F. Pan and Pan P. Zhang. ``Simulation of quantum circuits using the big-batch tensor network method''. Phys. Rev. Lett. 128, 030501 (2022).
https://doi.org/10.1103/PhysRevLett.128.030501

[21] T. Heinosaari and O. Kerppo. ``Communication of partial ignorance with qubits''. J. Phys. A: Math. Theor. 52, 395301 (2019).
https://doi.org/10.1088/1751-8121/ab3ae4

[22] T. Heinosaari, O. Kerppo, and L. Leppäjärvi. ``Communication tasks in operational theories''. J. Phys. A: Math. Theor. 53, 435302 (2020).
https://doi.org/10.1088/1751-8121/abb5dc

[23] P. E. Frenkel and M. Weiner. ``Classical information storage in an n-level quantum system''. Commun. Math. Phys. 340, 563 (2015).
https://doi.org/10.1007/s00220-015-2463-0

[24] G. Kimura, K. Nuida, and H. Imai. ``Distinguishability measures and entropies for general probabilistic theories''. Rep. Math. Phys. 66, 175 (2010).
https://doi.org/10.1016/S0034-4877(10)00025-X

[25] S. Bandyopadhyay, R. Jain, J. Oppenheim, and C. Perry. ``Conclusive exclusion of quantum states''. Phys. Rev. A 89, 022336 (2014).
https://doi.org/10.1103/PhysRevA.89.022336

[26] C. M. Caves, C. A. Fuchs, and R. Schack. ``Conditions for compatibility of quantum-state assignments''. Phys. Rev. A 66, 062111 (2002).
https://doi.org/10.1103/PhysRevA.66.062111

[27] T. Heinosaari and O. Kerppo. ``Antidistinguishability of pure quantum states''. J. Phys. A: Math. Theor. 51, 365303 (2018).
https://doi.org/10.1088/1751-8121/aad1fc

[28] J. E. Cohen and U. G. Rothblum. ``Nonnegative ranks, decompositions, and factorizations of nonnegative matrices''. Linear Algebra Appl. 190, 149 (1993).
https://doi.org/10.1016/0024-3795(93)90224-C

[29] H. Fawzi, J. Gouveia, P. A. Parrilo, R. Z. Robinson, and R. R. Thomas. ``Positive semidefinite rank''. Mathematical Programming 153, 133 (2015).
https://doi.org/10.1007/s10107-015-0922-1

[30] T. Lee, Z. Wei, and R. de Wolf. ``Some upper and lower bounds on psd-rank''. Math. Program. 162, 495 (2017).
https://doi.org/10.1007/s10107-016-1052-0

[31] K. Matsumoto and G. Kimura. ``Information storing yields a point-asymmetry of state space in general probabilistic theories'' (2022). arXiv:1802.01162.
arXiv:1802.01162

[32] B. Schumacher and M. Westmoreland. ``Quantum processes, systems, and information''. Cambridge University Press, Cambridge. (2010).
https://doi.org/10.1017/CBO9780511814006

[33] O. Kerppo. ``Quantum communication tasks''. PhD thesis. University of Turku. (2023). url: https://urn.fi/URN:ISBN:978-951-29-9127-3.
https://urn.fi/URN:ISBN:978-951-29-9127-3

[34] F. D. Martínez Pería, P. G. Massey, and L. E. Silvestre. ``Weak matrix majorization''. Linear Algebra Appl. 403, 343 (2005).
https://doi.org/10.1016/j.laa.2005.02.003

[35] A. S. Holevo. ``Bounds for the quantity of information transmitted by a quantum communication channel''. Probl. Peredachi Inf. 9, 3 (1973). url: https://www.mathnet.ru/eng/ppi903.
https://www.mathnet.ru/eng/ppi903

[36] M. Plávala. ``General probabilistic theories: An introduction''. Physics Reports 1033, 1 (2023).
https://doi.org/10.1016/j.physrep.2023.09.001

Cited by

[1] Teiko Heinosaari and Mark Hillery, "Can a qudit carry more information than a dit?", Contemporary Physics 65 1, 2 (2024).

[2] 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).

[3] Samgeeth Puliyil, Leevi Leppäjärvi, and Mário Ziman, "Semi-device-independent channel identification with communication matrices", arXiv:2511.14273, (2025).

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

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.