Given that reliable cloud quantum computers are becoming closer to reality, the concept of delegation of quantum computations and its verifiability is of central interest. Many models have been proposed, each with specific strengths and weaknesses. Here, we put forth a new model where the client trusts only its classical processing, makes no computational assumptions, and interacts with a quantum server in a single round. In addition, during a set-up phase, the client specifies the size $n$ of the computation and receives an untrusted, off-the-shelf (OTS) quantum device that is used to report the outcome of a single constant-sized measurement from a predetermined logarithmic-sized input. In the OTS model, we thus picture that a single quantum server does the bulk of the computations, while the OTS device is used as an untrusted and generic verification device, all in a single round. We show how to delegate polynomial-time quantum computations in the OTS model. Scaling up the technique also yields an interactive proof system for all of QMA, which, furthermore, we show can be accomplished in statistical zero-knowledge. This yields the first relativistic (one-round), two-prover zero-knowledge proof system for QMA. As a proof approach, we provide a new self-test for $n$-EPR pairs using only constant-sized Pauli measurements, and show how it provides a new avenue for the use of simulatable codes for local Hamiltonian verification. Along the way, we also provide an enhanced version of a well-known stability result due to Gowers and Hatami and show how it completes a common argument used in self-testing.


翻译:鉴于可靠的云量子计算机与现实越来越接近,量子计算的委派概念及其可验证性成为中心问题。已经提出了许多模型,每个模型都有特定的优缺点。在这里,我们提出了一个新模型,即客户端仅信任其经典处理,不做任何计算假设,并在单个回合中与量子服务器进行交互。此外,在设置阶段,客户端指定计算的大小 $n$,并接收一个不可信的、现成的 (OTS) 量子设备,该设备用于报告来自预先确定的对数级别输入的单个恒定大小的测量结果。在OTS模型中,因此我们认为一个单一的量子服务器完成大部分计算,而OTS设备作为一个不可信的、通用的验证设备,在单个回合中使用。我们展示了如何在OTS模型中委派多项式时间的量子计算。将这种技术扩大到规模,则可以获得所有 QMA 的交互式证明系​​统,而且我们还展示这可以在统计零知识下完成。这产生了第一个 QMA 的相对论性 (单回合)、两个证明人零知识证明系统。作为证明方法,我们提供了一个使用仅恒定大小的 Pauli 测量来进行 $n$ 个 EPR 对的自测试的新方法,并展示了它如何为本地哈密顿验证的模拟可证代码的使用提供新的途径。顺便提一句,我们还提供了一个著名的 Gowers 和Hatami稳定性结果的增强版本,并展示了它是自测中使用的常见论据的完整。

0
下载
关闭预览

相关内容

【干货书】计算优化:实践中的成功,415页pdf
专知会员服务
67+阅读 · 2022年12月29日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
151+阅读 · 2019年10月12日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
Flutter 组件: Autocomplete 自动填充 | 开发者说·DTalk
谷歌开发者
0+阅读 · 2022年10月28日
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
征稿 | International Joint Conference on Knowledge Graphs (IJCKG)
开放知识图谱
2+阅读 · 2022年5月20日
强化学习三篇论文 避免遗忘等
CreateAMind
19+阅读 · 2019年5月24日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Arxiv
31+阅读 · 2022年2月15日
Arxiv
54+阅读 · 2022年1月1日
VIP会员
相关VIP内容
【干货书】计算优化:实践中的成功,415页pdf
专知会员服务
67+阅读 · 2022年12月29日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
151+阅读 · 2019年10月12日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
相关资讯
Flutter 组件: Autocomplete 自动填充 | 开发者说·DTalk
谷歌开发者
0+阅读 · 2022年10月28日
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
征稿 | International Joint Conference on Knowledge Graphs (IJCKG)
开放知识图谱
2+阅读 · 2022年5月20日
强化学习三篇论文 避免遗忘等
CreateAMind
19+阅读 · 2019年5月24日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
相关基金
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Top
微信扫码咨询专知VIP会员