Doubly infinite separation of quantum information and communication
We prove the existence of (one-way) communication tasks with a subconstant versus superconstant asymptotic gap, which we call “doubly infinite,” between their quantum information and communication complexities. We do so by studying the exclusion game [C. Perry et al., Phys. Rev. Lett. 115, 030504 (2...
| Main Authors: | , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
American Physical Society
2016
|
| Online Access: | http://hdl.handle.net/1721.1/101073 https://orcid.org/0000-0002-4497-2093 https://orcid.org/0000-0002-8968-591X https://orcid.org/0000-0003-1333-4045 |
| _version_ | 1811082869911584768 |
|---|---|
| author | Liu, Zi-Wen Perry, Christopher Zhu, Yechao Koh, Dax Enshan Aaronson, Scott |
| author2 | Massachusetts Institute of Technology. Center for Theoretical Physics |
| author_facet | Massachusetts Institute of Technology. Center for Theoretical Physics Liu, Zi-Wen Perry, Christopher Zhu, Yechao Koh, Dax Enshan Aaronson, Scott |
| author_sort | Liu, Zi-Wen |
| collection | MIT |
| description | We prove the existence of (one-way) communication tasks with a subconstant versus superconstant asymptotic gap, which we call “doubly infinite,” between their quantum information and communication complexities. We do so by studying the exclusion game [C. Perry et al., Phys. Rev. Lett. 115, 030504 (2015)PRLTAO0031-900710.1103/PhysRevLett.115.030504] for which there exist instances where the quantum information complexity tends to zero as the size of the input n increases. By showing that the quantum communication complexity of these games scales at least logarithmically in n, we obtain our result. We further show that the established lower bounds and gaps still hold even if we allow a small probability of error. However in this case, the n-qubit quantum message of the zero-error strategy can be compressed polynomially. |
| first_indexed | 2024-09-23T12:11:05Z |
| format | Article |
| id | mit-1721.1/101073 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T12:11:05Z |
| publishDate | 2016 |
| publisher | American Physical Society |
| record_format | dspace |
| spelling | mit-1721.1/1010732022-10-01T08:40:00Z Doubly infinite separation of quantum information and communication Liu, Zi-Wen Perry, Christopher Zhu, Yechao Koh, Dax Enshan Aaronson, Scott Massachusetts Institute of Technology. Center for Theoretical Physics Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Department of Mathematics Massachusetts Institute of Technology. Department of Physics Liu, Zi-Wen Zhu, Yechao Koh, Dax Enshan Aaronson, Scott We prove the existence of (one-way) communication tasks with a subconstant versus superconstant asymptotic gap, which we call “doubly infinite,” between their quantum information and communication complexities. We do so by studying the exclusion game [C. Perry et al., Phys. Rev. Lett. 115, 030504 (2015)PRLTAO0031-900710.1103/PhysRevLett.115.030504] for which there exist instances where the quantum information complexity tends to zero as the size of the input n increases. By showing that the quantum communication complexity of these games scales at least logarithmically in n, we obtain our result. We further show that the established lower bounds and gaps still hold even if we allow a small probability of error. However in this case, the n-qubit quantum message of the zero-error strategy can be compressed polynomially. United States. Army Research Office (Award W911NF-11-1-0400) United States. Army Research Office (Grant Contract W911NF-12-0486) Singapore. Agency for Science, Technology and Research (National Science Scholarship) National Science Foundation (U.S.) (Alan T. Waterman Award Grant 1249349) 2016-02-02T15:47:54Z 2016-02-02T15:47:54Z 2016-01 2015-11 2016-01-29T23:00:11Z Article http://purl.org/eprint/type/JournalArticle 1050-2947 1094-1622 http://hdl.handle.net/1721.1/101073 Liu, Zi-Wen, Christopher Perry, Yechao Zhu, Dax Enshan Koh, and Scott Aaronson. "Doubly infinite separation of quantum information and communication." Phys. Rev. A 93, 012347 (January 2016). © 2016 American Physical Society https://orcid.org/0000-0002-4497-2093 https://orcid.org/0000-0002-8968-591X https://orcid.org/0000-0003-1333-4045 en http://dx.doi.org/10.1103/PhysRevA.93.012347 Physical Review A Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. American Physical Society application/pdf American Physical Society American Physical Society |
| spellingShingle | Liu, Zi-Wen Perry, Christopher Zhu, Yechao Koh, Dax Enshan Aaronson, Scott Doubly infinite separation of quantum information and communication |
| title | Doubly infinite separation of quantum information and communication |
| title_full | Doubly infinite separation of quantum information and communication |
| title_fullStr | Doubly infinite separation of quantum information and communication |
| title_full_unstemmed | Doubly infinite separation of quantum information and communication |
| title_short | Doubly infinite separation of quantum information and communication |
| title_sort | doubly infinite separation of quantum information and communication |
| url | http://hdl.handle.net/1721.1/101073 https://orcid.org/0000-0002-4497-2093 https://orcid.org/0000-0002-8968-591X https://orcid.org/0000-0003-1333-4045 |
| work_keys_str_mv | AT liuziwen doublyinfiniteseparationofquantuminformationandcommunication AT perrychristopher doublyinfiniteseparationofquantuminformationandcommunication AT zhuyechao doublyinfiniteseparationofquantuminformationandcommunication AT kohdaxenshan doublyinfiniteseparationofquantuminformationandcommunication AT aaronsonscott doublyinfiniteseparationofquantuminformationandcommunication |