Exponential Separation for One-Way Quantum Communication Complexity, with Applications to Cryptography
From MaRDI portal
bounded-storage modelcommunication complexityexponential separationextractorhidden matching problemone-way communicationquantum communicationquantum cryptographystreaming model
Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) General topics in the theory of computing (68Q01) Quantum measurement theory, state operations, state preparations (81P15) Quantum information, communication, networks (quantum-theoretic aspects) (81P45) Quantum cryptography (quantum-theoretic aspects) (81P94) Communication theory (94A05) Cryptography (94A60)
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.
Recommendations
- Exponential separations for one-way quantum communication complexity, with applications to cryptography
- Exponential Separation of Quantum and Classical One-Way Communication Complexity
- Exponential separation of quantum and classical one-way communication complexity
- A new exponential separation between quantum and classical one-way communication complexity
- Exponential separation of quantum and classical communication complexity
Cited in
(30)- Structural results on matching estimation with applications to streaming
- Concentration on the Boolean hypercube via pathwise stochastic analysis
- A quantum algorithm for approximating the influences of Boolean functions and its applications
- Experimental multipartner quantum communication complexity employing just one qubit
- The relative exponential time complexity of approximate counting satisfying assignments
- The relative exponential time complexity of approximate counting satisfying assignments
- A new exponential separation between quantum and classical one-way communication complexity
- Sublinear estimation of weighted matchings in dynamic data streams
- Exponential separations for one-way quantum communication complexity, with applications to cryptography
- Exponential separation of quantum and classical one-way communication complexity
- Exponential Separation of Quantum and Classical One-Way Communication Complexity
- Near-optimal bounds on the bounded-round quantum communication complexity of disjointness
- Exponential separation of quantum communication and classical information
- Polynomial data structure lower bounds in the group model
- scientific article; zbMATH DE number 7204275 (Why is no real title available?)
- Shadow tomography of quantum states
- Kolmogorov complexity and combinatorial methods in communication complexity
- Quantum one-way communication can be exponentially stronger than classical communication
- Optimal bounds for parity-oblivious random access codes
- scientific article; zbMATH DE number 7651028 (Why is no real title available?)
- Exponential Separation of Information and Communication for Boolean Functions
- Memory-sample lower bounds for learning with classical-quantum hybrid memory
- Streaming approximation resistance of every ordering CSP
- Exponential quantum one-wayness and EFI pairs
- A qubit, a coin, and an advice string walk into a relational problem
- Geometric influences on quantum Boolean cubes
- Sketching approximability of all finite CSPs
- Theorems of KKL, Friedgut, and Talagrand via random restrictions and log-Sobolev inequality
- Communication memento: memoryless communication complexity
- Better short-seed quantum-proof extractors
This page was built for publication: Exponential Separation for One-Way Quantum Communication Complexity, with Applications to Cryptography
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3642860)
