摘要。我们考虑一种从量子成员查询中学习布尔函数的模型。该模型在 [26] 中进行了研究，其中表明，任何一类布尔函数如果可以从多项式数量的量子成员查询中从信息理论上学习，那么从多项式数量的经典成员查询中也可以从信息理论上学习。在本文中，我们建立了量子学习和经典学习之间的强计算分离。我们证明，如果存在任何加密单向函数，那么就存在一类布尔函数，它可以从量子成员查询中以多项式时间学习，但不能从经典成员查询中以多项式时间学习。我们结果的一个新结果是量子算法可以破解在经典环境中安全的一般加密构造。