Exact Zero-Error Communication Complexity of an Entanglement-Assisted Quantum Learning Task

Abstract Zhao and Deng introduced an entanglement-assisted learning task exhibiting a constant-versus-linear separation against communication-bounded classical models: a quantum protocol with \(\:2n\) preshared Bell pairs achieves perfect success with zero input-dependent classical communication, while commonly used classical models must scale linearly to achieve nontrivial accuracy. The exact zero-error one-way classical communication cost was unknown. We prove an exact reduction: the minimum one-way classical communication for perfect success equals the logarithm of the ternary-cube covering number, equivalently the total domination number of the categorical power \(\:{K}_{3}^{\times\:n}\):