The quantum communication complexity of the pointer chasing problem: the bit version

Abstract

We consider the two-party quantum communication complexity of the bit version of the pointer chasing problem, originally studied by Klauck, Nayak, Ta-Shma and Zuckerman [KNTZ01]. We show that in any quantum protocol for this problem, the two players must exchange Δ(n/k⁴) qubits. This improves the previous best bound of Δ( n/2^2O(k)) in [KNTZ01], and comes significantly closer to the best upper bounds known O(n+k log n) (classical deterministic [PRV01]) and O(k log n+ n/k (log^[k/2](n)+log k)) (classical randomized [KNTZ01]). Our proof uses a round elimination argument with correlated input generation, making better use of the information theoretic tools than in previous papers.