论文标题
精确的单量子量子算法（II）的表征：对于部分功能
Characterization of exact one-query quantum algorithms (ii): for partial functions
论文作者
论文摘要
查询模型（或黑框模型）吸引了古典和量子计算社区的广泛关注。通常，通过提出一种比其经典对应物具有更好查询复杂性的量子算法来揭示量子优势。例如，众所周知的量子算法在内，包括Deutsch-Jozsa算法，Simon算法和Grover算法都显示出从查询复杂性的角度来看，都显示出量子计算的很大优势。最近，我们在（Phys。A.{\ bf 101}，02232（2020）中考虑了问题：可以通过确切的单晶量子算法计算哪些功能？该问题已针对总布尔功能解决，但仍针对部分布尔功能开放。因此，在本文中，我们通过提供几种必要和充分的条件来继续表征部分布尔函数的精确单质量量子算法的计算能力。根据这些条件，我们构建了一些可以通过一克量子算法精确计算的新功能，但与已经知道的算法具有本质上的区别。请注意，在我们的工作之前，可以通过精确的单晶量子算法计算的已知函数都是对称函数，而本文中构建的功能通常是不对称的。
The query model (or black-box model) has attracted much attention from the communities of both classical and quantum computing. Usually, quantum advantages are revealed by presenting a quantum algorithm that has a better query complexity than its classical counterpart. For example, the well-known quantum algorithms including Deutsch-Jozsa algorithm, Simon algorithm and Grover algorithm all show a considerable advantage of quantum computing from the viewpoint of query complexity. Recently we have considered in (Phys. Rev. A. {\bf 101}, 02232 (2020)) the problem: what functions can be computed by an exact one-query quantum algorithm? This problem has been addressed for total Boolean functions but still open for partial Boolean functions. Thus, in this paper we continue to characterize the computational power of exact one-query quantum algorithms for partial Boolean functions by giving several necessary and sufficient conditions. By these conditions, we construct some new functions that can be computed exactly by one-query quantum algorithms but have essential difference from the already known ones. Note that before our work, the known functions that can be computed by exact one-query quantum algorithms are all symmetric functions, whereas the ones constructed in this papers are generally asymmetric.
