论文标题
用于学习隐藏图及以后的量子算法
Quantum algorithms for learning a hidden graph and beyond
论文作者
论文摘要
我们研究了使用量子算法通过Oracle学习的未知图的问题。我们考虑三个查询模型。在第一个模型（“或查询”）中，Oracle返回顶点的给定子集是否包含任何边缘。在第二个（“均等查询”）中，Oracle返回子集中边缘数的奇偶校验。在第三个模型中，我们将获得与图形相对应的图形状态的副本。 我们给出量子算法，可在OR和奇偶校验查询模型中，对于某些图形族中的最佳经典算法实现加速，并在图形状态模型中给出量子算法，其复杂性类似于奇偶校验查询模型。对于某些参数制度，加速器可以在奇迹查询模型中指数级。另一方面，在图表上没有任何承诺，在或查询模型中不可能加速。 我们使用的主要技术是用于解决组合组测试问题的量子算法，Belovs给出了查询有效的量子算法。在这里，我们还基于Ambainis等人的算法为该问题提供了时间效率的量子算法，以进行组测试问题的“间隔”版本。我们还提供了基于傅立叶采样和振幅扩增的简单耗时量子算法，以学习确切的一半和多数功能，这几乎与Belovs算法的最佳复杂性相匹配。
We study the problem of learning an unknown graph provided via an oracle using a quantum algorithm. We consider three query models. In the first model ("OR queries"), the oracle returns whether a given subset of the vertices contains any edges. In the second ("parity queries"), the oracle returns the parity of the number of edges in a subset. In the third model, we are given copies of the graph state corresponding to the graph. We give quantum algorithms that achieve speedups over the best possible classical algorithms in the OR and parity query models, for some families of graphs, and give quantum algorithms in the graph state model whose complexity is similar to the parity query model. For some parameter regimes, the speedups can be exponential in the parity query model. On the other hand, without any promise on the graph, no speedup is possible in the OR query model. A main technique we use is the quantum algorithm for solving the combinatorial group testing problem, for which a query-efficient quantum algorithm was given by Belovs. Here we additionally give a time-efficient quantum algorithm for this problem, based on the algorithm of Ambainis et al.\ for a "gapped" version of the group testing problem. We also give simple time-efficient quantum algorithms based on Fourier sampling and amplitude amplification for learning the exact-half and majority functions, which almost match the optimal complexity of Belovs' algorithms.
