Please use this identifier to cite or link to this item:
https://hdl.handle.net/10356/88427
Title: | Separating quantum communication and approximate rank | Authors: | Anshu, Anurag Garg, Ankit Kothari, Robin Ben-David, Shalev Jain, Rahul Lee, Troy |
Keywords: | DRNTU::Science::Mathematics Communication Complexity Quantum Computing |
Issue Date: | 2017 | Source: | Anshu, A., Ben-David, S., Garg, A., Jain, R., Kothari, R., & Lee, T. (2017). Separating quantum communication and approximate rank. Leibniz International Proceedings in Informatics (LIPIcs), 79, 24-. doi: 10.4230/LIPIcs.CCC.2017.24 | Series/Report no.: | Leibniz International Proceedings in Informatics | 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. | URI: | https://hdl.handle.net/10356/88427 http://hdl.handle.net/10220/45784 |
ISSN: | 1868-8969 | DOI: | 10.4230/LIPIcs.CCC.2017.24 | Schools: | School of Physical and Mathematical Sciences | Rights: | © Anurag Anshu, Shalev Ben-David, Ankit Garg, Rahul Jain, Robin Kothari, and Troy Lee; licensed under Creative Commons License CC-BY 32nd Computational Complexity Conference (CCC 2017). Editor: Ryan O’Donnell; Article No. 24; pp. 24:1–24:33 | Fulltext Permission: | open | Fulltext Availability: | With Fulltext |
Appears in Collections: | SPMS Journal Articles |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Separating Quantum Communication and Approximate Rank.pdf | 722.88 kB | Adobe PDF | View/Open |
SCOPUSTM
Citations
50
6
Updated on Mar 20, 2024
Web of ScienceTM
Citations
50
5
Updated on Oct 26, 2023
Page view(s) 20
695
Updated on Mar 28, 2024
Download(s) 50
59
Updated on Mar 28, 2024
Google ScholarTM
Check
Altmetric
Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.