Quick Navigation

Overview Topics Abstract Importance Paper Tools References Reactions Discussion Publication Related

Topics

Quantum Machine Learning Entanglement Theory Quantum Correlations Quantum State Preparation Representation Quantum Simulation

Hybrid Decision Trees: Longer Quantum Time is Strictly More Powerful

arXiv

Authors: Xiaoming Sun, Yufan Zheng

Year

2019

Paper ID

14437

Status

Preprint

Abstract Read

~2 min

Abstract Words

236

Citations

N/A

Abstract

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'leq q. We present the following results: bullet There exists a total Boolean function f such that Q(f;1) = widetilde{mathcal{O}}\(R(f\)^4/5). bullet Q(f;q) = Ω\(bs(f\)/q + sqrt{bs(f)}) for any Boolean function f; the lower bound is tight when f is the {rm O{small R}} function. bullet Q\(g circ {rm X{small OR}}_{C log n};1\) = widetildeΩ\(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 Q\(gcirc {rm X{small OR}}_{C log n}\) = mathcal{O}\(polylog n\). Therefore an exponential separation is established. Furthermore, this open the road to prove the conjecture forall k, Q\(g circ {rm X{small OR}}_{C log^k+1 n};log^k n\) = widetildeΩ\(sqrt{n}\), which would imply the oracle separation mathsf{HP}\(mathsf{QSIZE}(n^α\))^mathfrak{O} subsetneq mathsf{BQP}^mathfrak{O} for any α, where mathsf{HP}\(mathsf{QSIZE}(n^α\)) is a complexity class that contains mathsf{BQTIME}\(n^α\)^{mathsf{BPP}} and mathsf{BPP}^{mathsf{BQTIME}\(n^α\)} in any relativized world.

Why This Paper Matters

This paper contributes to the Quantum Machine Learning research area in the Quantum Articles archive.
It adds a 2019 reference point for readers tracking recent quantum research.
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...

Paper Tools

Become a member to use research tools

Sign in to open papers, visit source links, share, cite, compare, copy DOI links, request category corrections, and build your reading list.

Become a member Sign in

Show Paper arXiv Publisher Share Cite This Paper Copy URL Compare Copy DOI Add to Reading List Category Correction Request

References & Citation Signals

[1] DOI https://doi.org/arXiv:1911.13091 [2] arXiv https://arxiv.org/abs/1911.13091 [3] Publisher https://arxiv.org/abs/1911.13091

Local Citation Graph (Related-Paper Links)

External citation index: OpenAlex citation signal

Community Reactions

Quick sentiment from readers on this paper.

Score: 0

Likes: 0 Dislikes: 0

Discussion & Reviews (Moderated)

Average Rating: 0.0 / 5 (0 ratings)

No written reviews yet.