Title: Oracle problems as communication tasks and optimization of quantum algorithms Show Chinese title

Title: Oracle 问题作为通信任务和量子算法的优化

Abstract: Quantum query complexity mainly studies the number of queries needed to learn some property of a black box with high probability. A closely related question is how well an algorithm can succeed with this learning task using only a fixed number of queries. In this work, we propose measuring an algorithm's performance using the mutual information between the output and the actual value. A key observation is that if an algorithm is only allowed to make a single query and the goal is to optimize this mutual information, then we obtain a task which is similar to a basic task of quantum communication, where one attempts to maximize the mutual information of the sender and receiver. We make this analogy precise by formally considering the oracle as a separate subsystem, whose state records the unknown oracle identity. The oracle query prepares a state, which is then measured; and the target property of the oracle plays the role of a message that should be deduced from the measurement outcome. Thus we obtain a link between the optimal single-query algorithm and minimization of the extent of quantum correlations between the oracle and the computer subsystems. We also find a lower bound on this mutual information, which is related to quantum coherence. These results extend to multiple-query non-adaptive algorithms. As a result, we gain insight into the task of finding the optimal non-adaptive algorithm that uses at most a fixed number of queries, for any oracle problem. Show Chinese abstract

Abstract: 量子查询复杂性主要研究在高概率下学习黑箱某些属性所需的查询次数。 一个密切相关的问题是，使用固定数量的查询，算法在这一学习任务中能成功多好。 在本工作中，我们提出使用输出与实际值之间的互信息来衡量算法的性能。 一个关键观察是，如果算法只能进行一次查询，并且目标是优化这一互信息，那么我们得到的任务类似于量子通信中的一个基本任务，其中一方试图最大化发送者和接收者之间的互信息。 我们通过正式地将预言机视为一个独立的子系统，其状态记录未知的预言机身份，使这一类比更加精确。 预言机查询准备一个状态，然后对其进行测量；预言机的目标属性扮演着应从测量结果中推断出的信息的角色。 因此，我们得到了最优单次查询算法与预言机和计算机子系统之间量子关联程度最小化之间的联系。 我们还发现这一互信息的一个下界，该下界与量子相干性有关。 这些结果适用于多查询非自适应算法。 作为结果，我们获得了对寻找最多使用固定数量查询的最优非自适应算法的任务的见解，对于任何预言机问题。