Noisy Tree Data Structures and Quantum Applications

We suggest a new technique for developing noisy tree data structures. We call it a walking tree. As applications of the technique we present a noisy Self-Balanced Binary Search Tree (we use a Red-Black tree as an implementation) and a noisy segment tree. The asymptotic complexity of the main operations for the tree data structures does not change compared to the case without noise. We apply the data structures in quantum algorithms for several problems on strings like the string-sorting problem and auto-complete problem. For both problems, we obtain quantum speed-up. Moreover, for the string-sorting problem, we show a quantum lower bound.

Automated summary

This article introduces a new technique called walking tree for developing noisy tree data structures. By applying this technique, the authors present noisy Self-Balanced Binary Search Tree and noisy segment tree, and use these data structures in quantum algorithms to solve string problems. The article also demonstrates a quantum lower bound and shows quantum speed-up for the string-sorting problem.