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

DOI10.1137/070706550zbMath1175.81038arXivquant-ph/0611209OpenAlexW3021537373MaRDI QIDQ3642860

Dmitry Gavinsky, Ran Raz, Iordanis Kerenidis, 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

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

Related Items (12)

Sublinear Estimation of Weighted Matchings in Dynamic Data Streams ⋮ The relative exponential time complexity of approximate counting satisfying assignments ⋮ Polynomial Data Structure Lower Bounds in the Group Model ⋮ Near-Optimal Bounds on the Bounded-Round Quantum Communication Complexity of Disjointness ⋮ The Relative Exponential Time Complexity of Approximate Counting Satisfying Assignments ⋮ Shadow Tomography of Quantum States ⋮ Structural results on matching estimation with applications to streaming ⋮ Kolmogorov complexity and combinatorial methods in communication complexity ⋮ Better short-seed quantum-proof extractors ⋮ Optimal bounds for parity-oblivious random access codes ⋮ Concentration on the Boolean hypercube via pathwise stochastic analysis ⋮ A quantum algorithm for approximating the influences of Boolean functions and its applications

This page was built for publication: Exponential Separation for One-Way Quantum Communication Complexity, with Applications to Cryptography