Best Subset Selection: Statistics Meets Quantum Computing

University Of Georgia Research Foundation Inc, Athens GA

Investigators

Abstract

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.