|
| related topics |
| {algorithm, log, probability} |
| {alice, bob, state} |
| {qubit, qubits, gate} |
| {key, protocol, security} |
| {let, theorem, proof} |
| {vol, operators, histories} |
| {information, entropy, channel} |
| {entanglement, phys, rev} |
| {error, code, errors} |
|
Quantum vs. Classical Communication and Computation
Harry Buhrman, Richard Cleve, Avi Wigderson
abstract: We present a simple and general simulation technique that transforms any
black-box quantum algorithm (a la Grover's database search algorithm) to a
quantum communication protocol for a related problem, in a way that fully
exploits the quantum parallelism. This allows us to obtain new positive and
negative results. The positive results are novel quantum communication
protocols that are built from nontrivial quantum algorithms via this
simulation. These protocols, combined with (old and new) classical lower
bounds, are shown to provide the first asymptotic separation results between
the quantum and classical (probabilistic) two-party communication complexity
models. In particular, we obtain a quadratic separation for the bounded-error
model, and an exponential separation for the zero-error model. The negative
results transform known quantum communication lower bounds to computational
lower bounds in the black-box model. In particular, we show that the quadratic
speed-up achieved by Grover for the OR function is impossible for the PARITY
function or the MAJORITY function in the bounded-error model, nor is it
possible for the OR function itself in the exact case. This dichotomy naturally
suggests a study of bounded-depth predicates (i.e. those in the polynomial
hierarchy) between OR and MAJORITY. We present black-box algorithms that
achieve near quadratic speed up for all such predicates.
- oai_identifier:
- oai:arXiv.org:quant-ph/9802040
- categories:
- quant-ph
- comments:
- 6 pages, LaTeX w/ ACMconf style, no figures, made changes in notation
in order to be consistent with other papers. To appear in Proceedings of the
30th Annual ACM Symposium on Theory of Computing (ACM Press)
- arxiv_id:
- quant-ph/9802040
- created:
- 1998-02-14
- updated:
- 1998-03-11
Full article ▸
|
|
| related documents |
| 9907020v2 |
| 0408150v2 |
| 0410042v1 |
| 0403140v2 |
| 0304131v1 |
| 0607148v3 |
| 0510185v1 |
| 0010034v1 |
| 0504083v2 |
| 0008059v3 |
| 9903071v1 |
| 0207131v1 |
| 0612089v3 |
| 0511272v1 |
| 0210077v1 |
| 0505007v3 |
| 0201152v1 |
| 9905026v1 |
| 0504067v3 |
| 0302022v1 |
| 0206089v2 |
| 0303175v1 |
| 0010021v1 |
| 0011052v2 |
| 0703231v2 |
|