A locally testable code is an error-correcting code that admits very efficient probabilistic tests of membership. Tensor codes provide a simple family of combinatorial constructions of locally testable codes that generalize the family of Reed-Muller codes. The natural test for tensor codes, the axis-parallel line vs. point test, plays an essential role in constructions of probabilistically checkable proofs. We analyze the axis-parallel line vs. point test as a two-prover game and show that the test is sound against quantum provers sharing entanglement. Our result implies the quantum-soundness of the low individual degree test, which is an essential component of the MIP* = RE theorem. Our proof also generalizes to the infinite-dimensional commuting-operator model of quantum provers.


翻译:本地测试代码是一种允许非常高效的会籍概率测试的错误校正代码。 Tensor 代码提供了一套简单的组合式组合式组合式的本地测试代码结构,将Reed- Muller 代码组合为通用的本地测试代码。 高频代码的自然测试, 轴- 平行线对点测试, 在概率校验证据的构造中起着关键作用 。 我们将轴- 平行线对点测试分析成一种双倍的游戏, 并显示测试对量子验证器的串联性是健全的。 我们的结果意味着低单度测试的量度判断性, 这是 MIP * = RE 参数的基本组成部分 。 我们的证据还概括了量子验证器的无限分流模型 。

0
下载
关闭预览

相关内容

物联网金融研究报告(2022年),50页pdf
专知会员服务
62+阅读 · 2022年1月15日
专知会员服务
52+阅读 · 2020年9月7日
Python分布式计算,171页pdf,Distributed Computing with Python
专知会员服务
107+阅读 · 2020年5月3日
经济学中的数据科学,Data Science in Economics,附22页pdf
专知会员服务
35+阅读 · 2020年4月1日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
已删除
将门创投
6+阅读 · 2019年7月11日
用霍夫变换&SCNN码一个车道追踪器
全球人工智能
4+阅读 · 2019年2月10日
【TED】生命中的每一年的智慧
英语演讲视频每日一推
9+阅读 · 2019年1月29日
【TED】什么让我们生病
英语演讲视频每日一推
7+阅读 · 2019年1月23日
carla无人驾驶模拟中文项目 carla_simulator_Chinese
CreateAMind
3+阅读 · 2018年1月30日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
Adversarial Variational Bayes: Unifying VAE and GAN 代码
CreateAMind
7+阅读 · 2017年10月4日
Highway Networks For Sentence Classification
哈工大SCIR
4+阅读 · 2017年9月30日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Arxiv
0+阅读 · 2022年1月20日
Arxiv
0+阅读 · 2022年1月20日
Arxiv
0+阅读 · 2022年1月19日
Quantum Ensemble for Classification
Arxiv
0+阅读 · 2022年1月18日
Arxiv
0+阅读 · 2022年1月17日
Arxiv
3+阅读 · 2018年10月18日
VIP会员
相关主题
相关VIP内容
物联网金融研究报告(2022年),50页pdf
专知会员服务
62+阅读 · 2022年1月15日
专知会员服务
52+阅读 · 2020年9月7日
Python分布式计算,171页pdf,Distributed Computing with Python
专知会员服务
107+阅读 · 2020年5月3日
经济学中的数据科学,Data Science in Economics,附22页pdf
专知会员服务
35+阅读 · 2020年4月1日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
相关资讯
已删除
将门创投
6+阅读 · 2019年7月11日
用霍夫变换&SCNN码一个车道追踪器
全球人工智能
4+阅读 · 2019年2月10日
【TED】生命中的每一年的智慧
英语演讲视频每日一推
9+阅读 · 2019年1月29日
【TED】什么让我们生病
英语演讲视频每日一推
7+阅读 · 2019年1月23日
carla无人驾驶模拟中文项目 carla_simulator_Chinese
CreateAMind
3+阅读 · 2018年1月30日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
Adversarial Variational Bayes: Unifying VAE and GAN 代码
CreateAMind
7+阅读 · 2017年10月4日
Highway Networks For Sentence Classification
哈工大SCIR
4+阅读 · 2017年9月30日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
相关论文
Arxiv
0+阅读 · 2022年1月20日
Arxiv
0+阅读 · 2022年1月20日
Arxiv
0+阅读 · 2022年1月19日
Quantum Ensemble for Classification
Arxiv
0+阅读 · 2022年1月18日
Arxiv
0+阅读 · 2022年1月17日
Arxiv
3+阅读 · 2018年10月18日
Top
微信扫码咨询专知VIP会员