Quantum communication complexity of symmetric predicates

Abstract: We completely (that is, up to a logarithmic factor) characterize the bounded-error quantum communication complexity of every predicate

f (x, y)

depending only on

| x c a p y |

(

x, y s u b s e t e q [n]

). Namely, for a predicate

D

on

0, 1, ..., n

let

e l l_{0} (D) d f m a x e l l : 1 l e q e l l l e q n / 2 l a n d D (e l l) o t e q u i v D (e l l - 1)

and

e l l_{1} (D) d f m a x n - e l l : n / 2 l e q e l l < n l a n d D (e l l) o t e q u i v D (e l l + 1)

. Then the bounded-error quantum communication complexity of

f_{D} (x, y) = D (| x c a p y |)

is equal (again, up to a logarithmic factor) to

s q r t n e l l_{0} (D) + e l l_{1} (D)

. In particular, the complexity of the set disjointness predicate is

O m e g a (s q r t n)

. This result holds both in the model with prior entanglement and without it.

Recommendations

Cited in

(41)

This page was built for publication: Quantum communication complexity of symmetric predicates