Hybrid Decision Trees: Longer Quantum Time is Strictly More Powerful

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^{\prime }$-query quantum subroutines for any $q^{\prime }\le q$. We present the following results: $\bullet$ There exists a total Boolean function $f$ such that $\mathrm{Q}(f;1)=\tilde{\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 $\mathrm{O}\mathrm{R}$ function. $\bullet$ $\mathrm{Q}(g\circ {\mathrm{X}\mathrm{OR}}_{C\log n};1)=\tilde{\Omega }(\sqrt{n})$ for some sufficiently large constant $C$, where $g:={\mathrm{B}\mathrm{OOL}\mathrm{S}\mathrm{IMON}}_n$ is a variant of Simon's problem. Note that $\mathrm{Q}(g\circ {\mathrm{X}\mathrm{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 {\mathrm{X}\mathrm{OR}}_{C{\log }^{k+1}n};{\log }^{k}n)=\tilde{\Omega }(\sqrt{n})$, which would imply the oracle separation $\mathsf{HP}(\mathsf{QSIZE}(n^{\alpha }){)}^{\mathfrak{O}}⊊{\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.

23 pages

References in corpus (2)

• An introduction to measurement based quantum computation
• Limits on Efficient Computation in the Physical World