In the oracle identification problem, we are given oracle access to an
unknown N-bit string x promised to belong to a known set C of size M and our
task is to identify x. We present a quantum algorithm for the problem that is
optimal in its dependence on N and M. Our algorithm considerably simplifies and
improves the previous best algorithm due to Ambainis et al. Our algorithm also
has applications in quantum learning theory, where it improves the complexity
of exact learning with membership queries, resolving a conjecture of Hunziker
et al.
The algorithm is based on ideas from classical learning theory and a new
composition theorem for solutions of the filtered $\gamma_2$-norm semidefinite
program, which characterizes quantum query complexity. Our composition theorem
is quite general and allows us to compose quantum algorithms with
input-dependent query complexities without incurring a logarithmic overhead for
error reduction. As an application of the composition theorem, we remove all
log factors from the best known quantum algorithm for Boolean matrix
multiplication.

本文介绍了一种新的量子算法，以解决预定大小的已知集合中的未知 N 位字符串的甄别问题，还在量子学习理论中应用该算法并改进了其复杂度，并且提出一种新的组合定理，使我们能够编写没有错误降低的具有依赖性查询复杂度的量子算法，最后用此方法消除了布尔矩阵乘法的最优量子算法中所有的对数因子。