机构名称：
¥ 1.0
特征选择需要从给定数据集中创建特征子集，以在原始数据集和选定特征集之间建立高度互信息 (MI) 共享 [ 1 , 2 ]。形式上，给定一组特征 F = { f 1 , f 2 , · · · , fm }，其中 fi ∈ R d ，设 fi K 为 fi 在 K 中的维度所跨越的子空间上的投影，设 FK = { fi K } 为一组独立的 fi 。特征选择问题定义为从 F 中选择 K ⊂{ 1 , · · · , p }，使得 K 保留最多信息。虽然特征选择是经典计算中一个研究得很深入的课题 [ 3 – 6 ]，但在量子算法开发的背景下，特征选择仍然是一个相对较新的领域。这项任务被认为是 NP 难题 [ 7 ]，在没有关于数据集结构的先验信息的情况下，量子算法的加速上限是二次的。此前，针对特征选择问题，人们提出了容错和效用规模量子算法 [8]，但成功率参差不齐 [9-15]。其中，容错量子特征选择算法分别表现出多对数时间复杂度和二次加速比。多对数时间复杂度是由于问题中隐藏着某种代数结构，而二次加速比是当手头的 NP 完全问题的结构未知时量子算法的一般 Grover 加速比 [16]。其他量子方法是实现变分方法的效用规模量子算法。尽管分析此类算法很困难，但可以合理地假设，除非进一步利用问题结构，否则此类算法的量子加速比的上限就是 Grover 加速比。表示特征选择问题的一种常用方法是二次无约束优化问题 (QUBO)，可以使用经典和量子计算框架进行处理。在量子计算机上，我们既可以使用 Grover 型容错算法，也可以使用 VQE [ 17 ] 或 QAOA 型 [ 18 ] 效用规模算法来求解该问题。另一方面，当量子算法能够利用已知结构时，加速比可以更显著，比如当简化为尖峰张量分解时，加速比可以达到四次方 [ 19 ]，而当与计算 Betti 数相关时，加速比甚至可以达到指数级 [ 20 , 21 ]。这促使人们探究是否存在一类具有最小结构的问题，即用户对特征拥有稍多的信息，而量子算法可能会带来一些加速。这项工作旨在解决黑盒特征选择问题 (B2FS) 的这个问题，在某些假设下，将其表述为碰撞问题 [ 22 ]。利用 Brassard-Høyer-Tapp 算法（BHT 算法）[ 23 ]，一种已知的碰撞问题解决方案，我们提供了对已经高效的经典概率算法进行多项式加速的证明。据我们所知，这是已知的第一个针对最小结构化特征选择问题的量子加速。
黑盒特征选择的多项式量子加速
主要关键词
相关文件推荐
