Three-input majority function as the unique optimal function for the bias amplification using nonlocal boxes
Ryuhei Mori · Physical Review A · 2016
Brassard et al. [Phys. Rev. Lett. 96, 250401 (2006)] showed that shared nonlocal boxes with a CHSH (Clauser, Horne, Shimony, and Holt) probability greater than $\frac{3+\sqrt{6}}{6}$ yield trivial communication complexity. There still exists a gap with the maximum CHSH probability $\frac{2+\sqrt{2}}{4}$ achievable by quantum mechanics. It is an interesting open question to determine the exact threshold for the trivial communication complexity. Brassard et al.'s idea is based on recursive bias amplification by the three-input majority function. It was not obvious if another choice of function exhibits stronger bias amplification. We show that the three-input majority function is the unique optimal function, so that one cannot improve the threshold $\frac{3+\sqrt{6}}{6}$ by Brassard et al.'s bias amplification. In this work, protocols for computing the function used for the bias amplification are restricted to be nonadaptive protocols or a particular adaptive protocol inspired by Paw\l{}owski et al.'s protocol for information causality [Nature (London) 461, 1101 (2009)]. We first show an adaptive protocol inspired by Paw\l{}owski et al.'s protocol, and then show that the adaptive protocol improves upon nonadaptive protocols. Finally, we show that the three-input majority function is the unique optimal function for the bias amplification if we apply the adaptive protocol to each step of the bias amplification.