Quasirandom quantum channels

Tom Bannink; Jop Briët; Farrokh Labib; Hans Maassen

doi:10.22331/q-2020-07-16-298

Quasirandom quantum channels

Tom Bannink¹, Jop Briët², Farrokh Labib¹, and Hans Maassen³

¹CWI, QuSoft, Science Park 123, 1098 XG Amsterdam, Netherlands. Supported by the Gravitation-grant NETWORKS-024.002.003 from the Dutch Research Council (NWO).
²CWI, QuSoft, Science Park 123, 1098 XG Amsterdam, Netherlands. Supported by the Gravitation-grant NETWORKS-024.002.003 from the Dutch Research Council (NWO). Additionally supported by an NWO VENI grant.
³QuSoft, Korteweg-de Vries Institute for Mathematics, Radboud University.

Published:	2020-07-16, volume 4, page 298
Eprint:	arXiv:1908.06310v3
Doi:	https://doi.org/10.22331/q-2020-07-16-298
Citation:	Quantum 4, 298 (2020).

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

Abstract

Mixing (or quasirandom) properties of the natural transition matrix associated to a graph can be quantified by its distance to the complete graph. Different mixing properties correspond to different norms to measure this distance. For dense graphs, two such properties known as spectral expansion and uniformity were shown to be equivalent in seminal 1989 work of Chung, Graham and Wilson. Recently, Conlon and Zhao extended this equivalence to the case of sparse vertex transitive graphs using the famous Grothendieck inequality.
Here we generalize these results to the non-commutative, or `quantum', case, where a transition matrix becomes a quantum channel. In particular, we show that for irreducibly covariant quantum channels, expansion is equivalent to a natural analog of uniformity for graphs, generalizing the result of Conlon and Zhao. Moreover, we show that in these results, the non-commutative and commutative (resp.) Grothendieck inequalities yield the best-possible constants.

► BibTeX data

@article{Bannink2020quasirandomquantum,
  doi = {10.22331/q-2020-07-16-298},
  url = {https://doi.org/10.22331/q-2020-07-16-298},
  title = {Quasirandom quantum channels},
  author = {Bannink, Tom and Bri{\"{e}}t, Jop and Labib, Farrokh and Maassen, Hans},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {4},
  pages = {298},
  month = jul,
  year = {2020}
}

► References

[1] Andris Ambainis and Adam Smith. Small pseudo-random families of matrices: Derandomizing approximate quantum encryption. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 249–260. Springer, 2004. 10.1007/978-3-540-27821-4_23. URL http://dx.doi.org/10.1007/978-3-540-27821-4_23.
https://doi.org/10.1007/978-3-540-27821-4_23

[2] Guillaume Aubrun. On almost randomizing channels with a short Kraus decomposition. Comm. Math. Phys., 288 (3): 1103–1116, 2009. ISSN 0010-3616. 10.1007/s00220-008-0695-y. URL https://doi.org/10.1007/s00220-008-0695-y.
https://doi.org/10.1007/s00220-008-0695-y

[3] Avraham Ben-Aroya, Oded Schwartz, and Amnon Ta-Shma. Quantum expanders: Motivation and construction. Theory of Computing, 6 (1): 47–79, 2010. 10.4086/toc.2010.v006a003. URL https://doi.org/10.4086/toc.2010.v006a003.
https://doi.org/10.4086/toc.2010.v006a003

[4] Béla Bollobás and Vladimir Nikiforov. Hermitian matrices and graphs: singular values and discrepancy. Discrete Math., 285 (1-3): 17–32, 2004. ISSN 0012-365X. 10.1016/j.disc.2004.05.006. URL https://doi.org/10.1016/j.disc.2004.05.006.
https://doi.org/10.1016/j.disc.2004.05.006

[5] M. Braverman, K. Makarychev, Y. Makarychev, and A. Naor. The Grothendieck constant is strictly smaller than Krivine's bound. Forum Math. Pi, 1: 453–462, 2013. 10.1017/fmp.2013.4. URL http://dx.doi.org/10.1017/fmp.2013.4. Preliminary version in FOCS'11. arXiv: 1103.6161.
https://doi.org/10.1017/fmp.2013.4

[6] Jop Briët. Grothendieck inequalities, nonlocal games and optimization. PhD thesis, Institute for Logic, Language and Computation, 2011.

[7] Fan Chung and Ronald Graham. Sparse quasi-random graphs. Combinatorica, 22 (2): 217–244, 2002. ISSN 0209-9683. 10.1007/s004930200010. URL https://doi.org/10.1007/s004930200010. Special issue: Paul Erdős and his mathematics.
https://doi.org/10.1007/s004930200010

[8] Fan R. K. Chung, Ronald L. Graham, and Richard M. Wilson. Quasi-random graphs. Combinatorica, 9 (4): 345–362, 1989. 10.1007/BF02125347. URL https://doi.org/10.1007/BF02125347.
https://doi.org/10.1007/BF02125347

[9] David Conlon and Yufei Zhao. Quasirandom Cayley graphs. Discrete Anal., pages Paper No. 6, 14, 2017. ISSN 2397-3129. 10.19086/da.1294. URL http://dx.doi.org/10.19086/da.1294.
https://doi.org/10.19086/da.1294

[10] Tom Cooney, Marius Junge, Carlos Palazuelos, and David Pérez-García. Rank-one quantum games. computational complexity, 24 (1): 133–196, 2015. 10.1007/s00037-014-0096-x. URL http://dx.doi.org/10.1007/s00037-014-0096-x.
https://doi.org/10.1007/s00037-014-0096-x

[11] A. Davie. Lower bound for $K_G$. Unpublished, 1984.

[12] William Fulton and Joe Harris. Representation theory: a first course, volume 129. Springer Science & Business Media, 2013. 10.1007/978-1-4612-0979-9. URL http://dx.doi.org/10.1007/978-1-4612-0979-9.
https://doi.org/10.1007/978-1-4612-0979-9

[13] A. Grothendieck. Résumé de la théorie métrique des produits tensoriels topologiques. Bol. Soc. Mat. São Paulo, 8: 1–79, 1953.

[14] Uffe Haagerup. The Grothendieck inequality for bilinear forms on $C^\ast$-algebras. Adv. in Math., 56 (2): 93–116, 1985. ISSN 0001-8708. 10.1016/0001-8708(85)90026-X. URL https://doi.org/10.1016/0001-8708(85)90026-X.
https://doi.org/10.1016/0001-8708(85)90026-X

[15] Uffe Haagerup. A new upper bound for the complex Grothendieck constant. Israel J. Math., 60 (2): 199–224, 1987. ISSN 0021-2172. 10.1007/BF02790792. URL http://dx.doi.org/10.1007/BF02790792.
https://doi.org/10.1007/BF02790792

[16] Uffe Haagerup and Takashi Itoh. Grothendieck type norms for bilinear forms on $C^*$-algebras. J. Operator Theory, 34 (2): 263–283, 1995. ISSN 0379-4024.

[17] Aram W. Harrow. Quantum expanders from any classical cayley graph expander. Quantum Information & Computation, 8 (8): 715–721, 2008. URL http://www.rintonpress.com/xxqic8/qic-8-89/0715-0721.pdf.
http://www.rintonpress.com/xxqic8/qic-8-89/0715-0721.pdf

[18] Matthew B. Hastings. Random unitaries give quantum expanders. Phys. Rev. A (3), 76 (3): 032315, 11, 2007. ISSN 1050-2947. 10.1103/PhysRevA.76.032315. URL https://doi.org/10.1103/PhysRevA.76.032315.
https://doi.org/10.1103/PhysRevA.76.032315

[19] Matthew B Hastings. Superadditivity of communication capacity using entangled inputs. Nature Physics, 5 (4): 255, 2009. 10.1038/nphys1224. URL http://dx.doi.org/10.1038/nphys1224.
https://doi.org/10.1038/nphys1224

[20] Matthew B. Hastings and Aram W. Harrow. Classical and quantum tensor product expanders. Quantum Information & Computation, 9 (3): 336–360, 2009. URL http://www.rintonpress.com/xxqic9/qic-9-34/0336-0360.pdf.
http://www.rintonpress.com/xxqic9/qic-9-34/0336-0360.pdf

[21] Alexander S Holevo. Remarks on the classical capacity of quantum channel. arXiv preprint quant-ph/0212025, 2002.
arXiv:quant-ph/0212025

[22] Alexander S. Holevo. The additivity problem in quantum information theory. In International Congress of Mathematicians. Vol. III, pages 999–1018. Eur. Math. Soc., Zürich, 2006.

[23] Shlomo Hoory, Nathan Linial, and Avi Wigderson. Expander graphs and their applications. Bull. Amer. Math. Soc., 43: 439–561, 2006. 10.1090/S0273-0979-06-01126-8. URL http://dx.doi.org/10.1090/S0273-0979-06-01126-8.
https://doi.org/10.1090/S0273-0979-06-01126-8

[24] Yoshiharu Kohayakawa, Vojtěch Rödl, and Mathias Schacht. Discrepancy and eigenvalues of Cayley graphs. Czechoslovak Math. J., 66(141) (3): 941–954, 2016. ISSN 0011-4642. 10.1007/s10587-016-0302-x. URL https://doi.org/10.1007/s10587-016-0302-x.
https://doi.org/10.1007/s10587-016-0302-x

[25] M. Krivelevich and B. Sudakov. Pseudo-random graphs. In More sets, graphs and numbers, volume 15 of Bolyai Soc. Math. Stud., pages 199–262. Springer, Berlin, 2006. 10.1007/978-3-540-32439-3_10. URL https://doi.org/10.1007/978-3-540-32439-3_10.
https://doi.org/10.1007/978-3-540-32439-3_10

[26] Alexander Lubotzky, Ralph Phillips, and Peter Sarnak. Ramanujan graphs. Combinatorica, 8 (3): 261–277, 1988. 10.1007/BF02126799. URL http://dx.doi.org/10.1007/BF02126799.
https://doi.org/10.1007/BF02126799

[27] Grigorii Aleksandrovich Margulis. Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators. Problems of Information Transmission, 24 (1): 39–46, 1988.

[28] Assaf Naor, Oded Regev, and Thomas Vidick. Efficient rounding for the noncommutative Grothendieck inequality. Theory Comput., 10 (11): 257–295, 2014. 10.1145/2488608.2488618. URL http://dx.doi.org/10.1145/2488608.2488618. Earlier version in STOC'13.
https://doi.org/10.1145/2488608.2488618

[29] Gilles Pisier. Grothendieck's theorem, past and present. Bull. Amer. Math. Soc. (N.S.), 49 (2): 237–323, 2012. ISSN 0273-0979. 10.1090/S0273-0979-2011-01348-9. URL https://doi.org/10.1090/S0273-0979-2011-01348-9.
https://doi.org/10.1090/S0273-0979-2011-01348-9

[30] J. Reeds. A new lower bound on the real Grothendieck constant, 1991.

[31] Oded Regev and Thomas Vidick. Quantum XOR games. ACM Trans. Comput. Theory, 7 (4): Art. 15, 43, 2015. ISSN 1942-3454. 10.1145/2799560. URL https://doi.org/10.1145/2799560.
https://doi.org/10.1145/2799560

[32] Barry Simon. Representations of finite and compact groups. Number 10. American Mathematical Soc., 1996. 10.1090/gsm/010. URL http://dx.doi.org/10.1090/gsm/010.
https://doi.org/10.1090/gsm/010

[33] Andrew Thomason. Pseudorandom graphs. In Random graphs '85 (Poznań, 1985), volume 144 of North-Holland Math. Stud., pages 307–331. North-Holland, Amsterdam, 1987a.
https://doi.org/10.1016/S0304-0208(08)73063-9

[34] Andrew Thomason. Random graphs, strongly regular graphs and pseudorandom graphs. In Surveys in combinatorics 1987 (New Cross, 1987), volume 123 of London Math. Soc. Lecture Note Ser., pages 173–195. Cambridge Univ. Press, Cambridge, 1987b.

Cited by

[1] Cécilia Lancien, "Characterizing expansion, classically and quantumly", Quantum Views 4, 44 (2020).

[2] Yinan Li, Youming Qiao, Avi Wigderson, Yuval Wigderson, and Chuanqi Zhang, "Connections between graphs and matrix spaces", Israel Journal of Mathematics 256 2, 513 (2023).

The above citations are from Crossref's cited-by service (last updated successfully 2024-08-31 20:28:17). The list may be incomplete as not all publishers provide suitable and complete citation data.

On SAO/NASA ADS no data on citing works was found (last attempt 2024-08-31 20:28:17).

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.

Quasirandom quantum channels

Abstract

► BibTeX data

► References

Cited by

1 thought on “Quasirandom quantum channels”