本文介绍了 oracle identification problem 的一些具体问题 (如 Grover search 和 Bernstein-Vazirani problem)，并给出了几个 quantum query complexity 的上下限，其中包括任何 S 的 OIP 查询复杂度为 O (sqrt (N*log M*log N)*log log M) 和 S 为任何元素个数为 N 的查询复杂度为 O (sqrt (N)) 的情况。

Mar, 2004

本文介绍了通过量子查询和量子示例从学习布尔函数的算法的复杂性的新结果，其中我们探讨了中间问题的量子和经典查询复杂度与精确学习问题和谐平衡的自然问题，并提高了期望严格学习的新下界，以达到经典 PAC 学习的已知上界。

Nov, 2004

本文研究了关于 Junta 学习问题的变体，分析了广义情况及量子查询复杂度，并展示了当预定义函数为 OR 函数或精确一半函数时最优的解决方案，对于大多数函数实现了二次优化。

Nov, 2013

采用量子对手来证明问题下界的新方法，通过设法获得足够的纠缠状态来限制计算的查询数，推出 AND 的 OR、排列倒置等计算所需的最小查询数。

Feb, 2000

该研究探讨了解决稀疏矩阵线性系统的期望值问题，通过使用量子算法实现了在 poly (log N, kappa) 时间内运行，这是目前最佳经典算法的指数级改进。

Nov, 2008

该研究文章讨论了发展基于量子算法用于学习和测试仅依赖于 k 个输入变量的布尔函数（即 juntas）的有效算法，并着重于在没有经典或量子会员资格（“黑盒”）查询的情况下实现高效算法，其中量子算法仅需少量输入样本但可能需要许多经典随机样本，并阐述了算法的上下界。

Jul, 2007

文章研究了一个量子计算版本的多臂老虎机问题，使用相干的 Oracle 访问状态，用 amplitudes 编码每个臂的奖励概率。特别地，作者提出了一种基于可变时间幅度放大和估计，用 Θ(| 根号 (n)| 乘以 | 根号 ∑_i=2^n Δ^(-2)_i|) 次量子查询可以找到最佳臂的算法。这个算法与经典算法相比，速度提升了一个平方级别。作者也证明了相匹配的量子下界（多项式对数因子）

Jul, 2020

基于两个分析下界，在已知纯态系列中鉴别状态选择成功的概率 p，并使用基于 Gram 矩阵本征值的分析下界来降低渐近区分 n 个随机量子态在 d 维度中的可分辨性，其中 n /d 趋向于一个常数。尤其对于几乎所有的 n 维度的 n 个态系列，p> 0.72。给出了对量子计算中的布尔函数（“oracle 识别问题”）的应用。

Jul, 2006

提出了一种利用量子算法实现降维和分类的方法，并对其性能进行了对比，结果表明其在训练数据向量队列和特征空间维数方面都比已知的经典算法具有指数级的加速度；同时，还给出了一种利用海森矩阵链积的量子算法，实现了线性及非线性费舍尔判别分析。

Oct, 2015

我们设计了基于量子算法的子线性算法，用于分类问题和矩阵零和游戏问题的求解，其复杂度都是量级上界的平方根，相较现有技术有瓶颈的常数。我们的算法生成与传统算法完全相同的结果，推荐用于端到端应用，同时探讨了实现方式以及机器可达到的限制。

Apr, 2019