Search Results

Documents authored by Laurière, Mathieu

Document
DOI: 10.4230/LIPIcs.ITCS.2017.47
The Flow of Information in Interactive Quantum Protocols: the Cost of Forgetting

Authors: Mathieu Laurière and Dave Touchette

Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)

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.
Cite as

Mathieu Laurière and Dave Touchette. The Flow of Information in Interactive Quantum Protocols: the Cost of Forgetting. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, p. 47:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{lauriere_et_al:LIPIcs.ITCS.2017.47,
  author =	{Lauri\`{e}re, Mathieu and Touchette, Dave},
  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 =	{Papadimitriou, Christos H.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.47},
  URN =		{urn:nbn:de:0030-drops-81898},
  doi =		{10.4230/LIPIcs.ITCS.2017.47},
  annote =	{Keywords: Communication Complexity, Information Complexity, Quantum Computation and Information}
}
Document
DOI: 10.4230/LIPIcs.STACS.2017.20
Extended Learning Graphs for Triangle Finding

Authors: Titouan Carette, Mathieu Laurière, and Frédéric Magniez

Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)

Abstract
We present new quantum algorithms for Triangle Finding improving its best previously known quantum query complexities for both dense and sparse instances. For dense graphs on n vertices, we get a query complexity of O(n^(5/4)) without any of the extra logarithmic factors present in the previous algorithm of Le Gall [FOCS'14]. For sparse graphs with m >= n^(5/4) edges, we get a query complexity of O(n^(11/12) m^(1/6) sqrt(log n)), which is better than the one obtained by Le Gall and Nakajima [ISAAC'15] when m >= n^(3/2). We also obtain an algorithm with query complexity O(n^(5/6) (m log n)^(1/6) + d_2 sqrt(n)) where d_2 is the variance of the degree distribution. Our algorithms are designed and analyzed in a new model of learning graphs that we call extended learning graphs. In addition, we present a framework in order to easily combine and analyze them. As a consequence we get much simpler algorithms and analyses than previous algorithms of Le Gall based on the MNRS quantum walk framework [SICOMP'11].
Cite as

Titouan Carette, Mathieu Laurière, and Frédéric Magniez. Extended Learning Graphs for Triangle Finding. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{carette_et_al:LIPIcs.STACS.2017.20,
  author =	{Carette, Titouan and Lauri\`{e}re, Mathieu and Magniez, Fr\'{e}d\'{e}ric},
  title =	{{Extended Learning Graphs for Triangle Finding}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{20:1--20:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Vollmer, Heribert and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.20},
  URN =		{urn:nbn:de:0030-drops-70132},
  doi =		{10.4230/LIPIcs.STACS.2017.20},
  annote =	{Keywords: Quantum query complexity, learning graphs, triangle finding}
}
Document
DOI: 10.4230/LIPIcs.TQC.2016.5
Robust Bell Inequalities from Communication Complexity

Authors: Sophie Laplante, Mathieu Laurière, Alexandre Nolin, Jérémie Roland, and Gabriel Senno

Published in: LIPIcs, Volume 61, 11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016)

Abstract
The question of how large Bell inequality violations can be, for quantum distributions, has been the object of much work in the past several years. We say a Bell inequality is normalized if its absolute value does not exceed 1 for any classical (i.e. local) distribution. Upper and (almost) tight lower bounds have been given in terms of number of outputs of the distribution, number of inputs, and the dimension of the shared quantum states. In this work, we revisit normalized Bell inequalities together with another family: inefficiency-resistant Bell inequalities. To be inefficiency-resistant, the Bell value must not exceed 1 for any local distribution, including those that can abort. Both these families of Bell inequalities are closely related to communication complexity lower bounds. We show how to derive large violations from any gap between classical and quantum communication complexity, provided the lower bound on classical communication is proven using these lower bounds. This leads to inefficiency-resistant violations that can be exponential in the size of the inputs. Finally, we study resistance to noise and inefficiency for these Bell inequalities.
Cite as

Sophie Laplante, Mathieu Laurière, Alexandre Nolin, Jérémie Roland, and Gabriel Senno. Robust Bell Inequalities from Communication Complexity. In 11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 61, pp. 5:1-5:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{laplante_et_al:LIPIcs.TQC.2016.5,
  author =	{Laplante, Sophie and Lauri\`{e}re, Mathieu and Nolin, Alexandre and Roland, J\'{e}r\'{e}mie and Senno, Gabriel},
  title =	{{Robust Bell Inequalities from Communication Complexity}},
  booktitle =	{11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016)},
  pages =	{5:1--5:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-019-4},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{61},
  editor =	{Broadbent, Anne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2016.5},
  URN =		{urn:nbn:de:0030-drops-66867},
  doi =		{10.4230/LIPIcs.TQC.2016.5},
  annote =	{Keywords: Communication complexity, Bell inequalities, nonlocality, detector efficiency}
}
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