2013/10/08 by Adrian Kosowski, Kosowski, Adrian, Marcin Markiewicz +1
Computer Science · Mathematics · Physics and Astronomy · #Algorithm #Arithmetic #Binary number #Bounded function #Communication complexity #Computer science #Discrete mathematics #FOS: Computer and information sciences #FOS: Physical sciences #Function (biology) #Information Theory (cs.IT) #Mathematical analysis #Mathematics #Physics #Protocol (science) #Quantum #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Mechanics and Applications #Quantum Physics (quant-ph) #Quantum measurement #Quantum mechanics #State (computer science) #Statistical physics #Theoretical computer science #Variance (accounting) #cs.IT #math.IT #quant-ph
paper · pdf · doi:10.48550/arxiv.1310.2217
arxiv created 2013/10/08 · openalex publication_date 2013/10/08 · arxiv updated 2013/10/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the problem of the classical simulation of quantum measurements in the scenario of communication complexity. Regev and Toner (2007) have presented a 2-bit protocol which simulates one particular correlation function arising from binary projective quantum measurements on arbitrary state, and in particular does not preserve local averages. The question of simulating other correlation functions using a protocol with bounded communication, or preserving local averages, has been posed as an open one. Within this paper we resolve it in the negative: we show that any such protocol must have unbounded communication for some subset of executions. In particular, we show that for any protocol, there exist inputs for which the random variable describing the number of communicated bits has arbitrarily large variance.