Quantum Locally Testable Codes
Quantum Locally Testable Codes
复制标题
量子本地可测试代码
DOI：
10.1137/140975498
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Lior Eldar
中科院分区：
文献类型：
--
作者：
D. Aharonov;Lior Eldar
我们开始研究量子局部可测码（$\text{qLTC}$s）。经典的$\text{LTC}$在计算复杂度方面非常重要。这些代码被定义为满足一组局部约束的线性子空间，其可靠性，$R（\delta）$，这是一个随机选择的约束被违反的概率，是成比例的接近度$\delta$，其中$\delta n$是一个字从代码的距离。优秀的$\text{LTC}$存在于古典世界中，它们与著名的$\text{PCP}$（概率可检验证明）定理密切相关。在量子复杂性中，量子纠错码在多粒子纠缠的虚幻行为的研究中提供了中心的例子，并且它们在许多计算复杂性结果中发挥了至关重要的作用。我们提供了一个定义的量子类似物的$\text{LTC}$s和激励它连接其中心概念的纠缠和量子Ha.
We initiate the study of quantum locally testable codes ($\text{qLTC}$s). Classical $\text{LTC}$s are very important in computational complexity. These codes are defined as the linear subspace satisfying a set of local constraints, with the additional requirement that their soundness, $R(\delta)$, which is the probability that a randomly chosen constraint is violated, is proportional to the proximity $\delta$, where $\delta n$ is the distance of a word from the code. Excellent $\text{LTC}$s exist in the classical world, and they are tightly related to the celebrated $\text{PCP}$ (probabilistically checkable proof) theorem. In quantum complexity, quantum error correcting codes provide central examples in the study of the illusive behavior of multiparticle entanglement, and they have played a crucial role in many computational complexity results. We provide a definition of the quantum analogue of $\text{LTC}$s and motivate it by connecting its central notions in the study of both entanglement and quantum Ha...
DOI：
10.1145/2488608.2488719
发表时间：
2013-06
期刊：
--
影响因子：
--
作者：
F. Brandão;A. Harrow
通讯作者：
F. Brandão;A. Harrow