Strong Direct Product Theorems for Quantum Communication and Query Complexity
From MaRDI portal
Publication:4907578
DOI10.1137/110842661zbMath1263.68050arXiv1011.4935MaRDI QIDQ4907578
Publication date: 4 February 2013
Published in: SIAM Journal on Computing, Proceedings of the forty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1011.4935
quantum communication; query complexity; quantum query complexity; quantum communication complexity; XOR lemmas; strong direct product theorems
81P68: Quantum computation
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
81P45: Quantum information, communication, networks (quantum-theoretic aspects)
68Q12: Quantum algorithms and complexity in the theory of computing