License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2017.47
URN: urn:nbn:de:0030-drops-81898
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8189/
Go to the corresponding LIPIcs Volume Portal

Laurière, Mathieu ; Touchette, Dave

The Flow of Information in Interactive Quantum Protocols: the Cost of Forgetting

pdf-format:
LIPIcs-ITCS-2017-47.pdf (0.3 MB)

Abstract

In two-party interactive quantum communication protocols,
we study a recently defined notion of quantum information cost (QIC), which has most of the important properties of its classical analogue (IC). Notably, its link with amortized quantum communication complexity has been used to prove an (almost) tight lower bound on the bounded round quantum complexity of Disjointness.
However, QIC was defined through a purification of the input state. This is valid for fully quantum inputs and tasks but difficult to interpret even for classical tasks.
Also, its link with other notions of information cost that had appeared in the literature was not clear.

We settle both these issues: for quantum communication with classical inputs, we characterize QIC in terms of information about the input registers, avoiding any reference to the notion of a purification of the classical input state. We provide an operational interpretation of this new characterization as the sum of the costs of revealing and of forgetting information about the inputs.
To obtain this result, we prove a general Information Flow Lemma assessing the transfer of information in general interactive quantum processes. Specializing this lemma to interactive quantum protocols accomplishing classical tasks, we are able to demistify the link between QIC and other previous notions of information cost in quantum protocols. Furthermore, we clarify the link between QIC and IC by simulating quantumly classical protocols.

Finally, we apply these concepts to argue that any quantum protocol that does not forget information solves Disjointness on n-bits in Omega(n) communication, completely losing the quadratic quantum speedup. Hence forgetting information is here a necessary feature in order to obtain any significant improvement over classical protocols. We also prove that QIC at 0-error
is exactly n for Inner Product, and n (1 - o(1)) for a random Boolean function on n+n bits.

BibTeX - Entry

@InProceedings{laurire_et_al:LIPIcs:2017:8189,
  author =	{Mathieu Lauri{\`e}re and Dave Touchette},
  title =	{{The Flow of Information in Interactive Quantum Protocols: the Cost of Forgetting}},
  booktitle =	{8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
  pages =	{47:1--47:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-029-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{67},
  editor =	{Christos H. Papadimitriou},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/8189},
  URN =		{urn:nbn:de:0030-drops-81898},
  doi =		{10.4230/LIPIcs.ITCS.2017.47},
  annote =	{Keywords: Communication Complexity, Information Complexity, Quantum Computation and Information}
}

Keywords: Communication Complexity, Information Complexity, Quantum Computation and Information
Collection: 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)
Issue Date: 2017
Date of publication: 28.11.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI