Lower Bounds for Quantum Communication Complexity

DOI10.1137/S0097539702405620zbMath1142.68034arXivquant-ph/0106160WikidataQ58040226 ScholiaQ58040226MaRDI QIDQ5454242

Hartmut Klauck

Publication date: 28 March 2008

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

Full work available at URL: https://arxiv.org/abs/quant-ph/0106160

zbMATH Keywords

computational complexitylower boundsquantum computingcommunication complexity

Mathematics Subject Classification ID

Quantum computation (81P68) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (17)

Hellinger volume and number-on-the-forehead communication complexity ⋮ The landscape of communication complexity classes ⋮ Zero-information protocols and unambiguity in Arthur-Merlin communication ⋮ Hadamard tensors and lower bounds on multiparty communication complexity ⋮ Unnamed Item ⋮ Unbounded-error quantum query complexity ⋮ Unbounded-Error Classical and Quantum Communication Complexity ⋮ Conditional Disclosure of Secrets: Amplification, Closure, Amortization, Lower-bounds, and Separations ⋮ Limits on alternation trading proofs for time-space lower bounds ⋮ The hardest halfspace ⋮ On the Power of Lower Bound Methods for One-Way Quantum Communication Complexity ⋮ Unnamed Item ⋮ Rectangles Are Nonnegative Juntas ⋮ Sensitivity, affine transforms and quantum communication complexity ⋮ Unnamed Item ⋮ A Lifting Theorem with Applications to Symmetric Functions ⋮ Upper bounds on communication in terms of approximate rank

This page was built for publication: Lower Bounds for Quantum Communication Complexity