The one-way communication complexity of the Boolean Hidden Matching Problem

Simple item page
dc.creatorKerenidis, Iordanis
dc.creatorRaz, Ran
dc.date2006-07-25
dc.date.accessioned2026-07-07T07:22:57Z
dc.date.available2026-07-07T07:22:57Z
dc.descriptionWe give a tight lower bound of Omega(\sqrt{n}) for the randomized one-way communication complexity of the Boolean Hidden Matching Problem [BJK04]. Since there is a quantum one-way communication complexity protocol of O(\log n) qubits for this problem, we obtain an exponential separation of quantum and classical one-way communication complexity for partial functions. A similar result was independently obtained by Gavinsky, Kempe, de Wolf [GKdW06]. Our lower bound is obtained by Fourier analysis, using the Fourier coefficients inequality of Kahn Kalai and Linial [KKL88].
dc.identifierhttps://arxiv.org/abs/quant-ph/0607173
dc.identifierhttp://arxiv.org/abs/quant-ph/0607173
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/115849
dc.subjectQuantum Physics
dc.subjectComputational Complexity
dc.titleThe one-way communication complexity of the Boolean Hidden Matching Problem
dc.typetext

Files

Collections

arXiv