Academician O.B. Lupanov International Scientific Seminar "Discrete Mathematics and Its Applications"

Search tree with probabilistic key comparison and quantum string sorting

Kamil Ravilevich Khadiev

Published Jan 1, 2022• 0 citations

Abstract

In the framework of this work, a binary data structure is considered. search tree, specifically red-black tree as an implementation self-balancing search tree. We consider the case when procedure for comparing elements in a tree "noisy" or probabilistic. We present an algorithm that implements the main operations (adding, deleting, searching) with error probability O(1/n2) and running time t=O(log n) steps. And use the data structure to build a quantum algorithm sorting n strings of length k in O(n log n √k).

DOI: 10.20948/dms-2022-22

Related papers

Quantum version of self-balanced binary search tree with strings as keys and applications

Kamil Ravilevich Khadiev, Syumbel Enikeeva

In this paper, we present the data structure that implements the Self-Balanced Binary Search Tree with strings as keys and quantum comparing procedure. We cannot use the standard Self-Balanced Binary Search because of an error probability for the quantum comparing procedure. We can solve the issue using the standard success probability boosting technique. The presented data structure is more effective (in terms of running time) than using boosting technique. We apply the data structure for the Most Frequently String problem. So, we obtain a quantum algorithm for the problem that is faster than the existing quantum algorithm, and the best classical algorithm in the case of a significant part of the input strings (we mean O(n)) has a length that is at least ω((log n)2). Here n means the number of strings in a collection.

International Conference on Micro- and Nano-Electronics (ICMNE)Jan 31, 20225 citations

Noisy Tree Data Structures and Quantum Applications

Kamil Ravilevich Khadiev, Nikita V. Savelyev, Mansur Ziatdinov +1 more

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.

arXiv:2210.11197MathematicsNov 20, 20234 citations

Optimized Red-Black Trees for the Most Frequent String Problem in Noisy Comparison Models

Faruk Ibrahimović

This study addresses the Most Frequent Item (MFI) problem with respect to noisy comparisons, which has implications of a quantum speed-up for this problem. We introduce two variants of noisy Red-Black trees that support efficient searching and addition operations which also mitigate the uncertainty inherent in quantum string comparisons. Through detailed complexity analysis and extensive experimental validation, we compare these structures with a probability-boosting approach. Our findings suggest that these data structures are well-suited for high-stakes applications in telecommunication, where efficient and accurate data structures and algorithms are critical.

Telecommunications Forum (TELFOR)Nov 26, 20240 citations

Quantum Algorithms for Some Strings Problems Based on Quantum String Comparator

Kamil Ravilevich Khadiev, Artem Ilikaev, Jevgēnijs Vihrovs

We study algorithms for solving three problems on strings. These are sorting of n strings of length k, “the Most Frequent String Search Problem”, and “searching intersection of two sequences of strings”. We construct quantum algorithms that are faster than classical (randomized or deterministic) counterparts for each of these problems. The quantum algorithms are based on the quantum procedure for comparing two strings of length k in O(k) queries. The first problem is sorting n strings of length k. We show that classical complexity of the problem is Θ(nk) for constant size alphabet, but our quantum algorithm has O˜(nk) complexity. The second one is searching the most frequent string among n strings of length k. We show that the classical complexity of the problem is Θ(nk), but our quantum algorithm has O˜(nk) complexity. The third problem is searching for an intersection of two sequences of strings. All strings have the same length k. The size of the first set is n, and the size of the second set is m. We show that the classical complexity of the problem is Θ((n+m)k), but our quantum algorithm has O˜((n+m)k) complexity.

MathematicsJan 26, 202214 citations

First Tree-like Quantum Data Structure: Quantum B+ Tree

Hao Liu, Xiaotian You, Raymond Chi-Wing Wong

Quantum computing is a popular topic in computer science, which has recently attracted many studies in various areas such as machine learning and network. However, the topic of quantum data structures seems neglected. There is an open problem in the database area: Can we improve existing data structures by quantum techniques? Consider a dataset of key-record pairs. Given an interval as a query range, a classical B+ tree can report all the records with keys within this interval, which is called a range query, in O(log N + k) time, where N is the total number of records and k is the output size. It is asymptotically optimal in a classical computer but not efficient enough in a quantum computer, because it is expected that the execution time and the output size are linear in a quantum computer. In this paper, we propose the quantum range query problem. Different from the classical range queries, a quantum range query returns the results in quantum bits, which has broad potential applications due to the foreseeable advance of quantum computers and quantum algorithms. To the best of our knowledge, we design the first tree-like quantum data structure called the quantum B+ tree. Based on this data structure, we propose a hybrid quantum-classical algorithm to do the range search. It answers a static quantum range query in O(log_B N) time, which is asymptotically optimal in quantum computers. Since the execution time does not depend on the output size (i.e., k, which could be as large as O(N)), it is significantly faster than the classical data structure. Moreover, we extend our quantum B+ tree to answer the dynamic and d-dimensional quantum range queries efficiently in O(log^2_B N) and O(log^d_B N) time, respectively. Our experimental results show that our proposed quantum data structures achieve up to 1000x improvement in the number of memory accesses compared to their classical competitors.

arXiv:2405.20416May 30, 20241 citation

Quantum bounds for ordered searching and sorting

Peter Høyer, Jan Neerbek, Yaoyun Shi

We consider the quantum complexities of searching an ordered list and sorting an un-ordered list. For searching an ordered list of N elements, we prove a lower bound of \\frac{1}{\\pi}(\\ln(N)-1) on the number of oracle queries that access the list elements. This improves the previously best lower bound of ({1/12}\\log_2(N) - O(1)) due to Ambainis. For sorting N numbers, we prove a lower bound of \\frac{N}{2\\pi}(\\ln(N)-1) on the number of binary comparisons. The previously best lower bound is \\Omega(N). Our proofs are based on a weighted all-pairs inner product argument, and our results generalize to bounded error quantum algorithms. Both results are proven in the so-called quantum black box model, a quantum analogue of classical decision trees. In addition to our lower bound results, we give an exact quantum algorithm for ordered searching using (\\log_3(N) + O(1)) queries, which is roughly 0.631 \\log_2(N). Although our algorithm is worse than that of Farhi, Goldstone, Gutmann and Sipser, which makes 0.526 \\log_2(N) queries, its philosophy is completely different. Our algorithm is a quantum version of the classical binary search algorithm, and it uses a quantum routine for traversing through a binary search tree faster than classically.

Feb 15, 20013 citations