面向大数据处理的新型量子算法及相关问题的研究

The present methods for data processing and analysis face serious challenges in the age of big data. At the same time, quantum computing has the natural genes for processing problems related to big data, because of its parallelism and powerful memory. Therefore, we will study quantum algorithms for big data and related problems. Specifically, we consider the following issues. (1). We consider generalization and application of the logarithmic-time quantum algorithm (i.e,the HHL algorithm) for solving a system of linear equations. The HHL algorithm was considered to provide a new algorithm template and probably induce a series of new applications. Thus, we consider how to apply this algorithm to solve some practical problems. Also we want to generalize the algorithm to compute some general matrix functions. (2). We aim to design fast quantum algorithms for the two basic problems related to data processing and analysis: finding the maximum (or minimum) eigenvalue and corresponding eigenvector of a matrix, and matrix multiplication. 3. We try to develop some new methods for quantum machine learning: build the model of quantum decision tree, characterize the quantum hidden Markov model, and design quantum algorithms for machine learning based on quantum walk. 4. We answer the question: what problems can be solved by the quantum query algorithms using only one query without error. This project will, on one hand, provide some possible approaches to coping with the challenge of big data, and on the other hand provide more witnesses that shows quantum computing has remarkable advantages over classical computing.

大数据时代的到来对现有的数据处理方法提出了巨大挑战，而量子计算由于强大的信息存储能力和计算上的并行性，使其具有应对大数据问题的天然基因。基于此，本项目研究面向大数据处理的量子算法及相关问题，具体如下：1.考虑解线性方程组的对数时间量子算法的应用与泛化。该算法被认为提供了一种新的算法模式，可能带来一系列新的应用。我们考虑如何基于该算法设计新的量子算法解决应用问题，并把该算法泛化到计算一般矩阵函数的量子算法。2.为求矩阵的最大（最小）特征值及对应特征向量和矩阵相乘这两个与数据处理相关的基础数学问题设计快速量子算法。3.发展新的量子机器学习方法：建立量子决策树，刻画量子隐马尔科夫模型，基于量子游走设计机器学习算法。4.回答只执行一次查询操作的量子算法能无差错解决什么问题。通过本项目的研究，一方面为应对大数据问题提供可能的新方法，另一方面为彰显量子计算优势提供新的证据，进而促进量子计算自身的发展。

大数据时代的到来对现有的数据处理方法提出了巨大挑战，而量子计算由于强大的信息存储能力和计算上的并行性，使其具有应对大数据问题的天然基因。基于此，本项目研究面向大数据处理的量子算法及相关问题，具体如下：1.考虑解线性方程组量子算法(HHL)的应用。2.发展新的量子机器学习方法，基于量子游走设计机器学习算法。3.回答只执行一次查询操作的量子算法能无差错解决什么问题。通过本项目的研究，一方面为应对大数据问题提供可能的新方法，另一方面为彰显量子计算优势提供新的证据，进而促进量子计算自身的发展。.围绕以上内容，在HHL算法的应用、量子机器学习、量子查询算法等方面取得比较集中的成果，在Information and Computation，Physical Review A, New Journal of Physics, Information Sciences, Science China Information Sciences等知名国际知名学术期刊发表论文27篇，几点主要成果如下：.a) HHL算法的应用。基于HHL算法，提出了量子双支撑向量机，相比经典有指数级加速， 从而扩展了HHL算法的应用范围 。.b) 面向量子机器学习的研究。 (i) 探讨了基于量子计算的对抗生成网络的能力。具体地，提出了一种用于产生经典离散分布的量子对抗生成网络，它是经典-量子混合结构，具有以下特点和潜在优势：本质上能够生成离散数据（如文本数据），而经典对抗生成网络由于梯度消失问题而难以完成这项任务。另外，我们的方案避免了现有量子学习算法的输入/输出瓶颈。（ii）提出了一种量子特征选择算法，把训练数据的无关特征移除，以提高分类器的泛化能力和速度，分析了其与经典特征选择算法相比在计算复杂度上存在优势。.c) 量子查询算法相关研究。首先回答了什么样的函数可以被一次精确量子查询算法所计算。另外，对量子算法历史上著名的Simon问题和隐含子群问题的经典查询复杂度和样本复杂度给出了比较全面的刻画，从来为更清楚地比较量子计算与经典计算在这些问题上的计算能力提供了帮助。.以上研究成果，对于扩展量子计算应用范围，研制具有实用价值的量子计算机提供了理论支持。