Optimal and Verifiable Quantum Advantages in Communication Complexity
quant-ph, cs.CC
Submitted: 2026-10-04
Updated: 2026-10-04
Sources
- Exponential quantum communication reductions from generalizations of the Boolean Hidden Matching problem
- Bounding the number of common zeros of multivariate polynomials and their consecutive derivatives
- Demonstrating an unconditional separation between quantum and classical information resources
- Quantum One-Way Communication is Exponentially Stronger Than Classical Communication
- Contextuality bounds the efficiency of classical simulation of quantum processes
- Improved Separations between Quantum and Classical Communication Complexity of Total Functions
Related papers
- Reconquering Bell sampling on qudits: stabilizer learning and testing, quantum pseudorandomness bounds, and more
- Encrypted clones can leak: Classification of informative subsets in Quantum Encrypted Cloning
- Polynomial-time classical and quantum simulation of quantum impurity models
- A quasiparticle-protected superconducting qubit
- Theory of quantum-enhanced interferometry with general Markovian light sources
- A convergent hierarchy of spectral gap certificates for qubit Hamiltonians