✦ LIBER ✦

Quantum communication and complexity

✍ Scribed by Ronald de Wolf

Publisher: Elsevier Science
Year: 2002
Tongue: English
Weight: 182 KB
Volume: 287
Category: Article
ISSN: 0304-3975
DOI: 10.1016/s0304-3975(02)00377-8

No coin nor oath required. For personal study only.

✦ Synopsis

In the setting of communication complexity, two distributed parties want to compute a function depending on both their inputs, using as little communication as possible. The required communication can sometimes be signiÿcantly lowered if we allow the parties the use of quantum communication. We survey the main results of the young area of quantum communication complexity: its relation to teleportation and dense coding, the main examples of fast quantum communication protocols, lower bounds, and some applications.

📜 SIMILAR VOLUMES

Communication complexity

✍ Christos H. Papadimitriou; Michael Sipser 📂 Article 📅 1984 🏛 Elsevier Science 🌐 English ⚖ 613 KB

Communication complexity hierarchy

✍ Juraj Hromkovič 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 445 KB

Matrix rank and communication complexity

✍ Bruno Codenotti; Gianna Del Corso; Giovanni Manzini 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 76 KB

The rank of a matrix seems to play a role in the context of communication complexity, a framework developed to analyze basic communication requirements of computational problems. We present some issues and open problems arising in this area, and put forward a number of research subjects in linear al

Recognition problems and communication c

Recognition problems and communication complexity

✍ Gábor Wiener 📂 Article 📅 2004 🏛 Elsevier Science 🌐 English ⚖ 248 KB

A special case of combinatorial search, the recognition problem is examined in this article. (H; A; f) is a recognition problem if H is a set, A is a set system on H and f : H → {0; 1} is a function. Someone chooses an arbitrary x ∈ H and instead of determining x itself (which is the case in most of

Communication complexity in lattices

✍ Rudolf Ahlswede; Ning Cai; Ulrich Tamm 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 467 KB

Quantum Kolmogorov Complexity

✍ André Berthiaume; Wim van Dam; Sophie Laplante 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 184 KB

In this paper we give a definition for quantum Kolmogorov complexity. In the classical setting, the Kolmogorov complexity of a string is the length of the shortest program that can produce this string as its output. It is a measure of the amount of innate randomness (or information) contained in the