2024/12/16 by Ablayev, Farid, Salikhova, Nailya, Ablayev, Marat
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Physical sciences #Information Theory (cs.IT) #Quantum Physics (quant-ph)
paper · doi:10.48550/arxiv.2412.11422
In this work, we present a quantum query algorithm for searching a word of length m in an unsorted dictionary of size n. The algorithm uses O(√(n)) queries (Grover operators), like previously known algorithms. What is new is that the algorithm is based on the quantum fingerprinting-hashing technique, which (a) provides a first level of amplitude amplification before applying the sequence of Grover amplitude amplification operators and (b) makes the algorithm more efficient in terms of memory use -- it requires O(log n + log m) qubits. Note that previously developed algorithms by other researchers without hashing require O(log n + m) qubits.