Hybrid Decision Trees: Longer Quantum Time is Strictly More Powerful
share
In this paper, we introduce the hybrid query complexity, denoted as 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'≤ q. We present the following results: ∙ There exists a total Boolean function f such that Q(f;1) = O(R(f)^4/5). ∙Q(f;q) = Ω(bs(f)/q + √(bs(f))) for any Boolean function f; the lower bound is tight when f is the O R function. ∙Q(g ∘ X OR_C log n;1) = Ω(√(n)) for some sufficiently large constant C, where g := B OOLS IMON_n is a variant of Simon's problem. Note that Q(g∘ X OR_C log n) = O(polylog n). Therefore an exponential separation is established. Furthermore, this open the road to prove the conjecture ∀ k, Q(g ∘ X OR_C log^k+1 n;log^k n) = Ω(√(n)), which would imply the oracle separation HP(QSIZE(n^α))^O⊊BQP^O for any α, where HP(QSIZE(n^α)) is a complexity class that contains BQTIME(n^α)^BPP and BPP^BQTIME(n^α) in any relativized world.
READ FULL TEXT