Berlin 2024 – wissenschaftliches Programm

Bereiche | Tage | Auswahl | Suche | Aktualisierungen | Downloads | Hilfe

QI: Fachverband Quanteninformation

QI 12: Poster I

QI 12.13: Poster

Dienstag, 19. März 2024, 11:00–14:30, Poster B

Hybrid classical-quantum text search based on hashing — •Farid Ablayev, Marat Ablayev, and Nailya Salikhova — Kazan, Russian Federation

We consider the problem of finding occurrences of a given substring w (of length m) in a text string (of length n).

We propose a hybrid classical - quantum algorithm A, that implements Grover’s search to find a given substring in a text.

What’s new is that our algorithm uses the hashing technique.

• The A algorithm produces a result with a high probability of obtaining the correct answer.
• The A algorithm is based on Grover’s search. This search is presented in the paper as an auxiliary algorithm A1 and requires O(√n) query steps.
• The A algorithm exponentially saves the number of qubits relative to the parameter m – the length of the substring. Namely, the algorithm requires O(log n+log m ) qubits for his work.

The main idea of the paper is the use of the uniform hash family functions technique to save space complexity in quantum search. The A algorithm is based on a certain universal family of hash functions. The arXiv version of the article was published in November 2024 https://arxiv.org/abs/2311.01213.

Keywords: quantum algorithms; text search; hashing; uniform hash family functions