An exponential separation between entanglement-assisted and unassisted one-way quantum communication
The paper proves an exponential separation between entanglement-assisted and unassisted one-way quantum communication for computing total Boolean functions. It shows that while shared entanglement significantly reduces classical communication costs to O(log n) bits, unassisted quantum protocols require a higher complexity of Omega(n^(1/3)) qubits. This resolves a key question about whether entanglement is strictly necessary for certain computational goals in one-way settings.