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. In the history of quantum algorithms, the Deutsch algorithm and the Deutsch-Jozsa algorithm play a fundamental role and both are exact one-query quantum algorithms. This leads us to consider the problem: what functions can be computed by exact one-query quantum algorithms? This problem has been addressed in the literature for total Boolean functions and symmetric partial Boolean functions, but {is} still open for general partial Boolean functions. Thus, in this paper, we continue to characterize the computational power of exact one-query quantum algorithms for general partial Boolean functions. First, we present several necessary and sufficient conditions for a partial Boolean function to be computed by exact one-query quantum algorithms. Second, inspired by these conditions we discover some new representative functions that can be computed by exact one-query quantum algorithms but have an essential difference from the already known ones. Specially, it is worth pointing out that before our work, the known functions that can be computed by exact one-query quantum algorithms are all symmetric functions and the quantum algorithm used is essentially the Deutsch-Jozsa algorithm, whereas the functions discovered in this paper are generally asymmetric and new algorithms to compute these functions are required. Thus, this expands the class of functions that can be computed by exact one-query quantum algorithms.

中文摘要：

量子计算是一种具有发展前景的新型计算模型，它在许多问题上展现出强大的计算能力。在量子计算领域，探索量子优势是一个核心的研究问题，而查询复杂性是比较量子和经典计算能力的一个有力工具。在量子算法的历史上，Deutsch算法和Deutsch-Jozsa算法是最早展示量子优势的算法，它们启发了研究人员对后续量子算法的构造和设计，在量子算法的发展历史上起了至关重要的作用。不同于其它的量子算法，Deutsch算法和 Deutsch-Jozsa算法有着如下特征：只做 1 次查询，并且确保百分之百返回正确的结果。我们把具有这种特征的量子算法称为一次查询精确量子算法。著名的 Bernstein-Vazirani 算法也是一个一次查询精确量子算法，它是 Deutsch-Jozsa 算法的一种推广。
1、目的
一个自然的问题是：什么类型的问题可以被一次查询精确量子算法解决呢？对于完全布尔函数和对称部分布尔函数来说，这个问题已经被解决了。然而，对于一般的部分布尔函数，这仍然是一个公开问题。因此，本文针对一般部分布尔函数的一次查询精确量子算法的能力进行刻画。
2、方法
首先，对于能够被一次查询量子算法精确计算的部分布尔函数，我们根据一次查询精确量子算法的特征，用一些等价的命题去描述这些部分布尔函数。然后，运用这些命题，我们去寻找一些新的部分函数实例，并对它们进行分析和讨论。
3、结果
我们对一次查询精确量子算法针对部分布尔函数的计算能力进行了刻画。首先，我们给出了一些充分必要条件去描述那些能够被一次查询量子算法精确计算的部分布尔函数。其次，受这些条件的启发，我们发现了一些新的可以被一次查询量子算法精确计算的布尔函数实例。值得注意的是，在我们的工作之前，所有已知的可以被一次查询精确量子算法计算的函数都是对称函数，并且计算这些函数的算法本质上都是 Deutsch-Jozsa 算法。而本文发现的函数在一般情况下都是非对称的，且计算它们的算法不再是 Deutsch-Jozsa 算法。
4、结论
我们对一次查询精确量子算法的计算能力进行了刻画，并且发现了一些新的可以被一次查询精确量子算法计算的非对称函数。注意到在本文之前，所有已知的能够被一次查询量子算法精确计算的布尔函数 ?? 都是对称的，并且可以被Deutsch-Jozsa 算法计算。与之相反，本文中构造的函数在通常情况下都是非对称的，并且需要新的算法去计算它们。此外，我们对这些新的函数的特征进行了讨论。在今后的研究中，我们希望找到这些函数的一些有趣的应用。本章的讨论将有助于继续讨论 ?? 次查询精确量子算法的能力。对于这个问题的探索不仅有利于加深我们对量子算法的理解，也能启发我们找到更多具有量子优势的问题。

Key words: quantum computing; quantum query complexity; quantum algorithm;