Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Telecommunications Forum (TELFOR)

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

Faruk Ibrahimović

Published Nov 26, 2024• 0 citations
Publisher

Abstract

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.

DOI
10.1109/telfor63250.2024.10819126

Related papers

Search tree with probabilistic key comparison and quantum string sorting

Kamil Ravilevich Khadiev

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).

Academician O.B. Lupanov International Scientific Seminar "Discrete Mathematics and Its Applications"•Jan 1, 2022•0 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.11197•Mathematics•Nov 20, 2023•4 citations

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, 2022•5 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.

Mathematics•Jan 26, 2022•14 citations

Quantum Search in an Ordered List via Adaptive Learning

Michael Ben-Or, Avinatan Hassidim

We use a Bayesian approach to optimally solve problems in noisy binary search. We deal with two variants: 1. Each comparison can be erroneous with some probability $1 - p$. 2. At each stage $k$ comparisons can be performed in parallel and a noisy answer is returned We present a (classic) algorithm which optimally solves both variants together, up to an additive term of O(\log \log(n)), and prove matching information theoretic lower bounds. We use the algorithm to improve the results of Farhi et al \cite{FGGS99} presenting a quantum (error free) search algorithm in an ordered list of expected complexity less than (\log_2n) / 3.

arXiv:quant-ph/0703231•Mar 24, 2007•12 citations

The Bayesian Learner is Optimal for Noisy Binary Search (and Pretty Good for Quantum as Well)

Michael Ben-Or, Avinatan Hassidim

We use a Bayesian approach to optimally solve problems in noisy binary search. We deal with two variants:1. Each comparison is erroneous with independent probability 1-p. 2. At each stage k comparisons can be performed in parallel and a noisy answer is returned. We present a (classical) algorithm which solves both variants optimally (with respect to p and k), up to an additive term of O(loglog n), and prove matching information-theoretic lower bounds. We use the algorithm to improve the results of Farhi et al., presenting an exact quantum search algorithm in an ordered list of expected complexity less than (log2n)/3.

Annual Symposium on Foundations of Computer Science•Oct 1, 2008•75 citations
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.
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).
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.
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.
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.
We use a Bayesian approach to optimally solve problems in noisy binary search. We deal with two variants: 1. Each comparison can be erroneous with some probability 1−p1 - p1−p. 2. At each stage kkk comparisons can be performed in parallel and a noisy answer is returned We present a (classic) algorithm which optimally solves both variants together, up to an additive term of O(\log \log(n)), and prove matching information theoretic lower bounds. We use the algorithm to improve the results of Farhi et al \cite{FGGS99} presenting a quantum (error free) search algorithm in an ordered list of expected complexity less than (\log_2n) / 3.
We use a Bayesian approach to optimally solve problems in noisy binary search. We deal with two variants:1. Each comparison is erroneous with independent probability 1-p. 2. At each stage k comparisons can be performed in parallel and a noisy answer is returned. We present a (classical) algorithm which solves both variants optimally (with respect to p and k), up to an additive term of O(loglog n), and prove matching information-theoretic lower bounds. We use the algorithm to improve the results of Farhi et al., presenting an exact quantum search algorithm in an ordered list of expected complexity less than (log2n)/3.