On quantum and probabilistic communication

DOI10.1145/335305.335396zbMath1296.68058OpenAlexW2083425572MaRDI QIDQ3192036

Hartmut Klauck

Publication date: 26 September 2014

Published in: Proceedings of the thirty-second annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/335305.335396

Mathematics Subject Classification ID

Network protocols (68M12) Quantum algorithms and complexity in the theory of computing (68Q12)

Related Items

Unary probabilistic and quantum automata on promise problems ⋮ Time-Space Complexity Advantages for Quantum Computing ⋮ A direct product theorem for two-party bounded-round public-coin communication complexity ⋮ Energy complexity of regular language recognition ⋮ Quantum weakly nondeterministic communication complexity ⋮ Quantum Finite Automata: A Modern Introduction ⋮ From Quantum Query Complexity to State Complexity ⋮ Exact Affine Counter Automata ⋮ Superiority of exact quantum automata for promise problems ⋮ Lifting query complexity to time-space complexity for two-way finite automata ⋮ Classical and Quantum Computations with Restricted Memory ⋮ Error-Free Affine, Unitary, and Probabilistic OBDDs ⋮ Energy complexity of regular languages ⋮ Generalizations of the distributed Deutsch–Jozsa promise problem ⋮ Quantum branching programs and space-bounded nonuniform quantum complexity ⋮ Exponential separation of quantum and classical online space complexity ⋮ Lower Bounds for Las Vegas Automata by Information Theory ⋮ Lower bounds in communication complexity based on factorization norms ⋮ Pointer chasing via triangular discrimination ⋮ The complexity of quantum disjointness ⋮ Improved constructions for succinct affine automata ⋮ Quantum communication and complexity. ⋮ On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata