Document Open Access Logo

Augmented Index and Quantum Streaming Algorithms for DYCK(2)

Authors Ashwin Nayak, Dave Touchette

PDF
Thumbnail PDF

File

LIPIcs.CCC.2017.23.pdf
  • Filesize: 0.66 MB
  • 21 pages

Document Identifiers

Author Details

Ashwin Nayak
Dave Touchette

Cite As Get BibTex

Ashwin Nayak and Dave Touchette. Augmented Index and Quantum Streaming Algorithms for DYCK(2). In 32nd Computational Complexity Conference (CCC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 79, pp. 23:1-23:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.CCC.2017.23

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.

Subject Classification

Keywords
  • Quantum streaming algorithms
  • Space complexity
  • Quantum communication complexity
  • Quantum information cost
  • DYCK(2)
  • Augmented Index

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Andris Ambainis and Rūsiņš Freivalds. 1-way quantum finite automata: Strengths, weaknesses and generalizations. In Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, pages 332-341, 1998. URL: http://dx.doi.org/10.1109/SFCS.1998.743469.
  2. Andris Ambainis, Ashwin Nayak, Amnon Ta-Shma, and Umesh Vazirani. Dense quantum coding and quantum finite automata. Journal of the ACM, 49(4):1-16, 2002. URL: http://dx.doi.org/10.1145/581771.581773.
  3. Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, and D. Sivakumar. An information statistics approach to data stream and communication complexity. Journal of Computer and System Sciences, 68(4):702-732, 2004. Special issue on FOCS 2002. URL: http://dx.doi.org/10.1016/j.jcss.2003.11.006.
  4. Boaz Barak, Mark Braverman, Xi Chen, and Anup Rao. How to compress interactive communication. SIAM Journal on Computing, 42(3):1327-1363, 2013. URL: http://dx.doi.org/10.1137/100811969.
  5. Robin Blume-Kohout, Sarah Croke, and Daniel Gottesman. Streaming universal distortion-free entanglement concentration. IEEE Transactions on Information Theory, 60(1):334-350, 2014. URL: http://dx.doi.org/10.1109/TIT.2013.2292135.
  6. Amit Chakrabarti, Graham Cormode, Ranganath Kondapally, and Andrew McGregor. Information cost tradeoffs for Augmented Index and streaming language recognition. SIAM Journal on Computing, 42(1):61-83, 2013. URL: http://dx.doi.org/10.1137/100816481.
  7. Amit Chakrabarti and Ranganath Kondapally. Everywhere-tight information cost tradeoffs for Augmented Index. In Proceedings of the 14th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, and the 15th International Workshop on Randomization and Computation, APPROX'11/RANDOM'11, pages 448-459, 2011. URL: http://dx.doi.org/10.1007/978-3-642-22935-0_38.
  8. Noam Chomsky and M. P. Schotzenberger. The algebraic theory of context-free languages. In P. Braffort and D. Hirschberg, editors, Computer Programming and Formal Languages, pages 118-161, 1963. URL: http://dx.doi.org/10.1016/S0049-237X(08)72023-8.
  9. Omar Fawzi and Renato Renner. Quantum conditional mutual information and approximate Markov chains. Communications in Mathematical Physics, 340(2):575-611, 2015. URL: http://dx.doi.org/10.1007/s00220-015-2466-x.
  10. Christopher A. Fuchs and Jeroen van de Graaf. Cryptographic distinguishability measures for quantum-mechanical states. IEEE Transactions on Information Theory, 45(4):1216-1227, 1999. URL: http://dx.doi.org/10.1109/18.761271.
  11. Dmitry Gavinsky, Julia Kempe, Iordanis Kerenidis, Ran Raz, and Ronald de Wolf. Exponential separation for one-way quantum communication complexity, with applications to cryptography. SIAM Journal on Computing, 38(5):1695-1708, 2008. URL: http://dx.doi.org/10.1137/070706550.
  12. Rahul Jain and Ashwin Nayak. The space complexity of recognizing well-parenthesized expressions in the streaming model: the index function revisited. IEEE Transactions on Information Theory, 60(10):6646-6668, 2014. URL: http://dx.doi.org/10.1109/TIT.2014.2339859.
  13. Rahul Jain, Jaikumar Radhakrishnan, and Pranab Sen. A lower bound for the bounded round quantum communication complexity of Set Disjointness. In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, pages 220-229, 2003. URL: http://dx.doi.org/10.1109/SFCS.2003.1238196.
  14. Iordanis Kerenidis, Mathieu Laurière, François Le Gall, and Mathys Rennela. Information cost of quantum communication protocols. Quantum Information and Computation, 16(3-4):181-196, 2016. Google Scholar
  15. Hartmut Klauck, Ashwin Nayak, Amnon Ta-Shma, and David Zuckerman. Interaction in quantum communication. IEEE Transactions on Information Theory, 53(6):1970-1982, 2007. URL: http://dx.doi.org/10.1109/TIT.2007.896888.
  16. Attila Kondacs and John Watrous. On the power of quantum finite state automata. In Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science, pages 66-75, 1997. URL: http://dx.doi.org/10.1109/SFCS.1997.646094.
  17. Mathieu Laurière and Dave Touchette. Information flow in quantum communication: The cost of forgetting classical information. In Proceedings of the 8th Conference on Innovations in Theoretical Computer Science, 2017. Google Scholar
  18. François Le Gall. Exponential separation of quantum and classical online space complexity. Theory of Computing Systems, 45:188-202, 2009. URL: http://dx.doi.org/10.1007/s00224-007-9097-3.
  19. Frédéric Magniez, Claire Mathieu, and Ashwin Nayak. Recognizing well-parenthesized expressions in the streaming model. SIAM Journal on Computing, 43(6):1880-1905, 2014. URL: http://dx.doi.org/10.1137/130926122.
  20. Ashley Montanaro. The quantum complexity of approximating the frequency moments. Quantum Information and Computation, 16(13-14):1169-1190, 2016. Google Scholar
  21. Cristopher Moore and James P. Crutchfield. Quantum automata and quantum grammars. Theoretical Computer Science, 237(1-2):275-306, 2000. URL: http://dx.doi.org/10.1016/S0304-3975(98)00191-1.
  22. S. Muthukrishnan. Data Streams: Algorithms and Applications, volume 1, number 2 of Foundations and Trends in Theoretical Computer Science. Now Publishers Inc., Hanover, MA, USA, 2005. URL: http://dx.doi.org/10.1561/0400000002.
  23. Ashwin Nayak and Dave Touchette. Augmented Index and quantum streaming algorithms for DYCK(2). Technical Report arXiv:1610.04937, arXiv.org Preprint, October 17, 2016. Google Scholar
  24. Dave Touchette. Quantum information complexity and amortized communication. Technical Report arXiv:1404.3733, arXiv.org Preprint, April 14, 2014. Google Scholar
  25. Dave Touchette. Quantum information complexity. In Proceedings of the 47th Annual ACM on Symposium on Theory of Computing, pages 317-326. ACM, 2015. URL: http://dx.doi.org/10.1145/2746539.2746613.
  26. John Watrous. Theory of Quantum Information, 2015. Manuscript of a book, available at URL: https://cs.uwaterloo.ca/~watrous/.
  27. Mark M. Wilde. Quantum Information Theory. Cambridge University Press, Cambridge, UK, 2013. URL: http://dx.doi.org/10.1017/CBO9781139525343.
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