Berlin 2024 – scientific programme

Parts | Days | Selection | Search | Updates | Downloads | Help

QI: Fachverband Quanteninformation

QI 12: Poster I

QI 12.13: Poster

Tuesday, March 19, 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