Classical and quantum partition bound and detector inefficiency
| Autor: | Jérémie Roland, Virginie Lerays, Sophie Laplante |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2012 |
| Předmět: |
Discrete mathematics
FOS: Computer and information sciences Quantum Physics FOS: Physical sciences 0102 computer and information sciences Quantum entanglement Computational Complexity (cs.CC) 01 natural sciences Upper and lower bounds Théorie des algorithmes Computer Science - Computational Complexity 010201 computation theory & mathematics Quantum state Bell's theorem 0103 physical sciences Informatique mathématique 010306 general physics Communication complexity Quantum information science Quantum Physics (quant-ph) Quantum Randomness |
| Zdroj: | 39th International Colloquium on Automata, Languages and Programming (ICALP'12). Springer Automata, Languages, and Programming ISBN: 9783642315930 |
| Popis: | In communication complexity, two players each have an input and they wish to compute some function of the joint inputs. This has been the object of much study and a wide variety of lower bound methods have been introduced to address the problem of showing lower bounds on communication. Recently, Jain and Klauck introduced the partition bound, which subsumes many of the known methods, in particular factorization norm, discrepancy, and the rectangle (corruption) bound. Physicists have considered a closely related scenario where two players share a predefined entangled state. Each is given a measurement as input, which they perform on their share of the system. The outcomes of the measurements follow a distribution which is predicted by quantum mechanics. In an experimental setting, Bell inequalities are used to distinguish truly quantum from classical behavior. We present a new lower bound technique based on the notion of detector inefficiency (where some runs are discarded by either of the players) for the extended setting of simulating distributions, and show that it coincides with the partition bound in the case of computing functions. The dual form is more feasible to use, and we show that it amounts to constructing an explicit Bell inequality. We also give a lower bound on quantum communication complexity which can be viewed as a quantum extension of the rectangle bound, effectively overcoming the necessity of a quantum minmax theorem. For one-way communication, we show that the quantum one-way partition bound is tight for classical communication with shared entanglement up to arbitrarily small error. Finally, an important goal in physics is to devise robust Bell experiments that are impervious to noise and detector inefficiency. We make further progress towards this by giving a general tradeoff between communication, Bell inequality violation, and detector efficiency. info:eu-repo/semantics/published |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|