Strong Direct Product Theorems for Quantum Communication and Query Complexity

DOI10.1137/110842661zbMath1263.68050arXiv1011.4935OpenAlexW2010501977MaRDI 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 communicationquery complexityquantum query complexityquantum communication complexityXOR lemmasstrong direct product theorems

Mathematics Subject Classification ID

Quantum computation (81P68) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum information, communication, networks (quantum-theoretic aspects) (81P45) Quantum algorithms and complexity in the theory of computing (68Q12)

Related Items (19)

Hardness Amplification and the Approximate Degree of Constant-Depth Circuits ⋮ Interactive Information Complexity ⋮ Approximate Degree in Classical and Quantum Computing ⋮ Breaking the Minsky--Papert Barrier for Constant-Depth Circuits ⋮ Interactive Information Complexity ⋮ A direct product theorem for two-party bounded-round public-coin communication complexity ⋮ Near-Optimal Bounds on the Bounded-Round Quantum Communication Complexity of Disjointness ⋮ A strong direct product theorem for quantum query complexity ⋮ Proofs of Work from worst-case assumptions ⋮ Approximation of \(\operatorname{sgn} (x)\) on two symmetric intervals by rational functions with fixed poles ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Improved direct product theorems for randomized query complexity ⋮ Simulation theorems via pseudo-random properties ⋮ New Strong Direct Product Results in Communication Complexity ⋮ Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$ ⋮ The Multiparty Communication Complexity of Set Disjointness ⋮ Communication Lower Bounds Using Directional Derivatives ⋮ Unnamed Item

This page was built for publication: Strong Direct Product Theorems for Quantum Communication and Query Complexity