Three-input Majority Function is the Unique Optimal for the Bias Amplification using Nonlocal Boxes
Three-input Majority Function is the Unique Optimal for the Bias Amplification using Nonlocal Boxes
复制标题
三输入多数函数是使用非局部框进行偏差放大的唯一最优值
DOI：
10.1103/physreva.94.052130
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
R. Mori
中科院分区：
文献类型：
--
作者：
R. Mori
Brassard等人[物理学]。Rev. Lett. 96, 250401(2006)]表明，CHSH概率大于$\frac{3+\sqrt{6}}6$的共享非局部盒子产生微不足道的通信复杂性。量子力学所能达到的最大CHSH概率$\frac{2+\sqrt{2}}4$仍然存在差距。确定微不足道的通信复杂性的确切阈值是一个有趣的开放问题。Brassard等人的想法是基于3输入多数函数的递归偏置放大。其他选择的函数是否表现出更强的偏置放大，则不明显。我们证明了3输入多数函数是唯一最优的，因此不能通过Brassard等人的偏置放大来提高阈值$\frac{3+\sqrt{6}}6$。在这项工作中，用于计算偏倚放大函数的协议被限制为非自适应协议或受Paw {\l} owski等人的信息因果关系协议启发的特定自适应协议[Nature 461, 1101(2009)]。我们首先展示了受Paw {\l} owski等人的协议启发的一种新的自适应协议，然后证明了新的自适应协议优于任何非自适应协议。最后，我们证明，如果我们将新的自适应协议应用于偏置放大的每一步，则3输入多数函数是唯一的最优偏置放大。
Brassard et al. [Phys. Rev. Lett. 96, 250401 (2006)] showed that shared nonlocal boxes with the CHSH probability greater than $\frac{3+\sqrt{6}}6$ yields trivial communication complexity. There still exists the 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 the recursive bias amplification by the 3-input majority function. It was not obvious if other choice of function exhibits stronger bias amplification. We show that the 3-input majority function is the unique optimal, 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 non-adaptive protocols or particular adaptive protocol inspired by Paw{\l}owski et al.'s protocol for information causality [Nature 461, 1101 (2009)]. We first show a new adaptive protocol inspired by Paw{\l}owski et al.'s protocol, and then show that the new adaptive protocol is better than any non-adaptive protocol. Finally, we show that the 3-input majority function is the unique optimal for the bias amplification if we apply the new adaptive protocol to each step of the bias amplification.
使用爱因斯坦方程数值计算约束的修正优化
DOI：
--
发表时间：
2022
期刊：
影响因子：
--
作者：
佐藤慧;星野秀朋;米田元
通讯作者：
米田元