Lower Bounds on the Communication Complexity of Binary Local Quantum Measurement Simulation

Adrian Kosowski 1, 2 Marcin Markiewicz 3
1 CEPAGE - Algorithmics for computationally intensive applications over wide scale distributed platforms
Université Sciences et Technologies - Bordeaux 1, Inria Bordeaux - Sud-Ouest, École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), CNRS - Centre National de la Recherche Scientifique : UMR5800
Abstract : 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.
Liste complète des métadonnées

https://hal.inria.fr/hal-00871120
Contributeur : Adrian Kosowski <>
Soumis le : mardi 8 octobre 2013 - 18:35:16
Dernière modification le : vendredi 11 septembre 2015 - 01:07:15
Document(s) archivé(s) le : jeudi 9 janvier 2014 - 04:35:17

Fichiers

Simulations_lower_bound.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00871120, version 1
  • ARXIV : 1310.2217

Collections

Citation

Adrian Kosowski, Marcin Markiewicz. Lower Bounds on the Communication Complexity of Binary Local Quantum Measurement Simulation. 2013. <hal-00871120>

Partager

Métriques

Consultations de
la notice

509

Téléchargements du document

139