Near-Optimal Bounds on the Bounded-Round Quantum Communication Complexity of Disjointness

DOI10.1137/16M1061400zbMath1408.68062arXiv1505.03110OpenAlexW2905051967WikidataQ128722761 ScholiaQ128722761MaRDI QIDQ4562275

Ankit Garg, Jieming Mao, Young Kun-Ko, Mark Braverman, Dave Touchette

Publication date: 19 December 2018

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1505.03110

zbMATH Keywords

disjointnessquantum communication complexityquantum information complexity

Mathematics Subject Classification ID

Quantum computation (81P68) Quantum algorithms and complexity in the theory of computing (68Q12)

Related Items (7)

Interactive Information Complexity ⋮ Interactive Information Complexity ⋮ Bounds on oblivious multiparty quantum communication complexity ⋮ Unnamed Item ⋮ The work of Mark Braverman ⋮ Communication and information complexity ⋮ The complexity of quantum disjointness

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Common information and unique disjointness
• Quantum conditional mutual information and approximate Markov chains
• An information statistics approach to data stream and communication complexity
• On the distributional complexity of disjointness
• Exponential separation of quantum and classical communication complexity
• How to compress interactive communication
• Quantum Information Complexity
• Lower Bounds on the Size of Semidefinite Programming Relaxations
• Certifying Equality With Limited Interaction.
• The Fidelity of Recovery Is Multiplicative
• Lower Bounds on Information Complexity via Zero-Communication Protocols and Applications
• Exponential Separation of Quantum and Classical One-Way Communication Complexity
• Exponential Separation for One-Way Quantum Communication Complexity, with Applications to Cryptography
• The Probabilistic Communication Complexity of Set Intersection
• Rounds in Communication Complexity Revisited
• Communication via one- and two-particle operators on Einstein-Podolsky-Rosen states
• Communication Complexity
• Strong Direct Product Theorems for Quantum Communication and Query Complexity
• Information Lower Bounds via Self-reducibility
• Interaction in quantum communication and the complexity of set disjointness
• Direct Product via Round-Preserving Compression
• Efficient Protocols for Generating Bipartite Classical Distributions and Quantum States
• Entangled simultaneity versus classical interactivity in communication complexity
• Exponential separation of communication and external information
• Interactive information complexity
• Quantum one-way communication can be exponentially stronger than classical communication
• Quantum and Classical Strong Direct Product Theorems and Optimal Time‐Space Tradeoffs
• From information to exact communication
• An information complexity approach to extended formulations
• Communication Lower Bounds Using Directional Derivatives
• Some Minimax Theorems.
• Quantum Information Theory
• Concentration of Measure for the Analysis of Randomized Algorithms
• The communication complexity of pointer chasing

This page was built for publication: Near-Optimal Bounds on the Bounded-Round Quantum Communication Complexity of Disjointness