交互证明在验证(量子)学习和测试中的应用
本文比较了传统和量子学习者在Probably Approximately Correct (PAC)框架下的生成模型能力,并构造了一类离散概率分布,通过决策Diffie-Hellman假设证明传统生成模型算法无法高效PAC学习,但我们构建了一个高效的量子学习器。同时,本文还讨论了证明经典生成建模难度结果的技术,以及布尔函数和离散概率分布的PAC学习性之间的关系。
Jul, 2020
通过研究量子记忆在学习量子系统和动力学属性方面的作用,我们展示了不使用量子记忆的学习算法需要更多的数据,提出了量子记忆与样本复杂度的权衡,并针对测试、判别演化以及估计纯度等方面的学习算法展示了量子记忆与非量子记忆算法之间的指数差距。
Nov, 2021
研究利用交互式证明系统框架来进行量子学习的经典验证,通过“混合超位置”量子示例提出了针对求解量子难题的新的量子数据访问模型,并证明了经典验证器只需随机例子或统计查询访问,就能有效地验证量子学习。
Jun, 2023
本文探讨如何找到一些学习问题,量子学习算法可以在其中证明比经典学习算法快速得多,还具有物理意义的应用,例如,在凝聚态物理和高能物理中表现出来的数据。
Jun, 2023
学习量子态和幺正算子的复杂度与创建这些态和算子的复杂度相关,量子状态重构和学习存在困难,但学习量子电路生成的态和幺正算子表明采样复杂度与门复杂度线性相关,查询复杂度与门数线性相关,而计算复杂度根据可信的加密猜想呈指数爆炸增长,这些结果限制了量子机器学习模型的表达能力,且对幺正算子学习中的 no-free-lunch 定理提供新的视角。
Oct, 2023
基于研究对现代量子设备的实际限制如何影响量子学习的复杂性,通过自然环境中对多个副本进行测量和采用Schur-Weyl采样的方式,揭示了量子学习中量子复制与纠缠之间的平滑交换,特别是在拓扑近似条件下的观测联通性以及从最大混合态偏离程度的估计。
Feb, 2024
我们针对不均衡分布学习问题,构建了一种双效证明系统的交互式协议,该协议能够学习给定函数的最大傅立叶特征,学习类AC^0[2]和k-juntas。此外,我们还提供了一个用于布尔函数学习的新模型,样本复杂度与n无关。
Apr, 2024
我们将各种量子学习算法按照三种设计的学习协议分类,并建立了其No-Free-Lunch定理;我们的研究结果表明量子学习协议在样本复杂度上具有二次降低,这取决于量子态的正交性和观测量的对角性,并深化了对量子学习协议能力的理解。
May, 2024
保证数据隐私在机器学习模型中至关重要,尤其是在分布式环境中,其中模型梯度通常在多个参与方之间共享,以实现协同学习。该研究揭示了基于量子机器学习模型的梯度中恢复输入数据的困难程度,并发现了动力学李代数在决定隐私漏洞方面的重要作用。研究结果显示,作为学习模型的变分量子电路的动力学李代数的某些特性可能导致隐私泄露,使得能够从输入数据的快照中训练用于不同学习任务的变分量子电路模型。此外,研究还探讨了从这些快照中恢复原始输入数据的条件,建立了与编码映射、动力学李代数基的重合度以及傅里叶频率特性等相关的条件,从而使得用于近似多项式时间恢复原始输入数据的经典或量子辅助方法成为可能。因此,该研究的发现对于指导设计平衡可训练性和强大隐私保护的量子机器学习模型的要求至关重要。
May, 2024
该论文研究了近期对未知量子电路的可学习性,证明了用于学习量子过程的量子统计查询的自然鲁棒性,并提供了一种有效的方式来评估各种统计噪声,为开发噪声容忍算法提供了强大的框架。我们对具有小的查询复杂度额外开销的常深度量子电路的学习算法进行了适应,并证明了通过统计查询在钻石距离内学习对数和更高深度的随机量子电路的平均情况下的下界。此外,我们展示了从量子统计查询中量子阈值搜索问题的困难性,并讨论了其对浅层量子电路可学习性的影响。最后,我们通过构造一个高效的区分器并证明量子无免费午餐定理的一个新变种,证明了伪随机幺正(PRU)不能使用常深度电路构造。
May, 2024