Unbounded-Error Classical and Quantum Communication Complexity
From MaRDI portal
Publication:5387749
DOI10.1007/978-3-540-77120-3_11zbMath1193.68134arXiv0709.2761OpenAlexW3105099251MaRDI QIDQ5387749
Harumichi Nishimura, Shigeru Yamashita, Rudy Raymond, Kazuo Iwama
Publication date: 27 May 2008
Published in: Algorithms and Computation (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0709.2761
Analysis of algorithms and problem complexity (68Q25) Network design and communication in computer systems (68M10) Quantum computation (81P68) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Probabilistic communication complexity
- On the smallest possible dimension and the largest possible margin of linear arrangements representing given concept classes
- A linear lower bound on the unbounded error probabilistic communication complexity.
- Exponential separation of quantum and classical communication complexity
- Bounded-error quantum state identification and exponential separations in communication complexity
- The Bloch-Vector Space for N-Level Systems: the Spherical-Coordinate Point of View
- Dense quantum coding and quantum finite automata
- Learning Complexity vs Communication Complexity
- On the power of quantum fingerprinting
- A Class of Linear Positive Maps in Matrix Algebras
- Nondeterministic Quantum Query and Communication Complexities
- Communication Complexity
- Algorithms and Computation
- Unbounded-Error One-Way Classical and Quantum Communication Complexity
- Lower Bounds for Quantum Communication Complexity
- Lower bounds in communication complexity based on factorization norms
- Geometry of Bloch vectors in two-qubit system
