REVIEW 3 cited by
Exponential separations for one-way quantum communication complexity, with applications to cryptography
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
read the original abstract
We give an exponential separation between one-way quantum and classical communication protocols for a partial Boolean function (a variant of the Boolean Hidden Matching Problem of Bar-Yossef et al.) Earlier such an exponential separation was known only for a relational problem. The communication problem corresponds to a \emph{strong extractor} that fails against a small amount of \emph{quantum} information about its random source. Our proof uses the Fourier coefficients inequality of Kahn, Kalai, and Linial. We also give a number of applications of this separation. In particular, we show that there are privacy amplification schemes that are secure against classical adversaries but not against quantum adversaries; and we give the first example of a key-expansion scheme in the model of bounded-storage cryptography that is secure against classical memory-bounded adversaries but not against quantum ones.
Forward citations
Cited by 3 Pith papers
-
Quantum Communication Lower Bounds for Search Problems via Matrix Discrepancy
A matrix-discrepancy argument proves tight one-way quantum lower bounds for collision finding (Ω(N^{1/4})) and for streaming triangle finding (Ω(√Δ_V)) where Boolean-Hidden-Matching reductions fail.
-
Exponential Advantage of Multipartite Entanglement over Quantum Communication with Applications to Bounded-Storage Cryptography
GHZ entanglement gives an exponential classical-communication advantage over unassisted quantum communication for multipartite Hidden Matching, and separates entangled from unentangled quantum side-information for a t...
-
A lower bound on the classical simulation cost of star-network correlations
A star-network exclusion game is won perfectly with quantum d-level messages, but classically needs a message of at least n^{d-1} symbols, so no fixed-size classical qubit description can simulate joint measurements o...
Discussion (0). Sign in to comment.