  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. Unlike existing
quantum search algorithms, QAS does not require the oracle information of the
true solution state and hence is applicable to various statistical learning
problems with random observations. Theoretically, we prove QAS attains any
arbitrary success probability $q \in (0.5, 1)$ within $O(\log_2D)$ iterations.
When the underlying regression model is linear, we propose a quantum linear
prediction method that is faster than its classical counterpart. We further
introduce a hybrid quantum-classical strategy to avoid the capacity bottleneck
of existing quantum computing systems and boost the success probability of QAS
by majority voting. The effectiveness of this strategy is justified by both
theoretical analysis and extensive empirical experiments on quantum and
classical computers.
