论文提出超越 Grover 与 Bernstein–Vazirani 范式的精确学习量子—经典查询复杂度分离

作者研究概念类精确学习中的确定性、随机化和量子成员查询复杂度，并构造概念类反驳长期猜想：随机查询复杂度的一个下界达到 $Ω(Q^3 log N / log Q)$，另一个确定性查询复杂度下界达到 $Ω(Q^3 log N)$。摘要称，这两个界分别与既有上界在常数因子外相匹配，表明随机化在随机查询上界中起关键作用，并首次表明量子学习加速可以超越 Grover 和 Bernstein–Vazirani 范式。