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.CCC.2017.23
URN: urn:nbn:de:0030-drops-75437
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7543/
Go to the corresponding LIPIcs Volume Portal

Nayak, Ashwin ; Touchette, Dave

Augmented Index and Quantum Streaming Algorithms for DYCK(2)

pdf-format:
LIPIcs-CCC-2017-23.pdf (0.7 MB)

Abstract

We show how two recently developed quantum information theoretic tools can be applied to obtain lower bounds on quantum information complexity. We also develop new tools with potential for broader applicability, and use them to establish a lower bound on the quantum information complexity for the Augmented Index function on an easy distribution. This approach allows us to handle superpositions rather than distributions over inputs, the main technical challenge faced previously. By providing a quantum generalization of the argument of Jain and Nayak [IEEE TIT'14], we leverage this to obtain a lower bound on the space complexity of multi-pass, unidirectional quantum streaming algorithms for the DYCK(2) language.

BibTeX - Entry

@InProceedings{nayak_et_al:LIPIcs:2017:7543,
  author =	{Ashwin Nayak and Dave Touchette},
  title =	{{Augmented Index and  Quantum Streaming Algorithms for DYCK(2)}},
  booktitle =	{32nd Computational Complexity Conference (CCC 2017)},
  pages =	{23:1--23:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-040-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{79},
  editor =	{Ryan O'Donnell},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7543},
  URN =		{urn:nbn:de:0030-drops-75437},
  doi =		{10.4230/LIPIcs.CCC.2017.23},
  annote =	{Keywords: Quantum streaming algorithms, Space complexity, Quantum communication complexity, Quantum information cost, DYCK(2), Augmented Index}
}

Keywords: Quantum streaming algorithms, Space complexity, Quantum communication complexity, Quantum information cost, DYCK(2), Augmented Index
Collection: 32nd Computational Complexity Conference (CCC 2017)
Issue Date: 2017
Date of publication: 01.08.2017

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