若干新的量子算法及相关问题

Solving some problems in computer science requires quite high time complexity and space complexity with traditional computing methods. Recently some quantum algorithms that are speedup over the classical counterparts have been discovered for solving some fundamental problems in scientific computing (such as solving a linear system of equations). Semi-algebraic set problems are other basic and important problems in scientific computing, and solving linear or nonlinear systems of equations can be considered as a special case of semi-algebraic sets problems. However, the known classical algorithms have quite high complexity for solving semi-algebraic sets problems. Thus, the purpose of this project is to search for some quantum algorithms solving semi-algebraic sets problems, including a quantum algorithm for deciding if or not a semi-algebraic set is empty; a quantum algorithm for finding a sample of a given semi-algebraic set if it is non-empty. Moreover, we consider quantum algorithm for efficiently diagonalizing Hermitian positive-semidefinite matrices. On the other hand, due to the shortage of precise quantum algorithms with super-linear advantage for computing Boolean functions (precise means no error for output outcomes), we try to discover new precise quantum algorithms for computing some Boolean functions. These algorithms may provide some insights to solve other similar problems in quantum computing.

计算中一些基本而重要的问题用传统的算法求解时要求较高的时间和空间复杂度。目前已经有学者发现了比经典计算有指数级加速的量子算法来解决科学计算的一些基本问题（如求解线性方程组）。半代数集问题是科学计算中基本而重要的问题之一；解线性和非线性方程组是半代数集的一类特殊情形。但是目前所知道的经典算法对求解半代数集问题的时间和空间复杂度比较高。因此，本项目试图设计量子算法来求解半代数集问题，包括设计量子算法判断一个半代数集是否为空；若一个半代数集非空，设计量子算法从中找到一个元素。进一步，我们也在量子计算的意义下考虑厄米特半正定矩阵的对角化问题。另一方面，由于目前所知道的计算布尔函数的超线性优势的精确量子算法比较少，所以本项目寻找新的计算一些布尔函数的超线性优势的精确量子算法 (精确是指输出结果没有误差)。设计这些算法需要新的思路，所以这些算法对解决计算中的相关问题可能具有较好的借鉴作用。

计算中一些基本而重要的问题用传统的算法求解时要求较高的时间和空间复杂度。目前已经有学者发现了比经典计算有指数级加速的量子算法来解决科学计算的一些基本问题。发现比经典算法更快的量子算法解决问题是的量子计算的核心。例如半代数集问题是科学计算中基本问题之一；解线性和非线性方程组是半代数集的一类特殊情形。但是目前所知道的经典算法对求解半代数集问题的时间和空间复杂度比较高。因此，本项目试图设计量子算法来求解一些基本问题（包括半代数集问题），设计量子算法判断一个半代数集是否为空；若一个半代数集非空，设计量子算法从中找到一个元素。进一步，我们也在量子计算的意义下考虑厄米特半正定矩阵的对角化问题。同时，由于目前所知道的计算布尔函数的超线性优势的精确量子算法比较少，所以本项目寻找新的计算一些布尔函数的超线性优势的精确量子算法(精确是指输出结果没有误差)。设计这些算法需要新的思路，所以这些算法对解决计算中的相关问题可能具有较好的借鉴作用。