论文标题
根据经典决策树改进的量子查询上限
Improved Quantum Query Upper Bounds Based on Classical Decision Trees
论文作者
论文摘要
给定经典查询算法作为决策树，什么时候存在量子查询算法并加快经典算法？我们根据基础决策树的结构提供一般结构，并证明这可以为我们提供最新的量子加速。特别是，我们获得了成本$ o（\ sqrt {s}）$的有界错误量子查询算法来计算可以通过大小$ s $的经典（甚至随机）决策树来计算的布尔函数（更一般而言，关系）。 Lin和Lin [TOC'16]以及Beigi和Taghavi [Quantum'20]显示出类似风味的结果，并以数量给出了上限，我们称之为决策树的“猜测复杂性”。我们确定决策树的猜测复杂性等于其等级，这是Ehrenfeucht和Haussler提出的这一概念[Inf。 comp.'89]在学习理论的背景下。这回答了林和林提出的一个问题，他们询问决策树的猜测复杂性是否与任何复杂性理论指标有关。我们还显示了完整二进制和或树的等级和随机等级之间的多项式分离。 Beigi和Taghavi构建了布尔功能的跨度程序和双对敌方解决方案，并给定经典决策树计算它们，并将非负权重分配给其边缘。我们探讨了将这些权重改变对双重对手界的生成跨度程序复杂性和客观价值的影响，并通过优化程序捕获最佳的加权方案。我们对该计划展示了解决方案，并从第一原则中争辩了它的最优性。我们还展示了我们的边界比林和林的界限强，而贝吉和塔加维的决策树。这回答了Beigi和Taghavi的问题，他们询问不同的加权方案是否可以产生更好的上限。
Given a classical query algorithm as a decision tree, when does there exist a quantum query algorithm with a speed-up over the classical one? We provide a general construction based on the structure of the underlying decision tree, and prove that this can give us an up-to-quadratic quantum speed-up. In particular, we obtain a bounded-error quantum query algorithm of cost $O(\sqrt{s})$ to compute a Boolean function (more generally, a relation) that can be computed by a classical (even randomized) decision tree of size $s$. Lin and Lin [ToC'16] and Beigi and Taghavi [Quantum'20] showed results of a similar flavor, and gave upper bounds in terms of a quantity which we call the "guessing complexity" of a decision tree. We identify that the guessing complexity of a decision tree equals its rank, a notion introduced by Ehrenfeucht and Haussler [Inf. Comp.'89] in the context of learning theory. This answers a question posed by Lin and Lin, who asked whether the guessing complexity of a decision tree is related to any complexity-theoretic measure. We also show a polynomial separation between rank and randomized rank for the complete binary AND-OR tree. Beigi and Taghavi constructed span programs and dual adversary solutions for Boolean functions given classical decision trees computing them and an assignment of non-negative weights to its edges. We explore the effect of changing these weights on the resulting span program complexity and objective value of the dual adversary bound, and capture the best possible weighting scheme by an optimization program. We exhibit a solution to this program and argue its optimality from first principles. We also exhibit decision trees for which our bounds are asymptotically stronger than those of Lin and Lin, and Beigi and Taghavi. This answers a question of Beigi and Taghavi, who asked whether different weighting schemes could yield better upper bounds.
