Strong Direct Product Theorems for Quantum Communication and Query Complexity

DOI10.1137/110842661zbMath1263.68050arXiv1011.4935MaRDI QIDQ4907578

Alexander A. Sherstov

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

zbMATH Keywords

quantum communication; query complexity; quantum query complexity; quantum communication complexity; XOR lemmas; strong direct product theorems

Mathematics Subject Classification ID

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