  In this work we first examine the hardness of solving various search problems
by hybrid quantum-classical strategies, namely, by algorithms that have both
quantum and classical capabilities. We then construct a hybrid
quantum-classical search algorithm and analyze its success probability.
Regarding the former, for search problems that are allowed to have multiple
solutions and in which the input is sampled according to arbitrary
distributions we establish their hybrid quantum-classical query complexities --
i.e., given a fixed number of classical and quantum queries, determine what is
the probability of solving the search task. At a technical level, our results
generalize the framework for hybrid quantum-classical search algorithms
proposed by Rosmanis. Namely, for an arbitrary distribution $D$ on Boolean
functions, the probability an algorithm equipped with $\tau_c$ classical and
$\tau_q$ quantum queries succeeds in finding a preimage of $1$ for a function
sampled from $D$ is at most $\nu_D \cdot(2\sqrt{\tau_c} + 2\tau_q + 1)^2$,
where $\nu_D$ captures the average (over $D$) fraction of preimages of $1$. As
applications of our hardness results, we first revisit and generalize the
security of the Bitcoin protocol called the Bitcoin backbone, to a setting
where the adversary has both quantum and classical capabilities, presenting a
new hybrid honest majority condition necessary for the protocol to properly
operate. Secondly, we examine the generic security of hash functions against
hybrid adversaries. Regarding our second contribution, we design a hybrid
algorithm which first spends all of its classical queries and in the second
stage runs a ``modified Grover'' where the initial state depends on the
distribution $D$. We show how to analyze its success probability for arbitrary
target distributions and, importantly, its optimality for the uniform and the
Bernoulli distribution cases.
