dorsal/arxiv
View SchemaQuantum vs. Classical Communication and Computation
| Authors | Harry Buhrman, Richard Cleve, Avi Wigderson |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/9802040 |
| URL | https://arxiv.org/abs/quant-ph/9802040 |
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.
{
"annotation_id": "5db430f8-0b58-4f9e-a28b-bfba5bf26fb4",
"date_created": "2026-03-02T18:02:41.700000Z",
"date_modified": "2026-03-02T18:02:41.700000Z",
"file_hash": "5335b8c70466731e62500e90756020175abe815423cde17c133512704a269f1d",
"private": false,
"record": {
"abstract": "We present a simple and general simulation technique that transforms any\nblack-box quantum algorithm (a la Grover\u0027s database search algorithm) to a\nquantum communication protocol for a related problem, in a way that fully\nexploits the quantum parallelism. This allows us to obtain new positive and\nnegative results. The positive results are novel quantum communication\nprotocols that are built from nontrivial quantum algorithms via this\nsimulation. These protocols, combined with (old and new) classical lower\nbounds, are shown to provide the first asymptotic separation results between\nthe quantum and classical (probabilistic) two-party communication complexity\nmodels. In particular, we obtain a quadratic separation for the bounded-error\nmodel, and an exponential separation for the zero-error model. The negative\nresults transform known quantum communication lower bounds to computational\nlower bounds in the black-box model. In particular, we show that the quadratic\nspeed-up achieved by Grover for the OR function is impossible for the PARITY\nfunction or the MAJORITY function in the bounded-error model, nor is it\npossible for the OR function itself in the exact case. This dichotomy naturally\nsuggests a study of bounded-depth predicates (i.e. those in the polynomial\nhierarchy) between OR and MAJORITY. We present black-box algorithms that\nachieve near quadratic speed up for all such predicates.",
"arxiv_id": "quant-ph/9802040",
"authors": [
"Harry Buhrman",
"Richard Cleve",
"Avi Wigderson"
],
"categories": [
"quant-ph"
],
"title": "Quantum vs. Classical Communication and Computation",
"url": "https://arxiv.org/abs/quant-ph/9802040"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "09adba4c-864f-46c1-97e6-dc88fa70d651",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}