Lower Bounds on the Communication Complexity of Binary Local Quantum Measurement Simulation
| hal.structure.identifier | Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE] | |
| hal.structure.identifier | Laboratoire Bordelais de Recherche en Informatique [LaBRI] | |
| dc.contributor.author | KOSOWSKI, Adrian | |
| hal.structure.identifier | Institute of Theoretical Physics and Astrophysics [Univ Gdańsk] [IFTIA] | |
| dc.contributor.author | MARKIEWICZ, Marcin | |
| dc.date.accessioned | 2024-04-15T09:42:48Z | |
| dc.date.available | 2024-04-15T09:42:48Z | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/197707 | |
| dc.description.abstractEn | 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. | |
| dc.language.iso | en | |
| dc.subject.en | Classical Simulation of Quantum Measurements | |
| dc.subject.en | Communication Complexity | |
| dc.subject.en | Quantum Nonlocality | |
| dc.title.en | Lower Bounds on the Communication Complexity of Binary Local Quantum Measurement Simulation | |
| dc.type | Document de travail - Pré-publication | |
| dc.subject.hal | Physique [physics]/Physique Quantique [quant-ph] | |
| dc.subject.hal | Informatique [cs]/Théorie de l'information [cs.IT] | |
| dc.subject.hal | Mathématiques [math]/Théorie de l'information et codage [math.IT] | |
| dc.identifier.arxiv | 1310.2217 | |
| bordeaux.hal.laboratories | Laboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800 | * |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| hal.identifier | hal-00871120 | |
| hal.version | 1 | |
| hal.audience | Non spécifiée | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-00871120v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.au=KOSOWSKI,%20Adrian&MARKIEWICZ,%20Marcin&rft.genre=preprint |
Fichier(s) constituant ce document
| Fichiers | Taille | Format | Vue |
|---|---|---|---|
|
Il n'y a pas de fichiers associés à ce document. |
|||