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

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

Abstract: Quantum query complexity studies the number of queries needed to learn some property of a black box. 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. The task of optimizing this mutual information using a single query, 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 splitting the algorithm between two agents, obtaining a communication protocol. The oracle's target property plays the role of a message that Alice encodes into a quantum state, which is subsequently sent over to Bob. The first part of the algorithm performs this encoding, and the second part measures the state and aims to deduce the message from the outcome. Moreover, we formally consider the oracle as a separate subsystem, whose state records the unknown oracle identity. Within this construction, Bob's optimal measurement basis minimizes the quantum correlations between the two subsystems. We also find a lower bound on the mutual information, which is related to quantum coherence. These results extend to multiple-query algorithms. As a result, we describe the optimal non-adaptive algorithm that uses at most a fixed number of queries, for any oracle classification problem. We demonstrate our results by studying several well-known algorithms through the proposed framework. Finally, we discuss some practical implications of our results. Show Chinese abstract

Abstract: 量子查询复杂性研究学习黑箱某些属性所需的查询数量。 一个密切相关的问题是，使用固定数量的查询，算法在该学习任务中能成功多好。 在本工作中，我们提出使用输出与实际值之间的互信息来衡量算法的性能。 使用单个查询优化此互信息的任务类似于量子通信中的基本任务，其中一方试图最大化发送方和接收方之间的互信息。 我们通过将算法分为两个代理来精确阐述这种类比，从而获得一个通信协议。 Oracle的目标属性扮演Alice将其编码到量子态中的消息角色，并随后发送给Bob。 算法的第一部分执行此编码，第二部分测量状态并旨在从结果中推断消息。 此外，我们正式考虑Oracle作为一个独立的子系统，其状态记录未知的Oracle身份。 在此构造中，Bob的最优测量基最小化两个子系统之间的量子关联。 我们还找到了一个与量子相干性相关的互信息下限。 这些结果适用于多查询算法。 因此，我们描述了对于任何Oracle分类问题，最多使用固定数量查询的最优非自适应算法。 我们通过所提出的框架研究了几种著名的算法来展示我们的结果。 最后，我们讨论了我们结果的一些实际意义。