论文标题
嘈杂的树数据结构和量子应用
Noisy Tree Data Structures and Quantum Applications
论文作者
论文摘要
本文提出了一种用于构建称为步行树的嘈杂数据结构的技术。我们将其应用于红黑树（自相平衡的二进制搜索树的实现）和细分树。我们获得这些数据结构的主要操作的复杂性与没有噪声的情况（渐近）。我们介绍了量子算法的数据结构的几个应用。 最后，我们建议使用新的量子解决方案来分类问题并显示下限。上限和下限是相同的对数因子。同时，它比古典同行更有效。
The paper presents a technique for constructing noisy data structures called a walking tree. We apply it for a Red-Black tree (an implementation of a Self-Balanced Binary Search Tree) and a segment tree. We obtain the same complexity of the main operations for these data structures as in the case without noise (asymptotically). We present several applications of the data structures for quantum algorithms. Finally, we suggest new quantum solution for strings sorting problem and show the lower bound. The upper and lower bounds are the same up to a log factor. At the same time, it is more effective than classical counterparts.
