A Bi-directional Quantum Search Algorithm

Zain Hafeez^∗ Department of Physics,
Purdue University, West Lafayette, USA
[email protected] Debanjan Konar^∗ and Vaneet Aggarwal Purdue Quantum Science and Engineering Institute (PQSEI), and
School of Industrial Eng., Purdue University, West Lafayette, USA
[email protected] and [email protected]

Abstract

Grover’s search algorithms, including various partial Grover searches, experience scaling problems as the number of iterations rises with increased qubits, making implementation more computationally expensive. This paper combines Partial Grover’s search algorithm and Bi-directional Search to create a fast Grover’s quantum search algorithm, referred to as Bi-Directional Grover Search (BDGS). We incorporated a bi-directional search tactic with a partial Grover search, starting from an initial state and a single marked state in parallel. We have shown in this article that our novel approach requires $\frac{\pi}{4\sqrt{2}}\sqrt{\mathcal{N}}(1-\sqrt{\frac{1}{b^{r/2k}}})$ iterations over regular Grover Search and Partial Grover Search (PGS), which take $\frac{\pi}{4}\sqrt{\mathcal{N}}\sqrt{1-\frac{1}{b}}$ (here, $\mathcal{N}=2^{r}$ elements, $b$ is the branching factor of partial search and $k=\lceil\log_{2}b\rceil$ ). The proposed BDGS algorithm is benchmarked against the state-of-the-art Depth-First Grover’s Search (DFGS) and generic Grover’s Search (GS) implementations for $2$ to $20$ qubits and provides promising results. The Qiskit Python implementation of the proposed BDGS algorithm is available on Github^∗^∗^∗https://github.com/hafeezzwiz21/DFGS-BDGS.

Index Terms:

Grover’s search algorithm, IBM quantum computer, Quantum Computing, Qubit

^{${}^{\ast}$}^{${}^{\ast}$}footnotetext: These authors contributed equally to this work

I Introduction

Grover’s quantum search algorithm [1] is one of the well-known applications of quantum computing, enabling quantum computers to perform a database search (an unsorted array) and quadratically outperform their classical counterparts in terms of time. Despite the efficient database search for an Oracle model (black box), researchers have shown several Grover circuit implementations across various platforms [2, 3, 4, 5, 6], as well as theoretical evidence of the algorithm’s efficiency [7]. Grover’s Search (GS) technique only requires O( $\sqrt{N}$ ) [8] evaluations to find an item with a high probability in an unstructured list. Compared to a classical system, Grover’s approach locates an entity in an unstructured list in fewer steps [1]. One state out of every conceivable superposition state is the search entity in quantum processing. Grover’s quantum search algorithm [1] asserts that in a $r$ -qubit network, there are ${2^{r}}$ = $\mathcal{N}$ states, and the chance of discovering each state is $\frac{1}{N}$ . Each state’s amplitude is therefore $\frac{1}{\sqrt{N}}$ . In the classical system, the identical problem requires a maximum of O( $\mathcal{N}$ ) [1] trials. Bennett et al. [8] states that no quantum approach can, asymptotically, solve the database search problem in fewer steps than O( $\sqrt{\mathcal{N}}$ ). Subsequently, Boyer et al. [9] has demonstrated that no quantum algorithm with a $50\%$ success probability can outperform Grover’s method by over a few percentage points. Grover’s search can solve collision problems, determine a dataset’s mean and median [1], and reverse-engineer cryptographic hash algorithms by revealing a victim’s password to an attacker.
However, generic Grover’s quantum search is computationally expensive in terms of computational time when the number of qubits or circuit depth increases, even though its implementation yielded a high success rate. To avoid a comprehensive (Grover) search and high computational complexity, the search often focuses on a block or collection of items that include the marked state rather than the marked state itself, and it is known as a Quantum Partial Search Algorithm (QPSA) [10]. Heiligman (2000) described a partial quantum search algorithm to find matches between two databases in $O(\mathcal{N}^{\frac{3}{4}}log\mathcal{N})$ [11]. Of late, a quantum pattern-matching method, as presented by P. Niroula et al., matches a search string (pattern) of length $S$ inside a larger text of length $T$ with time complexity $O(\sqrt{S})$ [12]. A quantum search method for nearest pattern matching in $O(\sqrt{S})$ , where $S$ is the string’s length, is introduced by P. Mateus [13]. A. Tulsi introduced a quantum search algorithm, which finds a single element in common between two sets in $O(\sqrt{\mathcal{N}})$ [14]. Grover and Radhakrishnan introduced a fast algorithm for partial Grover search relying on local and global searches [15] and attains $\frac{\pi}{4}\sqrt{\mathcal{N}}\sqrt{1-\frac{1}{b}}$ iterations. Recently, Guo et al. introduced an improved version of QPSA using Depth-First Search (DFS) referred to as Grover’s Search (DFGS) [16].
However, despite its potential in the faster partial Grover search procedures regarding iteration, partial Grover search algorithms have been limited in implementation due to their complex formulation [10]. This paper provides a bi-directional quantum search algorithm, which draws inspiration from the Quantum Partial Search Algorithm (QPSA) [15, 10] and Depth-First Grover’s Search (DFGS) [16]. We incorporated a Bi-directional search tactic with QPSA starting from an initial state and a single marked state in parallel. The notable contributions of the article are provided as follows.

1.

In this research, a faster and scalable bi-directional Grover’s search algorithm (BDGS) relying on partial Grover’s search for any number of qubits is introduced.
2.

Furthermore, we have implemented the Depth-First Grover Search Algorithm (DFGS) [16] on quantum simulation for the first time and benchmarked with the proposed BDGS with empirical results.
3.

On parallelization, our novel Bi-directional approach requires $\frac{\pi}{4\sqrt{2}}\sqrt{\mathcal{N}}(1-\sqrt{\frac{1}{b^{r/2k}}})$ iterations over Depth-First Partial Grover Search (DFGS) and the regular Grover Search.

II Partial Grover’s Search

Grover’s algorithm for quantum searching is primarily concerned with searching an unstructured data array of $\mathcal{N}$ items [17]. Grover’s quantum search approach has to locate an element in the collection $\{L=L_{1},L_{2},L_{3},\ldots L_{\mathcal{N}}\}$ , where $\mathcal{N}$ is the total number of elements in the set $L$ , to be effective. Finding an element in the collection is necessary for $\delta(x)\rightarrow[0,1]$ [6]. This is the responsibility of the Boolean function $\delta$ . The full Grover search algorithm locates the marked state in $\mathcal{I}_{f}$ iterations [15].

\mathcal{I}_{f}=\frac{\pi}{4}\sqrt{\mathcal{N}},\mathcal{N}\longrightarrow\infty

(1)

The input qubits are first converted into a superposition with equal coefficients using a Hadamard gate. The initial quantum state is subjected to phase inversion and inversion around the mean [6].
Grover’s iteration, also known as Grover’s operator, is used in the quantum Grover search circuit. Grover’s iteration is divided into two phases [17]. In a marked state, the oracle function first flips the phase of a single amplitude. The diffusion layer is said to have done its job when the indicated state amplitude flips over. The target state is inverted, causing its amplitude to grow dramatically while the amplitudes of the other states only slightly decrease. The other states maintain their previous amplitude.

II-A Oracle

An Oracle [18] is often shown as a black box that inverts the chosen coefficient of the target base state after receiving the input state, $|y\rangle$ .
Initialization: Due to creating an equal superposition of base states, the Hadamard gate ( $H$ gate) is utilized in the initial stage of Grover’s search algorithm to put all of the qubits in superposition [18]. The $|0\rangle$ state, i.e., $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$ , is superposed with equal probability over the $|0\rangle$ and $|1\rangle$ states when a $H$ gate is applied to it. The following matrix represents an $H$ gate:

H=\frac{1}{\sqrt{2}}\begin{bmatrix}1&\phantom{-}1\\ 1&-1\end{bmatrix}.

(2)

The uniform superposition of every basis vector in the whole database serves as the starting point for the Grover search as follows [19]:

|\mathcal{S}\rangle=\frac{1}{\sqrt{\mathcal{N}}}\sum_{y=0}^{\mathcal{N}-1}|y\rangle,\langle\mathcal{S}|\mathcal{S}\rangle=1.

(3)

Iteratively, the Grover’s algorithm looks for a single target object $|x\rangle$ . A unitary transform is the Grover iteration:

\mathcal{I}_{G}=-\mathcal{I}_{s}\mathcal{I}_{x},

(4)

Two inversions on the marked state $|x\rangle$ are presented as $\mathcal{I}_{s}$ (Diffusion operator) and $\mathcal{I}_{x}$ (Oracle operator) as follows:

\mathcal{I}_{s}=I-2|\mathcal{S}\rangle\langle\mathcal{S}|,

(5)

\mathcal{I}_{x}=I-2|x\rangle\langle x|

(6)

where $I$ is an identity operator.
The marked state undergoes a phase flip using the oracle function. All the states, including the one that is indicated, have an initial amplitude of $\frac{1}{\sqrt{\mathcal{N}}}$ . All states have a mean amplitude of $\frac{1}{\sqrt{\mathcal{N}}}$ . The initial state $\alpha^{(0)}$ has its amplitude transformed by the phase flip to $-\frac{1}{\sqrt{\mathcal{N}}}$ . The following is the change in mean amplitude ( $\mu$ ).

\begin{split}\mu^{(0)}=\frac{(\mathcal{N}-1)\beta^{(0)}+\alpha^{(0)}}{\mathcal{N}}\\ =\frac{(\mathcal{N}-1)\frac{1}{\sqrt{\mathcal{N}}}-\frac{1}{\sqrt{\mathcal{N}}}}{\mathcal{N}}\\ =\frac{\mathcal{N}-2}{\mathcal{N}\sqrt{\mathcal{N}}}\end{split}

(7)

the amplitudes of the marked and unmarked states are denoted by $\alpha$ and $\beta$ , respectively.
The Grover iteration $I_{G}$ rotates at an angle $\omega$ in Hilbert space, moving from $\mathcal{S}$ to the destination $|x\rangle$ , where, $\sin^{2}\omega=\frac{1}{\mathcal{N}}$ and following $t$ iterations

\mathcal{I}_{G}^{t}|\mathcal{S}\rangle=\sin((2t+1)\omega)|x\rangle+\frac{\cos((2t+1)\omega)}{\sqrt{\mathcal{N}-1}}\sum_{\mathcal{S}\neq x}^{\mathcal{N}-1}|\mathcal{S}\rangle.

(8)

Hence, following $\mathcal{I}_{f}=\frac{\pi}{4\omega}-\frac{1}{2}$ repetitions, the amplitudes of all other items vanish, and the probability amplitude of $|x\rangle$ becomes unity.

\mathcal{I}_{G}^{t}|\mathcal{S}\rangle=|x\rangle.

(9)

II-B Diffusion

A diffusion model can be implemented as HX + Oracle + XH, where $H$ represents the Hadamard transform and $X$ represents the $Pauli-X$ gate. This combination inverts the amplitudes surrounding their mean. According to Grover’s search, the amplitude of the marked state will rise by $\frac{1}{\sqrt{\mathcal{N}}}$ . The marked state $\alpha^{(1)}$ has a new amplitude that can be calculated using formula 2. $\alpha^{(0)}$ - $\mu^{(0)}$ . We can derive $\alpha^{(1)}$ as follows using $\mu^{(0)}$ = $\frac{\mathcal{N}-2}{\mathcal{N}\sqrt{\mathcal{N}}}$ and $\alpha^{(0)}$ = - $\frac{1}{\sqrt{\mathcal{N}}}$ (from Equation 7):

\begin{split}\alpha^{(1)}=2\frac{(\mathcal{N}-2)}{\mathcal{N}\sqrt{\mathcal{N}}}+\frac{1}{\sqrt{\mathcal{N}}}\\ =\frac{3(\mathcal{N}-1)}{N\sqrt{\mathcal{N}}}\end{split}

(10)

II-C Partial Grover Search Algorithm

Grover and Radhakrishnan (GRK) [15] proposed a faster quantum search method for partial search using the same Oracle as the Grover algorithm. The partial search also begins with the uniform superposition of all base states. The generic partial Grover search problem considers the following: A database with $\mathcal{N}$ items is divided into $b$ identically sized blocks.

\mathcal{B}=\frac{\mathcal{N}}{b}

(11)

In partial Grover search, approximately $\frac{\pi}{4}(1-c(b))\sqrt{\mathcal{N}}$ searches are required to locate the target block [15]. When the blocks are infinitely large ( $\mathcal{B}\longrightarrow\infty$ ), $c(b)$ is a finite positive number that depends on $b$ .
Every block has concurrent local Grover iterations, $j$ , as follows.

\mathcal{I}_{L}=\bigoplus_{j=1}^{b}\mathcal{I}_{L}^{j}=-(\bigoplus_{j=1}^{b}\mathcal{I}_{s}^{l})\mathcal{I}_{x}

(12)

where each $\mathcal{I}_{L}^{j}=-\mathcal{I}_{s}^{l}\mathcal{I}_{x}$ and inversion on the marked state (query to the oracle) $|x\rangle$ is $\mathcal{I}_{x}$ and the local inversion is presented as $\mathcal{I}_{s}^{l}$ (Diffusion operator)

\mathcal{I}_{s}^{l}=I-2|\mathcal{S}_{l}\rangle\langle\mathcal{S}_{l}|,

(13)

The uniform superposition of items in a block, $|\mathcal{S}_{l}\rangle$ , is represented here as follows.

|\mathcal{S}_{l}\rangle=\frac{1}{\sqrt{\mathcal{B}}}\sum_{i=0}^{\mathcal{B}-1}|z\rangle.

(14)

Regional repetition $\mathcal{I}_{L}$ is the Grover iteration carried out concurrently in every block. Only the target block has a non-trivial operation [rotation] with a new rotation angle $\omega_{l}$ specified by

\sin^{2}\omega_{l}=\frac{b}{\mathcal{N}}=\frac{1}{\mathcal{B}}

(15)

Every item in non-target blocks can have its amplitudes eliminated by applying one more global iteration [20].

\mathcal{D}=\mathcal{I}_{G}\mathcal{I}_{L}^{j}\mathcal{I}_{G}^{t}|\mathcal{S}\rangle=\sin\omega|x\rangle+\frac{\cos\omega}{\sqrt{\mathcal{B}-1}}\sum_{\mathcal{S}\neq x}^{\mathcal{B}-1}|\mathcal{S}\rangle.

(16)

For GRK partial Grover’s search, we randomly select ( $b-1$ ) blocks and apply Grover’s quantum search method to $\mathcal{N}(1-\frac{1}{b})$ places inside the selected blocks. This would need $\frac{\pi}{4}\sqrt{\mathcal{B}(b-1)}=\frac{\pi}{4}\sqrt{\mathcal{N}}\sqrt{\frac{b-1}{b}}$ inquiries are needed, and it is faster than a standard full Grover’s search [15].

III Bi-directional Grover Search Algorithm

A novel approach combining Bi-directional search (BDS) [21] and Partial Grover Search (PGS) [15] algorithms is proposed and referred to as Bi-directional Grover Search (BDGS) for faster convergence. In the proposed quantum circuit, as shown in Figure 1, $U_{\omega}$ and $U_{s}$ are two functions as the Oracle and Diffuser, respectively. The main idea of BDGS lies in forward and backward passes from the initial and target states simultaneously until the two search frontiers intersect. The entire solution path is then formed by concatenating the path from the start state with the inverse path from the target state. Optimal solutions are guaranteed using the proposed bi-directional quantum search algorithm with a time complexity of $O(\sqrt{\mathcal{N}})$ , and each search only needs to go halfway down the solution depth in parallel.
In this proposed BDGS algorithm,
1. we recursively traversed each possible solution interval at each layer using Partial Grover Search (quantum operator $\mathcal{I}_{G}$ ) for $b$ blocks to identify which intervals among the $b$ (branching factor) equal-size split sub-interval has a solution.
2. Finally, a standard Grover Search (using quantum operator $\mathcal{I}_{f}$ ) is involved in determining the precise address of the solution for intervals whose widths are less than or equal to $b$ .
The proposed BDGS algorithm incorporates Partial Grover Search [21] to determine the next $k=\lceil\log_{2}b\rceil$ bits in forward and backward search in BDGS as follows:

\begin{split}|\underbrace{X_{0}X_{1}\cdots X_{i}X_{i+1}}_{Found}\underbrace{\square\square}_{Next~{}k}\cdots\rangle\xrightarrow[Forward]{\text{Partial Grover Search}}\\ |\underbrace{X_{0}X_{1}\cdots X_{i}X_{i+1}}_{Found}\underbrace{X_{i+2}X_{i+3}}_{Next~{}k}\cdots\rangle\end{split}

(17)

\begin{split}|\cdots\underbrace{\square\square}_{Prev.~{}k}\underbrace{X_{i}X_{i+1}\cdots X_{r-1}X_{r}}_{Found}\rangle\xrightarrow[Backward]{\text{Partial Grover Search}}\\ |\cdots\underbrace{X_{i-2}X_{i-1}}_{Prev.~{}k}\underbrace{X_{i}X_{i+1}\cdots X_{r-1}X_{r}}_{Found}\rangle\end{split}

(18)

Here, $X_{i}\in\{0,1\}$ . Two auxiliary qubits are placed to store the following: (1) the bits’ found value; and (2) the bits’ status (checked and unchecked). The qubits will be initialized into a superposition of this encoding. Assuming $\mathcal{N}=2^{r}$

\begin{split}|\underbrace{\cdots\cdots}_{Found~{}l}\rangle\otimes\frac{1}{\sqrt{2^{\lfloor r/2\rfloor-l-1}}}\bigoplus_{i=0}^{\lfloor r/2\rfloor-l-1}(|0\rangle+|1\rangle)\end{split}

(19)

\begin{split}|\underbrace{\cdots\cdots}_{Found~{}l}\rangle\otimes\frac{1}{\sqrt{2^{\lfloor r/2\rfloor-l}}}\bigoplus_{i=r-1}^{\lfloor r/2\rfloor-l}(|0\rangle+|1\rangle)\end{split}

(20)

As shown in Figure 2, since the first four bits are determined on the second layer, the first four bits are encoded by the auxiliary qubits, which have the values $A_{1}$ = $0110\cdots$ and $A_{2}$ = $1111\cdots$ as follows.

\begin{split}|\underbrace{0110}\rangle\otimes\frac{1}{\sqrt{2^{r/2-4-1}}}\bigoplus_{i=0}^{\lfloor r/2\rfloor-4-1}(|0\rangle+|1\rangle)\end{split}

(21)

Refer to caption — Figure 1: Quantum Circuit schematic for Bi-directional Grover’s Quantum Search ( $U_{\omega}$ and $U_{s}$ are oracle and diffuser, respectively.)

We aim to find the next $k$ bits using the Partial Grover Search, but the determined bits are fixed. A pseudo-code for our BDGS algorithm Procedure BDGS () has been provided to understand the potential readers better.

Begin

Data: Quantum register

Q

, and a target element

x

Result: Index of target,

x

if found, else

-1

1 Procedure BDGS (

k

b

r

x

)

2 // The input-

k

: Number of bits representing segments of the search space,

3 //

b

: Branching factor of the bi-directional tree search space,

4 //

r

: Total number of bits representing the entire database,

5 //

x

: Target element to find.

6 Initialization of Input Qubits

8 7 Initialize Quantum Register

Q

with

r

qubits, set to

|0\rangle^{r}

2^{r}=\mathcal{N}

10 9 Apply Hadamard gates to all input qubits

Q

H^{\otimes r}|0^{r}\rangle

11 Initialization of Auxilary Qubits

13 12 Initialize

k=\lceil\log_{2}b\rceil

auxiliary qubits,

A

|0\rangle^{k}

14 Forward Search Phase

16 15 for $j\leftarrow 0$ to $\lfloor\frac{r}{2}\rfloor-1$

18 17

s=[j,min(j+k-1,\lfloor\frac{r}{2}\rfloor)]

19 // Here,

s

is a qubits segment selected for the current search.

21 20

j=j+k

23 22 Perform PGS (

Q,s,x,|A\rangle

)

24 end

25 Backward Search Phase

27 26 for $j\leftarrow r-1$ to $\lfloor\frac{r}{2}\rfloor$

29 28

s=[max(j-k+1,\lfloor\frac{r}{2}\rfloor)]

31 30

j=j+k

33 32 Perform PGS (

Q,s,x,|A\rangle

)

34 // Perform partial Grover search, PGS () targeting

x

2

qubits at a time.

36 end

38 37Measure all qubits, i.e., qubit register

Q

40 39 Procedure PGS (

Q,s,x,|A\rangle

)

42 41 Apply Oracle to mark the state corresponding to

x

44 43 Apply Diffusion operator to amplify the marked state.

46 45 return

48 End

Algorithm 1 Bi-directional Grover Search Algorithm

III-A Computational Complexity Analysis

In bi-directional search, if forward ( $\mathcal{F}$ ) and backward ( $\mathcal{R}$ ) passes to meet the satisfaction criteria $\mathcal{C}=\mathcal{F}\wedge\mathcal{R}$ , it is considered the target item has been found. We can create a database with all r-length pathways ( $2^{r}=\mathcal{N}$ ), $\lambda_{1}-\lambda_{2}-\cdots\lambda_{r}$ . The subpath $\mathcal{F}=\lambda_{1}-\lambda_{2}-\cdots\lambda_{\lfloor\frac{r}{2k}\rfloor}$ path each vertex once.
The proposed BDGS algorithm’s initial step aims to increase the target blocks’ amplitude using Partial Grover Search iteratively. To make it, in Equation 8 $\sin[(2t+1)\omega]=1$ , i.e., $(2t+1)\omega=\frac{\pi}{2}$ .
Hence, the maximum number of $\mathcal{I_{G}}$ iterations at level $\lambda$ of the bi-directional tree search is evaluated as [15].

\mathcal{I_{G}}^{\lambda}=\frac{\pi}{4}\sqrt{\frac{\frac{\mathcal{N}}{2}}{b^{\lambda}}}-\frac{\pi}{4}\sqrt{\frac{\frac{\mathcal{N}}{2}}{b^{\lambda+1}}}.

(22)

Since $(2t+1)\omega=\frac{\pi}{2}$ , $\cos[(2t+1)\omega]\approx 0$ , which implies that regardless of the number of iterations, the amplitudes of non-target blocks are all set to $0$ (Ref: Equation 8).
For example, as shown in Fig. 2, the database requires representing $8$ qubits ( $\mathcal{N}=2^{r}$ ). $\mathcal{F}$ is the initial $2$ qubits’ satisfaction condition and $\mathcal{R}$ is the final $2$ qubits’ satisfaction requirement, with $\mathcal{C}=\mathcal{F}\wedge\mathcal{R}$ . Therefore, $b=2^{2}$ and $\mathcal{B}=\frac{\mathcal{N}/2}{b}=4$ .
According to GRK’s partial Grover’s search [15], the total number of queries required for BDGS for a single partial Grover search in both forward and backward pass at level $\lambda$ is $\frac{\pi}{4}(\sqrt{\frac{\mathcal{N}/2}{b^{\lambda}}}-\sqrt{\frac{\mathcal{N}/2}{b^{\lambda+1}}})$ , assuming, on an average, each pass comprises $\lfloor\frac{N}{2}\rfloor$ states.
The BDGS procedure does partial or regular Grover searches for intervals with a size less than or equal to $b$ for each query at level $\lambda$ . Hence, the total complexity of the proposed BDGS is

\begin{split}2\sum_{\lambda=0}^{r/2k-1}\mathcal{I}_{G}^{\lambda}+\mathcal{I}_{L}\\ =\underbrace{2\sum_{\lambda=0}^{r/2k-1}\frac{\pi}{4}(\sqrt{\frac{\mathcal{N}/2}{b^{\lambda}}}-\sqrt{\frac{\mathcal{N}/2}{b^{\lambda+1}}})}_{Partial~{}Grover~{}Search}+\underbrace{\frac{\pi}{4}\sqrt{\frac{\mathcal{N}/2}{b^{r/2}}}}_{GS}\\ =2\frac{\pi}{4}\sqrt{\mathcal{N}/2}-2\frac{\pi}{4}\sqrt{\frac{\mathcal{N}/2}{b^{r/2k}}}+\frac{\pi}{4}\sqrt{\frac{\mathcal{N}/2}{b^{r/2k}}}\\ =2\frac{\pi}{4}\sqrt{\mathcal{N}/2}-\frac{\pi}{4}\sqrt{\frac{\mathcal{N}/2}{b^{r/2k}}}\\ =\frac{\pi}{4\sqrt{2}}\sqrt{\mathcal{N}}(1-\sqrt{\frac{1}{b^{r/2k}}})\leq\frac{\pi}{4\sqrt{2}}\sqrt{\mathcal{N}}\approx O(\sqrt{\mathcal{N}})\end{split}

(23)

We deduce that the average number of oracle calls of BDGS is $\frac{\pi}{4\sqrt{2}}\sqrt{\mathcal{N}}(1-\sqrt{\frac{1}{b^{r/2k}}})$ . Whereas, our BDGS, the DFGS [16] and the standard Grover Search [17], attains same the average computational complexity of $O(\sqrt{\mathcal{N}})$ .

IV Simulation Results

We have conducted various trials on quantum simulation on a qubit space ranging from $4$ to $20$ qubits on the Qiskit Aer simulator^∗^∗^∗https://qiskit.github.io/qiskit-aer/stubs/qiskit_aer.AerSimulator.html with $1024$ shots with each execution on $8$ -cores systems with a maximum frequency of 3.5 GHz and $8$ -GB RAM. In our quantum simulation settings, we implemented the Oracle and Diffuser searching for $k=2$ qubits as a part of a partial search in the forward and backward direction for the proposed BDGS algorithm. The choice of $k=2$ has functioned flawlessly in a database with an even distribution. An oracle design for $k=2$ has been shown in Figure 3. In general, the database configuration and the quantum resources will significantly impact the value of $k$ . We have also implemented a DFGS [16] algorithm based on a similar partial search method in a depth-wise manner using the same quantum simulation settings. We performed $5$ distinct trials in the experiments using the proposed BDGS, DFGS, and standard GS algorithms [17]. The simulation results demonstrate a significant improvement in runtime without compromising the accuracy of the proposed BDGS search algorithm compared with DFGS and standard GS algorithms, as shown in Table I. It is worth noting that the runtime of standard GS grows exponentially with an increase in the search space, whereas DFGS and BDGS grow linearly, as shown in Figure 4. In addition, we have also visualized the number of iterations required with an increase in the number of qubits, as shown in Figure 5. Our results indicate that DFGS and BDGS significantly lower the required iterations, making it far more efficient for larger search spaces. It may be noted that for $20$ qubits search space, the standard GS takes $804$ iterations, whereas DFGS and the proposed BDGS require only $10$ and $5$ iterations, respectively.

TABLE I: Comparative performance analysis of the proposed Bi-directional Grover’s Search (BDGS), standard Grover’s Search (GS) [17], and Depth-First Grover’s Search (DFGS) [16] with

1024

shots

Qubits	Trial	Acc.	Time(s)	Acc.	Time(s)	Acc.	Time(s)
		GS		DFGS		BDGS
	1	$95.3$	$0.00267$	$100$	$0.00174$	$100$	$0.00117$
	2	$96.6$	$0.00245$	$100$	$0.00197$	$100$	$0.00113$
4	3	$96.2$	$0.00222$	$100$	$0.00174$	$100$	$0.00108$
	4	$96.7$	$0.00263$	$100$	$0.00251$	$100$	$0.00104$
	5	$96.3$	$0.00300$	$100$	$0.00135$	$100$	$0.00104$
	Avg.	$96.02$	$0.00259$	$100$	$0.00186$	$100$	$0.00109$
	1	$100$	$0.0148$	$100$	$0.00255$	$100$	$0.00147$
	2	$100$	$0.0127$	$100$	$0.00301$	$100$	$0.00165$
8	3	$100$	$0.0131$	$100$	$0.00290$	$100$	$0.00170$
	4	$100$	$0.0123$	$100$	$0.00344$	$100$	$0.00152$
	5	$100$	$0.0133$	$100$	$0.00332$	$100$	$0.00163$
	Avg.	$100$	$0.0132$	$100$	$0.00304$	$100$	$0.00159$
	1	$100$	$0.206$	$100$	$0.00676$	$100$	$0.00224$
	2	$100$	$0.152$	$100$	$0.00737$	$100$	$0.00256$
16	3	$100$	$0.146$	$100$	$0.00617$	$100$	$0.00242$
	4	$100$	$0.150$	$100$	$0.00623$	$100$	$0.00248$
	5	$100$	$0.149$	$100$	$0.00589$	$100$	$0.00245$
	Avg.	$100$	$0.161$	$100$	$0.00645$	$100$	$0.00243$
	1	$100$	$0.810$	$100$	$0.00708$	$100$	$0.00284$
	2	$100$	$0.755$	$100$	$0.00705$	$100$	$0.00284$
20	3	$100$	$0.774$	$100$	$0.00799$	$100$	$0.00283$
	4	$100$	$0.780$	$100$	$0.00833$	$100$	$0.00261$
	5	$100$	$0.767$	$100$	$0.00786$	$100$	$0.00274$
	Avg.	$100$	$0.781$	$100$	$0.00766$	$100$	$0.00277$

V Discussion

In this study, we explore a class of structured bi-directional search problems for which the satisfaction criterion $\mathcal{C}=\mathcal{F}\wedge\mathcal{R}$ can be decomposed to $\mathcal{F}$ and $\mathcal{R}$ , the search-based satisfaction conditions. Using smaller oracles, we introduce the faster quantum partial search method for a single target item. The BDGS algorithm’s general concept is to parallelly increase the amplitude of the items in each block that fulfill $\mathcal{F}$ and $\mathcal{R}$ .
The maximum number of Grover iterations $2\sum_{\lambda=0}^{r/2k-1}\mathcal{I}_{G}^{\lambda}+\mathcal{I}_{L}$ for the bi-directional quantum search with a smaller oracle we provided in this work is $\frac{\pi}{4\sqrt{2}}\sqrt{\mathcal{N}}(1-\sqrt{\frac{1}{b^{r/2k}}})$ . Our simulation results show that the proposed BDGS algorithms yielded much shorter run times than DFGS [16] and standard GS [17] while maintaining similar measurement accuracy. This is primarily attributed to the efficient usage of gates and Grover iterations in DFGS and BDGS.
Moreover, owing to the decomposition of the entire problem search space into two halves (forward and backward passes), the proposed BDGS algorithm only requires smaller oracles, which is the most significant advantage of the quantum search with smaller oracles. The circuit depth of oracles will rise as database size increases. Operating the quantum circuit error-free becomes increasingly tricky as the circuit depth increases. Our BDGS technique will mitigate this issue by employing smaller oracles. Smaller oracles are more straightforward to build and aid in the error-free operation of the quantum circuit.
However, the proposed BDGS algorithm’s supremacy suffers due to the structured search problems subject to the requirements of satisfaction of the condition $\mathcal{C}=\mathcal{F}\wedge\mathcal{R}$ . Hence, the procedure is not a universal search algorithm.

VI Conclusion

This article offers the first new attempt to enable the creation of Bi-directional implementations of partial Grover’s quantum search method with a reduction in computational complexity. Here, the proposed quantum circuit is simulated for 2-qubit to 20-qubit circuits and enabled for scalable solutions for any number of qubits. The proposed framework exhibits a potential solution for quantum advantage in implementing our Bi-directional Grover’s Search (BDGS) algorithm without compromising the probability of success in searching a target. Our unique approach uses amplitude amplification to solve all problems and achieves the same efficiency as the standard Grover search with a lesser run time. Hence, our proposed BDGS offers an efficient usage of gates allowing for significantly smaller run times. In forthcoming research, the proposed Bi-directional Grover’s Search has the potential to extend to a multi-solution search using a hybrid quantum-classical approach to enable solutions for applications across various fields with better performance waiting to be discovered.

Acknowledgment

This work was partially supported by the Fulbright-Nehru Visiting Researcher Grant $\#2858FNPDR/2022$ .

Code availability

The Qiskit Python implementation of the proposed BDGS algorithm is available on Github: https://github.com/hafeezzwiz21/DFGS-BDGS.

References

[1] L. K. Grover, “Quantum mechanics helps in searching for a needle in a haystack,” Physical review letters, vol. 79, no. 2, p. 325, 1997.
[2] C. Durr and P. Hoyer, “A quantum algorithm for finding the minimum,” arXiv, 1999.
[3] G. Brassard, P. HØyer, and A. Tapp, “Quantum cryptanalysis of hash and claw-free functions,” In proc. LATIN 1998: Theoretical Informatics, Springer, Berlin, Heidelberg, vol. 1380, pp. 163–169, 1998.
[4] ——, “Quantum counting,” In proc. Automata, Languages and Programming: ICALP 1998, Springer, Berlin, Heidelberg, vol. 1443, pp. 159–164, 1998.
[5] N. J. Cerf, L. K. Grover, and C. P. Williams, “Nested quantum search and structured problems,” Phys. Rev. A, vol. 61, p. 032303, 2000.
[6] N. Mahmud, B. Haase-Divine, A. MacGillivray, and E. El-Araby, “Quantum dimension reduction for pattern recognition in high-resolution spatio-spectral data,” IEEE Transactions on Computers, vol. 71, no. 1, pp. 1–12, 2022.
[7] C. Zalka, “Grover’s quantum searching algorithm is optimal,” Phys. Rev. A, vol. 60, no. 4, pp. 2746–2751, 1999.
[8] C. H. Bennett, E. Bernstein, G. Brassard, and U. Vazirani, “Strengths and weaknesses of quantum computing,” SIAM Journal on Computing, vol. 26, no. 5, pp. 1510–1523, 1997.
[9] M. Boyer, G. Brassard, P. Høyer, and A. Tapp, “Tight bounds on quantum searching,” Fortschr. Phys., vol. 46, no. 4/5, pp. 493–505, 1998.
[10] V. Korepin and L. Grover, “Simple algorithm for partial quantum search,” Quantum Inf Process, vol. 5, p. 5–10, 2006.
[11] M. Heiligman, “Finding matches between two databases on a quantum computer,” 2000.
[12] P. Niroula and Y. Nam, “A quantum algorithm for string matching,” npj Quantum Inf, vol. 7, no. 37, 2021.
[13] P. Mateus and Y. Omar, “Quantum pattern matching,” 2005.
[14] A. Tulsi, “Optimal quantum searching to find a common element of two sets,” 2012.
[15] L. K. Grover and J. Radhakrishnan, “Is partial quantum search of a database any easier?” in Proceedings of the Seventeenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2005, p. 186–194.
[16] H. Guo, “Depth-first grover search algorithm on hybrid quantum-classical computer,” 2022.
[17] L. K. Grover, “A fast quantum mechanical algorithm for database search,” In Proc. 28th Annu. ACM Symp. Theory Comput., pp. 212–219, 1996.
[18] C. P. Williams, “Explorations in quantum computing,” Texts in Computer Science, Springer, 2011.
[19] I. Chuang and M. Nielsen, Quantum computation and quantum information, 2001, vol. 54.
[20] V. Korepin and J. Liao, “Quest for fast partial search algorithm,” Quantum Inf Process, vol. 5, p. 209–226, 2006.
[21] R. E. Korf, “Search techniques,” in Encyclopedia of Information Systems, 2003, pp. 31–43.