Exponential Separation of Quantum and Classical One-Way Communication Complexity

DOI10.1137/060651835zbMath1165.68028OpenAlexW2040813148MaRDI QIDQ3614162

Iordanis Kerenidis, T. S. Jayram, Ziv Bar-Yossef

Publication date: 16 March 2009

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.97.8537

zbMATH Keywords

quantum computationseparationcommunication complexityhidden matching

Mathematics Subject Classification ID

Quantum computation (81P68) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (7)

Sublinear Estimation of Weighted Matchings in Dynamic Data Streams ⋮ Near-Optimal Bounds on the Bounded-Round Quantum Communication Complexity of Disjointness ⋮ Quantum weakly nondeterministic communication complexity ⋮ A generalized Grothendieck inequality and nonlocal correlations that require high entanglement ⋮ Structural results on matching estimation with applications to streaming ⋮ Kolmogorov complexity and combinatorial methods in communication complexity ⋮ Towards quantum computing based community detection

This page was built for publication: Exponential Separation of Quantum and Classical One-Way Communication Complexity