Best Subset Selection: Statistical Computing Meets Quantum Computing

Understand

With the rapid development of quantum computers, quantum algorithms have been studied extensively.

• However, quantum algorithms tackling statistical problems are still lacking.
• In this paper, we propose a novel non-oracular quantum adaptive search (QAS) method for the best subset selection problems.
• QAS performs almost identically to the naive best subset selection method but reduces its computational complexity from $O(D)$ to $O(\sqrt{D}\log_2D)$, where $D=2^p$ is the total number of subsets over $p$ covariates.