Document Open Access Logo

Quasirandom Quantum Channels

Authors Tom Bannink, Jop Briët, Farrokh Labib, Hans Maassen

PDF
Thumbnail PDF

File

LIPIcs.TQC.2020.5.pdf
  • Filesize: 0.51 MB
  • 20 pages

Document Identifiers

Author Details

Tom Bannink
  • CWI, 1098 XG Amsterdam, Netherlands
  • QuSoft, Science Park 123, 1098 XG Amsterdam, Netherlands
Jop Briët
  • CWI, 1098 XG Amsterdam, Netherlands
  • QuSoft, Science Park 123, 1098 XG Amsterdam, Netherlands
Farrokh Labib
  • CWI, 1098 XG Amsterdam, Netherlands
  • QuSoft, Science Park 123, 1098 XG Amsterdam, Netherlands
Hans Maassen
  • QuSoft, Science Park 123, 1098 XG Amsterdam, Netherlands
  • Korteweg-de Vries Institute for Mathematics, Radboud University, Nijmegen, Netherlands

Funding

  • Bannink, Tom: Supported by the Gravitation-grant NETWORKS-024.002.003 from the Dutch Research Council (NWO).
  • Briët, Jop: Supported by the Gravitation-grant NETWORKS-024.002.003 from the Dutch Research Council (NWO). Additionally supported by an NWO VENI grant.
  • Labib, Farrokh: Supported by the Gravitation-grant NETWORKS-024.002.003 from the Dutch Research Council (NWO).

Acknowledgements

We would like to thank Māris Ozols, Michael Walter and Freek Witteveen for fruitful discussions.

Cite AsGet BibTex

Tom Bannink, Jop Briët, Farrokh Labib, and Hans Maassen. Quasirandom Quantum Channels. In 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 158, pp. 5:1-5:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.TQC.2020.5

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Quantum information theory
Keywords
  • Quantum channels
  • quantum expanders
  • quasirandomness

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Andris Ambainis and Adam Smith. Small pseudo-random families of matrices: Derandomizing approximate quantum encryption. In Klaus Jansen, Sanjeev Khanna, José D. P. Rolim, and Dana Ron, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 249-260, Berlin, Heidelberg, 2004. Springer Berlin Heidelberg. Google Scholar
  2. Guillaume Aubrun. On almost randomizing channels with a short Kraus decomposition. Comm. Math. Phys., 288(3):1103-1116, 2009. 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. 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. 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. Preliminary version in FOCS'11. URL: https://arxiv.org/abs/1103.6161.
  6. Jop Briët. Grothendieck inequalities, nonlocal games and optimization. PhD thesis, Institute for Logic, Language and Computation, 2011. Google Scholar
  7. Fan Chung and Ronald Graham. Sparse quasi-random graphs. Combinatorica, 22(2):217-244, 2002. Special issue: Paul Erdős and his mathematics. URL: 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. URL: https://doi.org/10.1007/BF02125347.
  9. David Conlon and Yufei Zhao. Quasirandom Cayley graphs. Discrete Anal., pages Paper No. 6, 14, 2017. Google Scholar
  10. Tom Cooney, Marius Junge, Carlos Palazuelos, and David Pérez-García. Rank-one quantum games. computational complexity, 24(1):133-196, 2015. Google Scholar
  11. A. Davie. Lower bound for K_G. Unpublished, 1984. Google Scholar
  12. William Fulton and Joe Harris. Representation theory: a first course, volume 129. Springer Science & Business Media, 2013. Google Scholar
  13. A. Grothendieck. Résumé de la théorie métrique des produits tensoriels topologiques. Bol. Soc. Mat. S~ao Paulo, 8:1-79, 1953. Google Scholar
  14. Uffe Haagerup. The Grothendieck inequality for bilinear forms on C^∗-algebras. Adv. in Math., 56(2):93-116, 1985. 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. URL: 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. Google Scholar
  17. Aram Wettroth 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. M. B. Hastings. Random unitaries give quantum expanders. Phys. Rev. A (3), 76(3):032315, 11, 2007. 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. Google Scholar
  20. Matthew B. Hastings and Aram Wettroth 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. Google Scholar
  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. Google Scholar
  23. Shlomo Hoory, Nathan Linial, and Avi Wigderson. Expander graphs and their applications. Bull. Amer. Math. Soc., 43:439-561, 2006. Google Scholar
  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. 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. 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. Google Scholar
  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. Google Scholar
  28. Assaf Naor, Oded Regev, and Thomas Vidick. Efficient rounding for the noncommutative Grothendieck inequality. Theory Comput., 10(11):257-295, 2014. Earlier version in STOC'13. Google Scholar
  29. Gilles Pisier. Grothendieck’s theorem, past and present. Bull. Amer. Math. Soc. (N.S.), 49(2):237-323, 2012. URL: https://doi.org/10.1090/S0273-0979-2011-01348-9.
  30. J. Reeds. A new lower bound on the real Grothendieck constant. Manuscript (http://www.dtc.umn.edu/~reedsj/bound2.dvi), 1991. URL: http://www.dtc.umn.edu/~reedsj/bound2.dvi.
  31. Oded Regev and Thomas Vidick. Quantum XOR games. ACM Trans. Comput. Theory, 7(4):Art. 15, 43, 2015. URL: https://doi.org/10.1145/2799560.
  32. Barry Simon. Representations of finite and compact groups. Number 10. American Mathematical Soc., 1996. Google Scholar
  33. Andrew Thomason. Pseudorandom graphs. In Random graphs '85 (Poznań, 1985), volume 144 of North-Holland Math. Stud., pages 307-331. North-Holland, Amsterdam, 1987. Google Scholar
  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, 1987. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact