Lower Bounds and Hierarchies for Quantum Memoryless Communication Protocols and Quantum Ordered Binary Decision Diagrams with Repeated Test

DOI10.1007/978-3-319-73117-9_14zbMath1444.68074arXiv1703.05015OpenAlexW2761666750MaRDI QIDQ5127179

Kamil Khadiev, Aliya Khadieva, Andris Ambainis, Farid M. Ablayev

Publication date: 21 October 2020

Published in: SOFSEM 2018: Theory and Practice of Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1703.05015

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum algorithms and complexity in the theory of computing (68Q12) Communication complexity, information complexity (68Q11)

Related Items (9)

Two-way and one-way quantum and classical automata with advice for online minimization problems ⋮ Quantum versus classical online streaming algorithms with logarithmic size of memory ⋮ Quantum algorithm for dynamic programming approach for DAGs and applications ⋮ Deterministic construction of QFAs based on the quantum fingerprinting technique ⋮ Classical and Quantum Computations with Restricted Memory ⋮ Error-Free Affine, Unitary, and Probabilistic OBDDs ⋮ Quantum online algorithms with respect to space and advice complexity ⋮ Quantum online streaming algorithms with logarithmic memory ⋮ New size hierarchies for two way automata

This page was built for publication: Lower Bounds and Hierarchies for Quantum Memoryless Communication Protocols and Quantum Ordered Binary Decision Diagrams with Repeated Test