Exponential Separation for One-Way Quantum Communication Complexity, with Applications to Cryptography

DOI10.1137/070706550MaRDI QIDQ3642860zbMATH OpenOpenAlexFDO

Authors Dmitry Gavinsky, Iordanis Kerenidis, Ran Raz, Julia Kempe, Ronald de Wolf

Publication date 6 November 2009

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/quant-ph/0611209

zbMATH Keywords

quantum communicationquantum cryptographycommunication complexityextractorexponential separationone-way communicationstreaming modelbounded-storage modelhidden matching problem

Mathematics Subject Classification ID

Communication theory (94A05) Cryptography (94A60) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Quantum measurement theory, state operations, state preparations (81P15) Quantum information, communication, networks (quantum-theoretic aspects) (81P45) Quantum cryptography (quantum-theoretic aspects) (81P94) General topics in the theory of computing (68Q01)

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)

• Kolmogorov complexity and combinatorial methods in communication complexity
• Experimental multipartner quantum communication complexity employing just one qubit
• Streaming approximation resistance of every ordering CSP
• Shadow tomography of quantum states
• Sublinear estimation of weighted matchings in dynamic data streams
• scientific article; zbMATH DE number 7651028 (Why is no real title available?)
• Exponential separation of quantum communication and classical information
• Quantum one-way communication can be exponentially stronger than classical communication
• Exponential separations for one-way quantum communication complexity, with applications to cryptography
• Polynomial data structure lower bounds in the group model
• Structural results on matching estimation with applications to streaming
• A quantum algorithm for approximating the influences of Boolean functions and its applications
• The relative exponential time complexity of approximate counting satisfying assignments
• Near-optimal bounds on the bounded-round quantum communication complexity of disjointness
• Sketching approximability of all finite CSPs
• A new exponential separation between quantum and classical one-way communication complexity
• Theorems of KKL, Friedgut, and Talagrand via random restrictions and log-Sobolev inequality
• Communication memento: memoryless communication complexity
• Better short-seed quantum-proof extractors
• The relative exponential time complexity of approximate counting satisfying assignments
• scientific article; zbMATH DE number 7204275 (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
• Exponential separation of quantum and classical one-way communication complexity
• Geometric influences on quantum Boolean cubes
• A qubit, a coin, and an advice string walk into a relational problem
• Exponential quantum one-wayness and EFI pairs
• Exponential Separation of Quantum and Classical One-Way Communication Complexity
• Optimal bounds for parity-oblivious random access codes
• Concentration on the Boolean hypercube via pathwise stochastic analysis

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)