Document Open Access Logo

Separating Quantum Communication and Approximate Rank

Authors Anurag Anshu, Shalev Ben-David, Ankit Garg, Rahul Jain, Robin Kothari, Troy Lee

PDF
Thumbnail PDF

File

LIPIcs.CCC.2017.24.pdf
  • Filesize: 0.7 MB
  • 33 pages

Document Identifiers

Author Details

Anurag Anshu
Shalev Ben-David
Ankit Garg
Rahul Jain
Robin Kothari
Troy Lee

Cite As Get BibTex

Anurag Anshu, Shalev Ben-David, Ankit Garg, Rahul Jain, Robin Kothari, and Troy Lee. Separating Quantum Communication and Approximate Rank. In 32nd Computational Complexity Conference (CCC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 79, pp. 24:1-24:33, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.CCC.2017.24

Abstract

One of the best lower bound methods for the quantum communication complexity of a function H (with or without shared entanglement) is the logarithm of the approximate rank of the communication matrix of H. This measure is essentially equivalent to the approximate gamma-2 norm and generalized discrepancy, and subsumes several other lower bounds. All known lower bounds on quantum communication complexity in the general unbounded-round model can be shown via the logarithm of approximate rank, and it was an open problem to give any separation at all between quantum communication complexity and the logarithm of the approximate rank.

In this work we provide the first such separation: We exhibit a total function H with quantum communication complexity almost quadratically larger than the logarithm of its approximate rank. We construct H using the communication lookup function framework of Anshu et al. (FOCS 2016) based on the cheat sheet framework of Aaronson et al. (STOC 2016). From a starting function F, this framework defines a new function H=F_G. Our main technical result is a lower bound on the quantum communication complexity of F_G in terms of the discrepancy of F, which we do via quantum information theoretic arguments. We show the upper bound on the approximate rank of F_G by relating it to the Boolean circuit size of the starting function F.

Subject Classification

Keywords
  • Communication Complexity
  • Quantum Computing
  • Lower Bounds
  • logrank
  • Quantum Information

Metrics

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

References

  1. Scott Aaronson, Shalev Ben-David, and Robin Kothari. Separations in query complexity using cheat sheets. In Proceedings of the 48th ACM Symposium on Theory of Computing (STOC 2016), pages 863-876, 2016. URL: http://dx.doi.org/10.1145/2897518.2897644.
  2. Andris Ambainis. Polynomial degree vs. quantum query complexity. In Proceedings of the 44th IEEE Symposium on Foundations of Computer Science (FOCS 2003), pages 230-239, 2003. URL: http://dx.doi.org/10.1109/SFCS.2003.1238197.
  3. Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, and Juris Smotrovs. Separations in query complexity based on pointer functions. In Proceedings of the 48th ACM Symposium on Theory of Computing (STOC 2016), 2016. URL: http://dx.doi.org/10.1145/2897518.2897524.
  4. Andris Ambainis, Martins Kokainis, and Robin Kothari. Nearly Optimal Separations Between Communication (or Query) Complexity and Partitions. In 31st Conference on Computational Complexity (CCC 2016), volume 50 of Leibniz International Proceedings in Informatics (LIPIcs), pages 4:1-4:14, Dagstuhl, Germany, 2016. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. URL: http://dx.doi.org/10.4230/LIPIcs.CCC.2016.4.
  5. Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika Göös, Rahul Jain, Robin Kothari, Troy Lee, and Miklos Santha. Separations in communication complexity using cheat sheets and information complexity. Proceedings of the 57h IEEE Symposium on Foundations of Computer Science (FOCS 2016), 2016. arXiv preprint http://arxiv.org/abs/arXiv:1605.01142. Google Scholar
  6. Koenraad M. R. Audenaert. Quantum skew divergence. Journal of Mathematical Physics, 55(11), 2014. URL: http://dx.doi.org/10.1063/1.4901039.
  7. Boaz Barak, Mark Braverman, Xi Chen, and Anup Rao. How to compress interactive communication. SIAM Journal on Computing, 42(3):1327-1363, 2013. URL: http://dx.doi.org/10.1137/100811969.
  8. Howard Barnum, Carlton M. Caves, Christopher A. Fuchs, Richard Jozsa, and Benjamin Schmacher. Noncommuting mixed states cannot be broadcast. Phys. Rev. Lett., 76(15):2818-2821, 1996. URL: http://dx.doi.org/10.1103/PhysRevLett.76.2818.
  9. M. Braverman, A. Rao, O. Weinstein, and A. Yehudayoff. Direct products in communication complexity. In 54th Annual Symposium on Foundations of Computer Science (FOCS 2013), pages 746-755, Oct 2013. URL: http://dx.doi.org/10.1109/FOCS.2013.85.
  10. Mark Braverman, Ankit Garg, Young Kun Ko, Jieming Mao, and Dave Touchette. Near-optimal bounds on bounded-round quantum communication complexity of disjointness. In Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on, pages 773-791, Oct 2015. URL: http://dx.doi.org/10.1109/FOCS.2015.53.
  11. Mark Braverman and Omri Weinstein. An interactive information odometer and applications. In Proceedings of the 47th Annual ACM on Symposium on Theory of Computing, STOC'15, pages 341-350, 2015. URL: http://dx.doi.org/10.1145/2746539.2746548.
  12. Harry Buhrman, Richard Cleve, and Avi Wigderson. Quantum vs. classical communication and computation. In Proceedings of the 30th Annual ACM Symposium on Theory of Computing, STOC'98, pages 63-68, 1998. URL: http://dx.doi.org/10.1145/276698.276713.
  13. Harry Buhrman and Ronald de Wolf. Communication complexity lower bounds by polynomials. In Proceedings of the 16th IEEE Conference on Computational Complexity, pages 120-130. IEEE, 2001. URL: http://dx.doi.org/10.1109/CCC.2001.933879.
  14. Donald Bures. An extension of Kakutani’s theorem on infinite product measures to the tensor product of semifinite ω^*-algebras. Transactions of the American Mathematical Society, 135:199-212, 1969. URL: http://dx.doi.org/10.2307/1995012.
  15. Richard Cleve, Wim van Dam, Michael Nielsen, and Alain Tapp. Quantum entanglement and the communication complexity of the inner product function. Theoretical Computer Science, 486:11-19, 2013. URL: http://dx.doi.org/10.1016/j.tcs.2012.12.012.
  16. Andrew Drucker. The Complexity of Joint Computation. PhD thesis, Massachusetts Institute of Technology, 2012. Google Scholar
  17. Jürgen Forster. A linear lower bound on the unbounded error probabilistic communication complexity. Journal of Computer and System Sciences, 65(4):612-625, 2002. Special Issue on Complexity 2001. URL: http://dx.doi.org/10.1016/S0022-0000(02)00019-3.
  18. Christopher A. Fuchs and Jeroen van de Graaf. Cryptographic distinguishability measures for quantum-mechanical states. IEEE Transactions on Information Theory, 45(4):1216-1227, May 1999. URL: http://dx.doi.org/10.1109/18.761271.
  19. Mika Göös, T. S. Jayram, Toniann Pitassi, and Thomas Watson. Randomized communication vs. partition number. Electronic Colloquium on Computational Complexity (ECCC) http://eccc.hpi-web.de/report/2015/169/, 2015.
  20. Mika Göös, Toniann Pitassi, and Thomas Watson. Deterministic communication vs. partition number. In Proceedings of the 56th IEEE Symposium on Foundations of Computer Science (FOCS), pages 1077-1088, 2015. URL: http://dx.doi.org/10.1109/FOCS.2015.70.
  21. Lov K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the 28th ACM Symposium on Theory of Computing (STOC), pages 212-219, 1996. URL: http://dx.doi.org/10.1145/237814.237866.
  22. Rahul Jain and Ashwin Nayak. Accessible versus Holevo information for a binary random variable. Preprint, 2006. URL: http://arxiv.org/abs/quant-ph/0603278.
  23. Rahul Jain, Jaikumar Radhakrishnan, and Pranab Sen. A lower bound for the bounded round quantum communication complexity of set disjointness. In Proceedings of the 44th IEEE Symposium on Foundations of Computer Science (FOCS 2003), pages 220-229, Oct 2003. URL: http://dx.doi.org/10.1109/SFCS.2003.1238196.
  24. Hartmut Klauck. Lower bounds for quantum communication complexity. SIAM Journal on Computing, 37(1):20-46, 2007. URL: http://dx.doi.org/10.1137/S0097539702405620.
  25. Gillat Kol, Shay Moran, Amir Shpilka, and Amir Yehudayoff. Approximate nonnegative rank is equivalent to the smooth rectangle bound. In Automata, Languages, and Programming: 41st International Colloquium (ICALP 2014), pages 701-712. Springer Berlin Heidelberg, 2014. URL: http://dx.doi.org/10.1007/978-3-662-43948-7_58.
  26. Ilan Kremer. Quantum communication. Master’s thesis, The Hebrew University of Jerusalem, 1995. URL: http://www.cs.huji.ac.il/~noam/kremer-thesis.ps.
  27. Eyal Kushilevitz and Noam Nisan. Communication Complexity. Cambridge University Press, 2006. Google Scholar
  28. Sophie Laplante, Troy Lee, and Mario Szegedy. The quantum adversary method and classical formula size lower bounds. Computational Complexity, 15:163-196, 2006. URL: http://dx.doi.org/10.1007/s00037-006-0212-7.
  29. Sophie Laplante, Virginie Lerays, and Jérémie Roland. Classical and quantum partition bound and detector inefficiency. In Proceedings of the 39th International Colloquium Conference on Automata, Languages, and Programming - Volume Part I, ICALP'12, pages 617-628, Berlin, Heidelberg, 2012. Springer-Verlag. URL: http://dx.doi.org/10.1007/978-3-642-31594-7_52.
  30. Troy Lee and Jérémie Roland. A strong direct product theorem for quantum query complexity. Computational Complexity, 22(2):429-462, 2013. URL: http://dx.doi.org/10.1007/s00037-013-0066-8.
  31. Troy Lee and Adi Shraibman. An approximation algorithm for approximation rank. In Proceedings of the 24th IEEE Conference on Computational Complexity, pages 351-357, 2008. URL: http://dx.doi.org/10.1109/CCC.2009.25.
  32. Göran Lindblad. Completely positive maps and entropy inequalities. Communications in Mathematical Physics, 40(2):147-151, 1975. URL: http://dx.doi.org/10.1007/BF01609396.
  33. Nati Linial and Adi Shraibman. Lower bounds in communication complexity based on factorization norms. Random Structures &Algorithms, 34(3):368-394, 2009. URL: http://dx.doi.org/10.1002/rsa.20232.
  34. Ashwin Nayak and Dave Touchette. Augmented index and quantum streaming algorithms for DYCK(2). arXiv preprint http://arxiv.org/abs/arXiv:1610.04937, 2016. Google Scholar
  35. Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge Series on Information and the Natural Sciences. CUP, 2000. Google Scholar
  36. Alexander Razborov. Quantum communication complexity of symmetric predicates. Izvestiya: Mathematics, 67(1):145, 2003. URL: http://dx.doi.org/10.1070/IM2003v067n01ABEH000422.
  37. Ben W. Reichardt. Reflections for quantum query algorithms. In Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA 2011), SODA'11, pages 560-569, 2011. URL: http://dl.acm.org/citation.cfm?id=2133036.2133080.
  38. Alexander A. Sherstov. The pattern matrix method. SIAM Journal on Computing, 40(6):1969-2000, 2011. URL: http://dx.doi.org/10.1137/080733644.
  39. Alexander A. Sherstov. Strong direct product theorems for quantum communication and query complexity. SIAM Journal on Computing, 41(5):1122-1165, 2012. URL: http://dx.doi.org/10.1137/110842661.
  40. Yaoyun Shi and Yufan Zhu. Quantum communication complexity of block-composed functions. Quantum information and computation, 9(5,6):444-460, 2009. URL: http://arxiv.org/abs/0710.0095.
  41. Maurice Sion. On general minimax theorems. Pacific J. of Mathematics, 1:171–176, 1958. Google Scholar
  42. Marco Tomamichel. Quantum Information Processing with Finite Resources: Mathematical Foundations. SpringerBriefs in Mathematical Physics. Springer, 2016. URL: http://dx.doi.org/10.1007/978-3-319-21891-5.
  43. Dave Touchette. Quantum information complexity. In Proceedings of the 47th Annual ACM on Symposium on Theory of Computing, STOC'15, pages 317-326. ACM, 2015. URL: http://dx.doi.org/10.1145/2746539.2746613.
  44. A. Uhlmann. The "transition probability" in the state space of a *-algebra. Reports on Mathematical Physics, 9:273-279, 1976. URL: http://dx.doi.org/10.1016/0034-4877(76)90060-4.
  45. John Watrous. Theory of Quantum Information. Unpublished, January 2016. Available at https://cs.uwaterloo.ca/~watrous/TQI/.
  46. Mark M. Wilde. Quantum Information Theory. Cambridge University Press, Cambridge, 12 2012. URL: http://dx.doi.org/10.1017/CBO9781139525343.
  47. Andrew Yao. Quantum circuit complexity. In Proceedings of the 34th IEEE Symposium on Foundations of Computer Science (FOCS 1993), pages 352-360, 1993. URL: http://dx.doi.org/10.1109/SFCS.1993.366852.
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 About DROPS Imprint Privacy Contact