Noisy Tree Data Structures and Quantum Applications

Kamil Khadiev (), Nikita Savelyev, Mansur Ziatdinov and Denis Melnikov
Additional contact information
Kamil Khadiev: Institute of Computational Mathematics and Information Technologies, Kazan Federal University, 420008 Kazan, Russia
Nikita Savelyev: Intel Inc., D-81671 Munich, Germany
Mansur Ziatdinov: Institute of Computational Mathematics and Information Technologies, Kazan Federal University, 420008 Kazan, Russia
Denis Melnikov: Institute of Computational Mathematics and Information Technologies, Kazan Federal University, 420008 Kazan, Russia

Mathematics, 2023, vol. 11, issue 22, 1-18

Abstract: 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.

Keywords: noisy computation; self-balanced search tree; segment tree; quantum computation; quantum algorithms; string processing; sorting (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2023
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/11/22/4707/pdf (application/pdf)
https://www.mdpi.com/2227-7390/11/22/4707/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:11:y:2023:i:22:p:4707-:d:1284060

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().