Hybrid Decision Trees: Longer Quantum Time is Strictly More Powerful. (arXiv:1911.13091v1 [cs.CC])
(Submitted on 29 Nov 2019)
Abstract: 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}(gcirc {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.
