Quantum Communication Complexity and Raz's Problem
Nipun Agarwal · 2024
This study states and analyzes a family of classical algorithms that solves Raz's problem, a problem in the communication complexity framework of distributed computing. The protocols' probabilistic convergence to the answer, their communication complexities, and how each protocol behaves in special cases of input variables are discussed. The family of protocols behaves in the following way: O(log d) communication complexity when stabilizer states and Clifford gates are guaranteed, O(d log d) when only the quantum gates are Clifford, O(d 2 log d) when the input vector is a stabilizer state, and O(d 3 log d) when there are no specifications on the input vector or gates. It performs as well as the quantum algorithm in the stabilizer sub-theory, but performs poorly in the general case.