|
| related topics |
| {algorithm, log, probability} |
| {key, protocol, security} |
| {information, entropy, channel} |
| {alice, bob, state} |
| {let, theorem, proof} |
| {time, decoherence, evolution} |
| {error, code, errors} |
| {measurement, state, measurements} |
| {entanglement, phys, rev} |
| {phase, path, phys} |
| {vol, operators, histories} |
|
Interaction in Quantum Communication
Hartmut Klauck, Ashwin Nayak, Amnon Ta-Shma, David Zuckerman
abstract: In some scenarios there are ways of conveying information with many fewer,
even exponentially fewer, qubits than possible classically. Moreover, some of
these methods have a very simple structure--they involve only few message
exchanges between the communicating parties. It is therefore natural to ask
whether every classical protocol may be transformed to a ``simpler'' quantum
protocol--one that has similar efficiency, but uses fewer message exchanges.
We show that for any constant k, there is a problem such that its k+1 message
classical communication complexity is exponentially smaller than its k message
quantum communication complexity. This, in particular, proves a round hierarchy
theorem for quantum communication complexity, and implies, via a simple
reduction, an Omega(N^{1/k}) lower bound for k message quantum protocols for
Set Disjointness for constant k.
Enroute, we prove information-theoretic lemmas, and define a related measure
of correlation, the informational distance, that we believe may be of
significance in other contexts as well.
- oai_identifier:
- oai:arXiv.org:quant-ph/0603135
- categories:
- quant-ph
- comments:
- 35 pages. Uses IEEEtran.cls, IEEEbib.bst. Submitted to IEEE
Transactions on Information Theory. Strengthens results in quant-ph/0005106,
quant-ph/0004100 and an earlier version presented in STOC 2001
- arxiv_id:
- quant-ph/0603135
- created:
- 2006-03-15
Full article ▸
|
|
| related documents |
| 0703231v2 |
| 9910033v4 |
| 0408119v1 |
| 0510185v1 |
| 0504083v2 |
| 0510230v3 |
| 9904079v3 |
| 0408150v2 |
| 9802040v2 |
| 0008059v3 |
| 0607148v3 |
| 0612089v3 |
| 0206023v2 |
| 0610235v2 |
| 0609220v1 |
| 0609166v1 |
| 0609160v1 |
| 0702007v2 |
| 0610105v1 |
| 0606077v1 |
| 0612052v2 |
| 0610214v3 |
| 0703099v5 |
| 0608156v1 |
| 0611145v1 |
|