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 use these data structures in quantum algorithms for two problems: the Exam Problem and the Largest File Problem. Finally, we suggest new quantum solution for strings sorting problem and show the lower bound. The upper bound and lower bound for the problem are the same up to log factor. At the same time, it is more effective than classical counterparts.