Best Subset Selection: Statistics Meets Quantum Computing

量子计算的最新发展表明，量子计算机可以在特定问题上胜过经典计算机。然而，这些问题是高度物理导向的，对统计和数据科学界没有吸引力。自然会产生一些问题，比如量子计算机是否会使统计学界受益，量子计算机可以加速什么样的统计问题？在开发量子算法来解决统计问题方面存在重大挑战。首先，量子计算机不提供确定性结果，而是由于其内在机制而给出随机结果。其次，一般来说，现有的量子搜索算法依赖于一个函数，它可以告诉我们解决方案是否正确。例如，我们可以定义一个函数来检查数独解决方案是否正确，尽管这样的函数不能直接帮助我们解决数独问题。不幸的是，由于观测的随机性，我们无法为大多数统计问题定义这种类型的函数。第三，公众可用的量子计算机的发展仍然是原型。最先进的量子计算机的能力远远不足以进行大数据应用。该项目旨在开发一套变革性的量子算法，以弥合量子计算和统计学习之间的差距。主要研究者（PI）将调查一系列定义明确的研究问题，包括方法有效性，算法复杂性，理论严谨性和经验通用性。完成该项目可以通过强大的量子计算机激活统计学习，并为量子统计学习的新研究领域提供关键见解。PI计划开发高效的量子计算软件包来传播结果。该项目将为本科生和研究生提供参与前沿和跨学科研究的机会。最佳子集选择一直是一个统计上有吸引力，但计算上具有挑战性的问题。解决它涉及到对所有子集的组合搜索，因此是一个NP难问题。在这个项目中，PI将通过研究三个密切相关的研究目标来建立最佳子集选择问题的量子统计学习框架：（i）探索一种新的非预言量子搜索算法，该算法实现了接近最优的计算复杂度，而无需任何真实解的预言信息;（二）通过紧奇异值分解，发展了一种有效的量子线性预测算法，并利用最近发展的量子层析成像技术估计了逆奇异值技术;（iii）设计一种混合量子-经典网络结构，通过在量子节点上实施计算要求步骤和在经典节点上运行容量要求步骤来推进量子和经典计算的互补优势。该项目将有利于解决统计问题的量子算法开发的后续研究。该奖项反映了NSF的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

Recent developments in quantum computing have shown that quantum computers can outperform classic computers in specific problems. However, these problems are highly physics-oriented and are not appealing to the statistics and data science community. Natural questions arise, such as whether quantum computers will benefit the statistics community and what kind of statistical problems can be sped-up by quantum computers? There are significant challenges in developing quantum algorithms to solve statistical problems. First, a quantum computer does not provide deterministic results but gives a random result due to its intrinsic mechanism. Second, in general, existing quantum search algorithms depend on a function that can tell us if the solution is correct or not. For example, we can define a function to check if a Sudoku solution is correct or not, although such a function cannot help us directly solve the Sudoku problem. Unfortunately, we are not able to define this type of function for most statistics problems due to the randomness in observations. Third, the development of public available quantum computers is still prototypical. The capacity of the state-of-the-art quantum computer is far from enough to conduct big data applications. This project aims at developing a set of transformative quantum algorithms to bridge the gap between quantum computing and statistical learning. The principal investigator (PI) will investigate a series of well-defined research problems, including methodological validity, algorithm complexity, theoretically rigorous, and empirical versatility. Completing the project can invigorate statistical learning with powerful quantum computers and provide key insights into the new research area of quantum statistical learning. The PI plans to develop efficient quantum computing software packages to disseminate the results. The project will offer undergraduate and graduate students opportunities to participate in cutting-edge and interdisciplinary research. Best subset selection has been a statistically attractive but computationally challenging problem. Solving it involves a combinatorial search over all subsets and hence is an NP-hard problem. In this project, the PI will establish a quantum statistical learning framework for the best subset selection problems by investigating three closely related research aims: (i) explore a novel non-oracular quantum search algorithm that achieves near-optimal computational complexity without requiring any oracle information of the true solution; (ii) develop an efficient quantum linear prediction algorithm through the compact singular value decomposition and estimates the inverse singular values by utilizing a recently developed quantum tomography technique; (iii) design a hybrid quantum-classical network structure to advance complementary advantages of quantum and classical computing by implementing computational demanding steps on quantum nodes and running capacity demanding steps on classical nodes. This project will benefit the subsequent studies in quantum algorithm development for solving statistical problems.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.