Jul, 2020

关于离散分布的量子与经典可学习性

HTML
PDF
TL;DR本文比较了传统和量子学习者在Probably Approximately Correct (PAC)框架下的生成模型能力，并构造了一类离散概率分布，通过决策Diffie-Hellman假设证明传统生成模型算法无法高效PAC学习，但我们构建了一个高效的量子学习器。同时，本文还讨论了证明经典生成建模难度结果的技术，以及布尔函数和离散概率分布的PAC学习性之间的关系。
发现论文，激发创造
  • PAC模型中学习量子通道的高效算法及近似状态辨识问题

    研究PAC学习量子过程问题，给出了样本复杂度估计，并推广了此问题到量子世界，得出了量子电路可在多项式样本下进行PAC学习且可近似区分量子状态。

    Oct, 2018

  • 本地量子电路输出分布的可学习性

    本文研究了两种不同的神经网络模型下，量子电路Born机的可学习性，发现虽然当给定访问样本时可用于统计学习，但具有超对数深度的克里福德电路的输出分布在统计查询模型下不易于学习，这限制了学习本地量子电路输出分布的可能性，并提供了从概率建模角度学习本地量子电路输出分布的严格见解。

    Oct, 2021

  • 量子生成模型中的可训练性障碍与机遇

    本文研究了量子生成模型中如何解决靠近平原以及指数损失集中的挑战，提出了解决这个问题的新方法Quantum fidelity-type loss，并且通过对高能物理数据建模表明了本研究理论结果的正确性。

    May, 2023

  • 量子学习的经典验证

    研究利用交互式证明系统框架来进行量子学习的经典验证，通过“混合超位置”量子示例提出了针对求解量子难题的新的量子数据访问模型，并证明了经典验证器只需随机例子或统计查询访问，就能有效地验证量子学习。

    Jun, 2023

  • 经典学习器与量子学习器之间的指数差距

    本文探讨如何找到一些学习问题，量子学习算法可以在其中证明比经典学习算法快速得多，还具有物理意义的应用，例如，在凝聚态物理和高能物理中表现出来的数据。

    Jun, 2023

  • POVM假设类的脂肪粉碎、联合测量和PAC可学习性

    我们通过建立匹配的PAC可学习性的必要和充分条件，并相应地给出样本复杂度界限，对量子测量类别的可学习性进行了表征，其设置下学习者只能访问已准备的量子态。

    Aug, 2023

  • 从Nisan的自然证明中分布式PAC-Learning

    自然证明能够推导有效学习算法的条件在分布式 PAC 学习模型中得以推广，证明了我们的主要结果，以及对深度-2 多数电路、多面体和自然目标分布中的 DNFs 的分布式 PAC 学习算法的应用以及通过深度-2 多数电路评估的编码输入弱 PRF 的不存在性。

    Oct, 2023

  • 去噪扩散概率模型的生成型量子机器学习

    基于经典对应物，我们提出了量子去噪扩散概率模型（QuDDPM），以实现对量子数据的高效可训练生成学习。

    Oct, 2023

  • 可训练的令牌嵌入量子生成时序数据模型

    使用可训练的量子测量算子将嵌入方法推广到Born机器，研究发现结合可训练的嵌入，Born机器可以表现出更好的性能，并从数据集中学习更深层次的相关性。

    Nov, 2023

  • 可复现学习的计算景观

    我们研究算法可复现性的计算方面，这是由Impagliazzo、Lei、Pitassi和Sorrell [2022]引入的稳定性概念。通过一系列与可学习性的统计联系的最新研究，如在线学习、私有学习和SQ学习，我们旨在更好地理解可复现性与这些学习范式之间的计算联系。我们的第一个结果表明，存在一个概念类，其PAC学习可复现且高效，但在标准的密码学假设下，不存在这个类的高效在线学习者。随后，我们设计了一个高效的可复现学习算法，用于在边际分布与均匀分布之间差异很大的情况下PAC学习奇偶函数，进展了Impagliazzo等人 [2022]提出的问题。为了获得这个结果，我们设计了一个可复现的提升框架，受Blanc、Lange、Malik和Tan [2023]的启发，以黑盒方式将均匀边际分布上的高效可复现PAC学习器转化为任意边际分布上的可复现PAC学习器，其样本和时间复杂度依赖于分布复杂度的某个度量。最后，我们证明任何纯DP学习器都可以在准确性、置信度参数的多项式时间内转化为一个可复现学习器，并且与底层假设类的表示维度成指数关系。

    May, 2024