.png){kind=icon}
返回
Quantum Random Access Codes for Boolean Functions
.png){kind=icon}
OA
AI
DOI：10.22331/q-2021-03-07-402.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
An n ->(p) 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 noise stability of the Boolean function f. Moreover, we give an 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.
Keyword:
LOCALLY DECODABLE CODES
COMMUNICATION COMPLEXITY
NOISE SENSITIVITY
LOWER BOUNDS
PRIVATE
期刊
IF:
5.4
论文数:
974
被引数:
1.0W
机构
引用论文
.png){kind=icon}
分享收藏
查看更多内容