  In this paper, we introduce the hybrid query complexity, denoted as
$\mathrm{Q}(f;q)$, which is the minimal query number needed to compute $f$,
when a classical decision tree is allowed to call $q'$-query quantum
subroutines for any $q'\leq q$. We present the following results:
  $\bullet$ There exists a total Boolean function $f$ such that
$\mathrm{Q}(f;1) = \widetilde{\mathcal{O}}(\mathrm{R}(f)^{4/5})$.
  $\bullet$ $\mathrm{Q}(f;q) = \Omega(\mathrm{bs}(f)/q +
\sqrt{\mathrm{bs}(f)})$ for any Boolean function $f$; the lower bound is tight
when $f$ is the ${\rm O{\small R}}$ function.
  $\bullet$ $\mathrm{Q}(g \circ {\rm X{\small OR}}_{C \log n};1) =
\widetilde{\Omega}(\sqrt{n})$ for some sufficiently large constant $C$, where
$g := {\rm B{\small OOL}S{\small IMON}}_n$ is a variant of Simon's problem.
Note that $\mathrm{Q}(g\circ {\rm X{\small OR}}_{C \log n}) =
\mathcal{O}(\mathrm{polylog}\; n)$. Therefore an exponential separation is
established. Furthermore, this open the road to prove the conjecture $\forall
k,\,\mathrm{Q}(g \circ {\rm X{\small OR}}_{C \log^{k+1} n};\log^{k} n) =
\widetilde{\Omega}(\sqrt{n})$, which would imply the oracle separation
$\mathsf{HP}(\mathsf{QSIZE}(n^\alpha))^\mathfrak{O} \subsetneq
\mathsf{BQP}^\mathfrak{O}$ for any $\alpha$, where
$\mathsf{HP}(\mathsf{QSIZE}(n^\alpha))$ is a complexity class that contains
$\mathsf{BQTIME}(n^\alpha)^{\mathsf{BPP}}$ and
$\mathsf{BPP}^{\mathsf{BQTIME}(n^\alpha)}$ in any relativized world.

Computational Complexity;Quantum Physics