Quasirandom quantum channels

Tom Bannink1, Jop Briët2, Farrokh Labib1, and Hans Maassen3

1CWI, QuSoft, Science Park 123, 1098 XG Amsterdam, Netherlands. Supported by the Gravitation-grant NETWORKS-024.002.003 from the Dutch Research Council (NWO).
2CWI, 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.
3QuSoft, Korteweg-de Vries Institute for Mathematics, Radboud University.

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


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

► 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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

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

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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

On Crossref's cited-by service no data on citing works was found (last attempt 2020-08-10 16:34:36). On SAO/NASA ADS no data on citing works was found (last attempt 2020-08-10 16:34:37).