Lower Bounds on Quantum Query Complexity for Read-Once Decision Trees with Parity Nodes
Lower Bounds on Quantum Query Complexity for Read-Once Decision Trees with Parity Nodes
复制标题
具有奇偶校验节点的一次性读取决策树的量子查询复杂性下限
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Eiji Takimoto
中科院分区：
文献类型：
--
作者：
H. Fukuhara;Eiji Takimoto
我们引入了一种称为软排名的决策树复杂性度量，它可以衡量给定树的平衡程度。软秩是秩的某种放松变体。在深度为d的所有决策树中，完全二叉决策树（最平衡的树）具有最大软秩d，决策列表（最不平衡的树）具有最小软秩d，并且任何其他树具有在d和d之间的软秩。我们表明，对于任何决策树T在一些类G的决策树，其中包括所有的只读一次决策树，T的软秩是一个下界的量子查询的复杂性的布尔函数，T表示。这意味着对于任何由G中的决策树表示的布尔函数f，f的确定性查询复杂度仅比f的量子查询复杂度大二次方。
We introduce a complexity measure for decision trees called the soft rank, which measures how well-balanced a given tree is. The soft rank is a somehow relaxed variant of the rank. Among all decision trees of depth d, the complete binary decision tree (the most balanced tree) has maximum soft rank d, the decision list (the most unbalanced tree) has minimum soft rank √d, and any other trees have soft rank between √d and d. We show that, for any decision tree T in some class G of decision trees which includes all read-once decision trees, the soft rank of T is a lower bound on the quantum query complexity of the Boolean function that T represents. This implies that for any Boolean function f that is represented by a decision tree in G, the deterministic query complexity of f is only quadratically larger than the quantum query complexity of f.