Unbounded-Error Classical and Quantum Communication Complexity
From MaRDI portal
Abstract: Since the seminal work of Paturi and Simon cite[FOCS'84 & JCSS'86]{PS86}, the unbounded-error classical communication complexity of a Boolean function has been studied based on the arrangement of points and hyperplanes. Recently, cite[ICALP'07]{INRY07} found that the unbounded-error {em quantum} communication complexity in the {em one-way communication} model can also be investigated using the arrangement, and showed that it is exactly (without a difference of even one qubit) half of the classical one-way communication complexity. In this paper, we extend the arrangement argument to the {em two-way} and {em simultaneous message passing} (SMP) models. As a result, we show similarly tight bounds of the unbounded-error two-way/one-way/SMP quantum/classical communication complexities for {em any} partial/total Boolean function, implying that all of them are equivalent up to a multiplicative constant of four. Moreover, the arrangement argument is also used to show that the gap between {em weakly} unbounded-error quantum and classical communication complexities is at most a factor of three.
Recommendations
Cites work
- A Class of Linear Positive Maps in Matrix Algebras
- A linear lower bound on the unbounded error probabilistic communication complexity.
- Algorithms and Computation
- Bounded-error quantum state identification and exponential separations in communication complexity
- Communication Complexity
- Dense quantum coding and quantum finite automata
- Exponential separation of quantum and classical communication complexity
- Exponential separations for one-way quantum communication complexity, with applications to cryptography
- Geometry of Bloch vectors in two-qubit system
- scientific article; zbMATH DE number 1579275 (Why is no real title available?)
- scientific article; zbMATH DE number 1256775 (Why is no real title available?)
- scientific article; zbMATH DE number 2081103 (Why is no real title available?)
- scientific article; zbMATH DE number 1769898 (Why is no real title available?)
- Learning complexity vs communication complexity
- Lower Bounds for Quantum Communication Complexity
- Lower bounds in communication complexity based on factorization norms
- Nondeterministic Quantum Query and Communication Complexities
- On the power of quantum fingerprinting
- On the smallest possible dimension and the largest possible margin of linear arrangements representing given concept classes
- Probabilistic communication complexity
- The Bloch-Vector Space for N-Level Systems: the Spherical-Coordinate Point of View
- Unbounded-Error One-Way Classical and Quantum Communication Complexity
Cited in
(9)- scientific article; zbMATH DE number 5953454 (Why is no real title available?)
- Unbounded-Error Quantum Query Complexity
- On multiparty communication with large versus unbounded error
- Union bound for quantum information processing
- Unbounded-Error One-Way Classical and Quantum Communication Complexity
- Unbounded-error quantum computation with small space bounds
- Unbounded-error quantum query complexity
- On the fine-grained query complexity of symmetric functions
- On the fine-grained query complexity of symmetric functions
This page was built for publication: Unbounded-Error Classical and Quantum Communication Complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5387749)
