Quantum search in a dictionary based on fingerprinting-hashing

Searching for a word in a text, as a task of searching for information in a database, has been considered in many works and has some specific features. First, the oracle $f_{w}$, defined by the task, is used to find the occurrence of the word $w$ in the dictionary $V$. Namely, $f_{w}(x)=1$ if and only if $w=x$. Secondly, for searching for a word in a text to speed up search in the 1970s and 1980s, hashing-based algorithms were proposed. The Knuth-Morris-Pratt (KMP) algorithm [7] and the Rabin-Karp algorithm [8] solve the problem in linear number of comparisons (in linear time), with $O(n+m)$ complexity.

It is clear that quantum algorithms for this task, based on Grover’s idea, provide a quadratic saving in the number of calls to the oracle. Note that to describe Grover’s algorithm, we first need to specify an efficient oracle circuit for $f_{w}$ for such algorithm. A number of similar studies in recent decades in the field of developing algorithms for searching for occurrences of a word $w$ in a text $V$ (in an unsorted dictionary $V$ constructed from the text) were devoted to the construction of efficient oracles $f_{w}$. A number of constructions of such oracles in terms of quantum circuits were proposed and the complexity of such circuits was studied: Practical Implementation of a Quantum String Matching Algorithm [9], Algorithm of Ramesh, Hariharan, and Vinay [10] (2003). Montanaro [11] (2017). Soni and Rasool [12] (2020).

Note that all of these listed results require $O(\log n+m)$ qubits to search for a word $w$ of length $m$ in a dictionary $V$ of size $n$.

The idea of using hashing methods for quantum information retrieval in an unordered database was realized in 2024 [13]. In [13], a hybrid classical-quantum (probabilistic-quantum) algorithm is proposed for searching a word $w$ of length $m$ in a dictionary $V$ of size $n$.

The key idea of the hybrid classical-quantum algorithm is as follows: (a) choose a universal hash family $\cal F$ of hash functions, (b) uniformly randomly choose a hash function $h\in{\cal F}$, (c) hash the elements of $V$ with the hash function $h$, and (d) apply the quantum amplification technique to search for the hash image $h(w)$ of the word $w$ in the hashed dictionary $h(V)$. It has been proven that using hashing methods can exponentially reduce the number of qubits required. Specifically, $\log n+\log m$ qubits are sufficient when using hashing, instead of $\log n+m$ qubits in algorithms without hashing.

The quantum fingerprinting-hashing technique (quantum fingerprinting-hashing technique or quantum hashing technique for short) is a key component of the algorithms considered in this paper. The quantum fingerprinting was formalized as a method of quantum information compression in 2001 by Burman et al. [14]. The quantum fingerprinting function presented in [14] was built on error-correcting codes. Various designs of quantum hash functions and their cryptographic properties were discussed in [15]. See also the book [16]. The quantum hash function $\psi:\Sigma^{m}\to({\mathcal{H}}^{2})^{\otimes s}$ maps words of length $m$ to $s$ qubit states. Such a map has the following important (for our algorithms) properties: (a) the map is contractive, i.e. $s<m$ (for example for fingerprinting function [14] $s=\log m$), (b) the resulting quantum states are highly distinguishable, and (c) the function $\psi$ is invertible.

In this work, we make a further step in applying hashing technique for finding a specific word of length $m$ from an unordered collection (vocabulary) of $n$ words, each of which has length $m$.

The quantum search algorithm works as follows. The vocabulary $V$ is represented as a quantum state ${\left|{V,\psi}\right\rangle}$, whose elements are hashed by the quantum hash function $\psi$. The search for an occurrence of the word $w$ is performed in two stages as follows. In the first stage, the quantum state is quantum-parallel inverted by the mapping $\psi^{-1}(w)$ determined by $w$. This stage provides the first level of amplitude amplification. Then, in the second stage, a known sequence of Grover amplitude amplification operators is applied. Finally, the resulting quantum state is measured, and the algorithm produces the result.

The high probability of the correct result is based on properties (b) and (c) of the quantum hash function — they provides a first level of amplitude amplification before applying the sequence of Grover amplitude amplification operators

The quantum hash function is memory efficient: searching for a word $w$ of length $m$ in a dictionary $V$ of size $n$ requires $O(\log n+s)$ qubits. The number of oracle calls is $O(\sqrt{n})$.

Note that, as in the previous work [13], we present the algorithm in terms of the quantum query model. This level of representation is sufficient to demonstrate the efficiency of memory use by the algorithm. We leave the issues of efficient implementation of the oracle scheme for further consideration.

The paper is organized as follows. In Section 2, we describe the quantum fingerprinting function and the necessary operators for its further implementation. In Section 3, we present a dictionary search algorithm based on the quantum fingerprinting function in technical detail. In Section 4, we formulate and prove theorems analyzing the operation of the algorithm and its complexity characteristics.

In Section 5.2, we generalize the specific construction of the algorithm from Section 3 to the general case of constructing ${\cal A}$ algorithms based on the quantum hashing technique in terms of an arbitrary $\epsilon$-collision-resistant quantum hash function $\psi$. More precisely, in Section 5 we present a group of algorithms that can differ depending on which quantum hash function (see Section 5.1) we use.

In Section 6, we present its characteristics. We conclude Section 6 with a discussion of the features of the algorithm.

The error-correcting code is defined by the mapping

$$E:\Sigma^{m}\to\Sigma^{l}$$

with the following condition: for any different words

$$w,w^{\prime}\in\Sigma^{m},$$

their maps

$$E(w),E(w^{\prime})\in\Sigma^{l}$$

satisfy the condition that the Hamming distance $d(E(w),E(w^{\prime}))$ between them is at least $d$.

Such a code $E$ is called an $(l,m,d)$-code. A binary code is one in which $\Sigma=\{0,1\}$.

For arbitrary $d>1$, there exists an $(l,m,d)$-error-correcting code $E$ with $l=cm$, $c>1$.

The function $\psi_{E}$ generated by the binary $(l,m,d)$-error-correcting code $E$ defined as follows.

For $s=\log l$ the function

$$\psi_{E}:\{0,1\}^{m}\to({\cal H}^{2})^{\otimes{(s+1)}}$$

is defined by the condition

$${\left|{\psi_{E}(w)}\right\rangle}=\frac{1}{\sqrt{2^{s}}}\sum_{i=0}^{2^{s}-1}{\left|{i}\right\rangle}{\left|{E_{i}(w)}\right\rangle},$$

(1)

where $E_{i}(w)$ is the $i$-th bit of the codeword $E(w)$.

In content: a word $w$ with length $m$ is mapped to a $(\log m+const)$-qubit quantum state ${\left|{\psi_{E}(w)}\right\rangle}$. This state ${\left|{\psi_{E}(w)}\right\rangle}$ represents the encoding $E(w)$ of the original word $w$. The state ${\left|{\psi_{E}(w)}\right\rangle}$ is a superposition over $s+1=\log m+const$ qubits.

Let ${\left|{\bf 0}\right\rangle}={\left|{0}\right\rangle}^{\otimes{(s+1)}}$.

The transformation

$$U_{\psi_{E}}:{\left|{\bf 0}\right\rangle}\xrightarrow{w}({\mathcal{H}}^{2})^{\otimes(s+1)}$$

(2)

acts on $(s+1)$-qubits. We define the transformation $U_{\psi_{E}}(w)=U_{E}(w)(H^{\otimes s}\otimes I)$. It is defined by a $2^{s+1}\times 2^{s+1}$ unitary matrix. It is a composition of the Hadamard transformation $H^{\otimes s}$, the identity transformation $I$ and the transformation $U_{E}$. It is convenient to define the $U_{E}$ transformation by describing its action on the $2^{s+1}$ vectors ${\left|{k}\right\rangle}$ of the computational basis $B=\{(0,\dots,1),\dots,(1,\dots,0)\}$ of the $({\mathcal{H}}^{2})^{\otimes(s+1)}$ space. The arguments of the transformation $U_{E}$ are words $w\in\{0,1\}^{m}$:

$${U_{E}}:{\left|{k}\right\rangle}\xrightarrow{w}{\left|{k^{\prime}}\right\rangle}.$$

${U_{E}}$ is defined by the codeword $E(w)$, which has a length of $l=2^{s}$. In terms of content, the transformation $U_{E}$ “changes” the last $(s+1)$-st qubit ${\left|{a}\right\rangle}$ in the basis state ${\left|{k}\right\rangle}={\left|{i}\right\rangle}\otimes{\left|{a}\right\rangle}$ to ${\left|{k^{\prime}}\right\rangle}={\left|{i}\right\rangle}\otimes{\left|{a\oplus E_{i}(w)}\right\rangle}$.

Proof. The transformation $H^{\otimes s}\otimes I$, transforms the basis state ${\left|{0}\right\rangle}^{\otimes{(s+1)}}$ into an equal-amplitude superposition of the first $s$ qubits (Hadamard transformation $H^{\otimes s}$ of the first $s$ qubits)

$${\left|{\bf 0}\right\rangle}={\left|{0}\right\rangle}^{\otimes{(s+1)}}\xrightarrow{H^{\otimes s}\otimes I}{\left|{\psi_{0}}\right\rangle}=\frac{1}{\sqrt{2^{s}}}\sum\limits_{i=0}^{2^{s}-1}{\left|{i}\right\rangle}\otimes{\left|{0}\right\rangle}.$$

Next, the transformation ${U_{E}}(w)$ transforms the state ${\left|{\psi_{0}}\right\rangle}$ to the state ${\left|{\psi_{E}(w)}\right\rangle}$:

$$\frac{1}{\sqrt{2^{s}}}\sum\limits_{i=0}^{2^{s}-1}{\left|{i}\right\rangle}\otimes{\left|{0}\right\rangle}\xrightarrow{{U_{E}}(w)}{\left|{\psi_{E}(w)}\right\rangle}=\frac{1}{\sqrt{2^{s}}}\sum_{i=0}^{2^{s}-1}{\left|{i}\right\rangle}{\left|{0\oplus E_{i}(w)}\right\rangle}=\frac{1}{\sqrt{2^{s}}}\sum_{i=0}^{2^{s}-1}{\left|{i}\right\rangle}{\left|{E_{i}(w)}\right\rangle}.$$

$\Box$
Next, we also need the transformation

$$U^{-1}_{\psi_{E}}:({\mathcal{H}}^{2})^{\otimes(s+1)}\xrightarrow{w}({\mathcal{H}}^{2})^{\otimes(s+1)},$$

given by words $w\in\{0,1\}^{m}$, and it is the inverse of the transformation $U_{\psi_{E}}$ in the following sense

$$U^{-1}_{\psi_{E}}:{\left|{\psi_{E}(w)}\right\rangle}\xrightarrow{w}{\left|{\bf 0}\right\rangle}.$$

Proof. Indeed, for an arbitrary word $w\in\{0,1\}^{m}$, for a $(s+1)$-qubit state ${\left|{\psi_{E}(w)}\right\rangle}$ it is true that $U^{-1}_{\psi_{E}}(w){\left|{\psi_{E}(w)}\right\rangle}={\left|{\bf 0}\right\rangle}$:

$$\frac{1}{\sqrt{2^{s}}}\sum_{i=0}^{2^{s}-1}{\left|{i}\right\rangle}{\left|{E_{i}(w)}\right\rangle}\xrightarrow{U_{E}(w)}\frac{1}{\sqrt{2^{s}}}\sum_{i=0}^{2^{s}-1}{\left|{i}\right\rangle}{\left|{E_{i}(w)\oplus E_{i}(w)}\right\rangle}=\frac{1}{\sqrt{2^{s}}}\sum\limits_{i=0}^{2^{s}-1}{\left|{i}\right\rangle}\otimes{\left|{0}\right\rangle}\xrightarrow{H^{\otimes s}\otimes I}{\left|{0}\right\rangle}^{\otimes{s+1}}.$$

$\Box$

Given an unordered set $V$ composed of $n$ binary sequences $w_{k}$, each of length $m$.

$$V=\{w_{0},\dots,w_{n-1}\},$$

where $w_{k}=\{0,1\}^{m}$ for $0\leq k\leq n-1$.

Given a binary string $w$ of length $m$, where $m<n$. It is required to find the index of the occurrence of $w$ in the sequence $V$. Namely, it is required to find an index $k$ such that $w=w_{k}$.

Note that this is essentially a database search problem.

The algorithm ${\cal A}$ consists of two parts:

1. 1.

   First part: preparing the initial state based on the sequence $V$.

2. 2.

   Second part: reading the search word $w$ and searching for its position in the sequence.

Note that the algorithm ${\cal A}$ takes different input data in the two parts: $V$ and $w$, respectively.

Description of the algorithm ${\cal A}$.

Input data:

For the first part: the sequence $V=\{w_{0},\dots,w_{n-1}\}$ of binary words with a length of $m$.

For the second part: a binary string $w$ with length $m$.

Output data: The index $k$, which denotes the number of an element in the sequence, such that $w=w_{k}$.

Thus, the algorithm ${\cal{A}}$ implements the mapping

$${\cal{A}}:V,w\longmapsto k.$$

1. 1.

   The first part of the algorithm (Initialization of hashed vocabulary) involves preparing the initial state ${\left|{V,\psi_{E}}\right\rangle}$.

   The initial state is

   $${\left|{\psi_{0}}\right\rangle}=\frac{1}{\sqrt{n}}\sum\limits_{j=0}^{n-1}{\left|{j}\right\rangle}\otimes{\left|{\bf 0}\right\rangle}\otimes{\left|{1}\right\rangle}.$$

   Here, ${\left|{\bf 0}\right\rangle}$ – is the zero state of $s+1$ qubits. According to this sequence $V$, based on the transformation $U_{\psi_{E}}$, which defines the quantum function $\psi_{E}$, the state ${\left|{0}\right\rangle}$ is converted into the initial state:

   $${\left|{V,\psi_{E}}\right\rangle}=\frac{1}{\sqrt{n}}\sum\limits_{j=0}^{n-1}{\left|{j}\right\rangle}\otimes{\left|{\psi_{E}(w_{j})}\right\rangle}\otimes{\left|{1}\right\rangle}.$$

   Recall that

   $${\left|{\psi_{E}(w_{j})}\right\rangle}=\frac{1}{\sqrt{2^{s}}}\sum_{i=0}^{2^{s}-1}{\left|{i}\right\rangle}{\left|{E_{i}(w_{j})}\right\rangle},$$

   (3)

2. 2.

   The second part of the algorithm ${\cal{A}}$ consists of reading the searched word $w$ and searching for a position $k$, such that $w=w_{k}$.

   The search procedure consists of applying the amplitude amplification method presented in the paper [2] and described in the book [4].

   • •

     Conversion hash transformation

     The $I^{\otimes\log{n}}\otimes U_{\psi_{E}}^{-1}(w)\otimes I$ operator is applied to the state ${\left|{V,\psi_{E}}\right\rangle}$,

     	$\displaystyle{\left|{V,\psi_{E},w}\right\rangle}$	$\displaystyle=$	$\displaystyle\frac{1}{\sqrt{n}}\sum\limits_{j=0}^{n-1}{\left|{j}\right\rangle}\left(\frac{1}{\sqrt{2^{s}}}\sum\limits_{i=0}^{2^{s}-1}{\left|{i}\right\rangle}{\left|{E_{i}(\omega_{j})\oplus E_{i}(\omega)}\right\rangle}\right){\left|{1}\right\rangle}$
     		$\displaystyle=$	$\displaystyle\frac{1}{\sqrt{n}}\sum\limits_{j=0}^{n-1}{\left|{j}\right\rangle}\left(\frac{1}{\sqrt{2^{s}}}\sum\limits_{i=0}^{2^{s}-1}{\left|{i}\right\rangle}\left(\sum\limits_{i:E_{i}(\omega_{j})=E_{i}(\omega)}{\left|{0}\right\rangle}+\sum\limits_{i:E_{i}(\omega_{j})\neq E_{i}(\omega)}{\left|{1}\right\rangle}\right)\right){\left|{1}\right\rangle}$
     		$\displaystyle=$	$\displaystyle\frac{1}{\sqrt{n}}\sum\limits_{j=0}^{n-1}{\left|{j}\right\rangle}{\left|{\phi_{E}(w_{j},w)}\right\rangle}{\left|{1}\right\rangle},$

     where ${\left|{\phi_{E}(w_{j},w)}\right\rangle}=U^{-1}_{\psi_{E}}(w){\left|{\psi_{E}(w_{j})}\right\rangle}$ for $j\in\{0,\dots,n-1\}$.

   • •

     Amplification

     The amplification procedure of the amplitudes of basic states ${\left|{j}\right\rangle}{\left|{0}\right\rangle}^{\otimes s+1}{\left|{1}\right\rangle}$ (“good states” as they are called in [4]) is applied to state ${\left|{V,\psi_{E},w}\right\rangle}$.

     The amplitude amplification procedure consists in the use of Grover macro steps according to the description in [4].

   • •

     Measurement

     The first $\log{n}+s+1$ qubits of the final state are measured in a computational basis. If the last $s+1$ qubits are all zero, then the result of measuring the first $\log n$ qubits is the position of element $w_{k}$, where $w_{k}=w$.