论文标题
布尔功能的量子随机访问代码
Quantum Random Access Codes for Boolean Functions
论文作者
论文摘要
$ n \ overset {p} {\ mapsto} m $随机访问代码（RAC）是$ n $ lits的编码为$ m $ $位，以便可以以概率至少$ p $恢复任何初始位，而在量子rac（qrac）中，$ n $ bits在$ n $中被编码为$ m $ $ $ $ qubits。自从提出的提议以来，RAC的思想以许多不同的方式被推广，例如允许使用共享的纠缠（称为纠缠辅助的随机访问代码，或简单地称为earac）或恢复多个位而不是一个位。在本文中，我们概括了RAC的想法，以在任何初始位的固定大小的子集上恢复给定布尔函数的值$ f $，我们称之为$ f $ -random访问代码。我们使用经典（$ f $ -rac）和Quantum（$ f $ -QRAC）编码的$ f $ -random访问代码进行研究并提供协议，以及许多不同的资源，例如私人或共享随机性，共享纠缠（$ f $ -earac）和Popescu-rohrlich盒子（$ f $ -prrac）。我们协议的成功概率的特征在于布尔函数$ f $的\ emph {噪声稳定性}。此外，我们在任何$ f $ -QRAC的成功概率上给出了一个\ emph {上限}，并具有共享的随机性，将其成功概率匹配到乘法常数（和扩展的$ f $ -racs），这意味着量子协议只能在其经典的对抗方面实现有限的优势。
An $n\overset{p}{\mapsto}m$ random access code (RAC) is an encoding of $n$ bits into $m$ bits such that any initial bit can be recovered with probability at least $p$, while in a quantum RAC (QRAC), the $n$ bits are encoded into $m$ qubits. Since its proposal, the idea of RACs was generalized in many different ways, e.g. allowing the use of shared entanglement (called entanglement-assisted random access code, or simply EARAC) or recovering multiple bits instead of one. In this paper we generalize the idea of RACs to recovering the value of a given Boolean function $f$ on any subset of fixed size of the initial bits, which we call $f$-random access codes. We study and give protocols for $f$-random access codes with classical ($f$-RAC) and quantum ($f$-QRAC) encoding, together with many different resources, e.g. private or shared randomness, shared entanglement ($f$-EARAC) and Popescu-Rohrlich boxes ($f$-PRRAC). The success probability of our protocols is characterized by the \emph{noise stability} of the Boolean function $f$. Moreover, we give an \emph{upper bound} on the success probability of any $f$-QRAC with shared randomness that matches its success probability up to a multiplicative constant (and $f$-RACs by extension), meaning that quantum protocols can only achieve a limited advantage over their classical counterparts.
