量子假设检验的样本复杂度
该研究文章讨论了发展基于量子算法用于学习和测试仅依赖于k个输入变量的布尔函数(即juntas)的有效算法,并着重于在没有经典或量子会员资格(“黑盒”)查询的情况下实现高效算法,其中量子算法仅需少量输入样本但可能需要许多经典随机样本,并阐述了算法的上下界。
Jul, 2007
在本文中,我们研究了量子样本复杂性,使用了二种方法证明了量子和经典样本复杂性在PAC和agnostic模型上差不多,其中第一种方法可以得到与经典边界相同或仅相差一个对数的量子边界,而第二种方法可以不丧失对数因子的情况下完成分析。
Jul, 2016
本文主要研究关于量子态证明的基础问题,展示了使用非自适应的非相干测量量子态证明所需的拷贝数目与混合度测量所需的拷贝数目之间存在关联,实现了一个实例优化的上限。
Feb, 2021
在本文中,我们重新思考了用于表征量子设备中噪声结构的典型任务之一,即估计 n 量子比特 Pauli 噪声通道的特征值。我们改进了之前的工作,给出了更好的下界,并且证明了具有限定量子内存的算法在估计每个特征值的误差为 ε 时必须进行 Ω(2^n/ε^2) 个测量。此外,我们还研究了具有 k 个量子内存的算法以及任意自适应控制和通道串联情况下的查询个数下界。此外,我们的下界适用于假设检验问题,并且展示了当只有 2 个辅助比特量子内存时,可以使用单个测量高概率解决这个假设检验任务。这个结果揭示了通道串联和 O(1) 量子内存如何结合以实现量子过程学习的显著加速的新机制。
Sep, 2023
学习量子态和幺正算子的复杂度与创建这些态和算子的复杂度相关,量子状态重构和学习存在困难,但学习量子电路生成的态和幺正算子表明采样复杂度与门复杂度线性相关,查询复杂度与门数线性相关,而计算复杂度根据可信的加密猜想呈指数爆炸增长,这些结果限制了量子机器学习模型的表达能力,且对幺正算子学习中的 no-free-lunch 定理提供新的视角。
Oct, 2023
基于研究对现代量子设备的实际限制如何影响量子学习的复杂性,通过自然环境中对多个副本进行测量和采用Schur-Weyl采样的方式,揭示了量子学习中量子复制与纠缠之间的平滑交换,特别是在拓扑近似条件下的观测联通性以及从最大混合态偏离程度的估计。
Feb, 2024
该论文研究了近期对未知量子电路的可学习性,证明了用于学习量子过程的量子统计查询的自然鲁棒性,并提供了一种有效的方式来评估各种统计噪声,为开发噪声容忍算法提供了强大的框架。我们对具有小的查询复杂度额外开销的常深度量子电路的学习算法进行了适应,并证明了通过统计查询在钻石距离内学习对数和更高深度的随机量子电路的平均情况下的下界。此外,我们展示了从量子统计查询中量子阈值搜索问题的困难性,并讨论了其对浅层量子电路可学习性的影响。最后,我们通过构造一个高效的区分器并证明量子无免费午餐定理的一个新变种,证明了伪随机幺正(PRU)不能使用常深度电路构造。
May, 2024
本文研究了量子监督学习在从量子态进行经典推断中的应用,提出了一种基于量子样本的学习模型。通过改进认为样本复杂度的界限到 $O(V_{\mathcal{C}^*} \log |\mathcal{C}^*|)$,有效解决了以前高估样本复杂度的问题,且在有界希尔伯特-施密特范数的类别中证明了界限的紧致性,展现出新提出的量子经验风险最小化算法的有效性。
Aug, 2024