Quantum communication complexity of symmetric predicates
By Alexander A. Razborov. 2002
211 citations recorded by the source corpus.
We completely (that is, up to a logarithmic factor) characterize the bounded-error quantum communication complexity of every predicate ) depending only on . More precisely, given a predicate on , we put Then the bounded-error quantum communication complexity of is equal to (up to a logarithmic factor). In particular, the complexity of the set disjointness predicate is equal to . This result holds both in the model with prior entanglement and in the model without it.
Subfields: Artificial Intelligence, Computational Theory and Mathematics
View Paper: https://www.semanticscholar.org/paper/b74b85f95b804c9af1e7d0d576f6d5d359922e04
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Oded Regev
- Amit Chakrabarti
- Chris Peikert
- Vadim Lyubashevsky
- Daniele Micciancio
- Damien Stehlé
- Shai Halevi
- Zvika Brakerski
In Computational Theory and Mathematics
- Oded Regev
- Amit Chakrabarti
- Chris Peikert
- Daniele Micciancio
- Vadim Lyubashevsky
- Shai Halevi
- Zvika Brakerski
- Craig Gentry
Citations in the corpus
- An optimal lower bound on the communication complexity of gap-hamming-distance (2010, methodology): “quantum communication protocol, as can be seen by combining a query complexity upper bound due to Nayak and Wu [NW99] with a communication-to-query reduction, as in Buhrman et al. [BCW98] or Razborov [Raz02]. Instead, what does work is a suitable generalization of the corruption method. Recall that ”