A Bi-directional Quantum Search Algorithm
Debanjan Konar Zain Hafeez Vaneet Aggarwal





 










A Bi-directional Quantum Search Algorithm
    Zain Hafeez^∗
Department of Physics, 

Purdue University, West Lafayette, USA


zhafeez@purdue.edu
Debanjan Konar^∗ and Vaneet Aggarwal
Purdue Quantum Science and Engineering Institute (PQSEI), and  

School of Industrial Eng., Purdue University, West Lafayette, USA 


dkonar@purdue.edu and  vaneet@purdue.edu

    
===========================================================================================================================================================================================================================================================================================================================

^∗These authors contributed equally to this work

  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 π/4√(2)√(𝒩)(1-√(1/b^r/2k)) iterations over regular Grover Search and Partial Grover Search (PGS), which take π/4√(𝒩)√(1-1/b) (here, 𝒩=2^r elements, b is the branching factor of partial search and k= ⌈log_2b ⌉).
  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>].



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




A Bi-directional Quantum Search Algorithm
    Zain Hafeez^∗
Department of Physics, 

Purdue University, West Lafayette, USA


zhafeez@purdue.edu
Debanjan Konar^∗ and Vaneet Aggarwal
Purdue Quantum Science and Engineering Institute (PQSEI), and  

School of Industrial Eng., Purdue University, West Lafayette, USA 


dkonar@purdue.edu and  vaneet@purdue.edu

    
===========================================================================================================================================================================================================================================================================================================================





§ INTRODUCTION





Grover's quantum search algorithm <cit.> 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 <cit.>, as well as theoretical evidence of the algorithm's efficiency <cit.>. Grover's Search (GS) technique only requires O(√(N)) <cit.> 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 <cit.>. One state out of every conceivable superposition state is the search entity in quantum processing. Grover's quantum search algorithm <cit.> asserts that in a r-qubit network, there are 2^r = 𝒩 states, and the chance of discovering each state is 1/N. Each state's amplitude is therefore 1/√(N). In the classical system, the identical problem requires a maximum of O(𝒩) <cit.> trials. Bennett et al. <cit.> states that no quantum approach can, asymptotically, solve the database search problem in fewer steps than O(√(𝒩)). Subsequently, Boyer et al. <cit.> 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 <cit.>, 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) <cit.>. Heiligman (2000) described a partial quantum search algorithm to find matches between two databases in O(𝒩^3/4 log 𝒩) <cit.>. 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(√(S)) <cit.>. A quantum search method for nearest pattern matching in O(√(S)), where S is the string's length, is introduced by P. Mateus <cit.>. A. Tulsi introduced a quantum search algorithm, which finds a single element in common between two sets in O(√(𝒩)) <cit.>. Grover and Radhakrishnan introduced a fast algorithm for partial Grover search relying on local and global searches <cit.> and attains π/4√(𝒩)√(1-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) <cit.>. 
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 <cit.>. 

This paper provides a bi-directional quantum search algorithm, which draws inspiration from the Quantum Partial Search Algorithm (QPSA) <cit.> and Depth-First Grover's Search (DFGS) <cit.>. 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.


    
  * 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. 
    
  * Furthermore, we have implemented the Depth-First Grover Search Algorithm (DFGS) <cit.> on quantum simulation for the first time and benchmarked with the proposed BDGS with empirical results. 
    
  * On parallelization, our novel Bi-directional approach requires π/4√(2)√(𝒩)(1-√(1/b^r/2k)) iterations over Depth-First Partial Grover Search (DFGS) and the regular Grover Search. 
   







§ PARTIAL GROVER'S SEARCH
 


Grover's algorithm for quantum searching is primarily concerned with searching an unstructured data array of 𝒩 items <cit.>. Grover's quantum search approach has to locate an element in the collection {L=L_1, L_2, L_3,… L_𝒩}, where 𝒩 is the total number of elements in the set L, to be effective. Finding an element in the collection is necessary for δ(x) →[0, 1] <cit.>. This is the responsibility of the Boolean function δ. The full Grover search algorithm locates the marked state in ℐ_f iterations <cit.>. 

    ℐ_f = π/4√(𝒩), 𝒩⟶∞

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 <cit.>. 

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 <cit.>. 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. 


 §.§ Oracle

An Oracle <cit.> is often shown as a black box that inverts the chosen coefficient of the target base state after receiving the input state, |y⟩.

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 <cit.>. The |0⟩ state, i.e.,1/√(2)(|0⟩+|1⟩), is superposed with equal probability over the |0⟩ and |1⟩ states when a H gate is applied to it. The following matrix represents an H gate:

    H = 1/√(2)[  1 -1;  1 -1 ].

The uniform superposition of every basis vector in the whole database serves as the starting point for the Grover search as follows <cit.>:

    |𝒮⟩ = 1/√(𝒩)∑_y=0^𝒩-1|y⟩, ⟨𝒮|𝒮⟩ =1.

Iteratively, the Grover's algorithm looks for a single target object |x⟩. A unitary transform is the Grover iteration:

    ℐ_G= -ℐ_sℐ_x,

Two inversions on the marked state |x⟩ are presented as ℐ_s (Diffusion operator) and ℐ_x (Oracle operator) as follows:

    ℐ_s = I-2|𝒮⟩⟨𝒮|,


    ℐ_x = I-2|x⟩⟨ x|

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 1/√(𝒩). All states have a mean amplitude of 1/√(𝒩). The initial state α^(0) has its amplitude transformed by the phase flip to -1/√(𝒩). The following is the change in mean amplitude (μ).

    μ^(0) = (𝒩-1)β^(0) + α^(0)/𝒩
    =  (𝒩-1)1/√(𝒩)-1/√(𝒩)/𝒩
     =𝒩-2/𝒩√(𝒩)
 
the amplitudes of the marked and unmarked states are denoted by α and β, respectively. 

The Grover iteration I_G rotates at an angle ω in Hilbert space, moving from 𝒮 to the destination |x⟩, where, sin^2 ω = 1/𝒩 and following t iterations

    ℐ_G^t|𝒮⟩ = sin ((2t +1)ω)|x⟩ + cos ((2t +1)ω)/√(𝒩-1)∑_𝒮≠ x^𝒩-1|𝒮⟩.

Hence, following ℐ_f = π/4ω-1/2 repetitions, the amplitudes of all other items vanish, and the probability amplitude of |x⟩ becomes unity.

    ℐ_G^t|𝒮⟩ = |x⟩.









 §.§ 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 1/√(𝒩). The marked state α^(1) has a new amplitude that can be calculated using formula 2.α^(0)-μ^(0). We can derive α^(1) as follows using μ^(0)= 𝒩-2/𝒩√(𝒩) and α^(0)= -1/√(𝒩) (from Equation <ref>):

    α^(1)=2(𝒩-2)/𝒩√(𝒩) +1/√(𝒩)
    = 3(𝒩-1)/N√(𝒩)
 



 §.§ Partial Grover Search Algorithm



Grover and Radhakrishnan (GRK) <cit.> 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 𝒩 items is divided into b identically sized blocks.

    ℬ = 𝒩/b

In partial Grover search, approximately π/4(1-c(b))√(𝒩) searches are required to locate the target block <cit.>. When the blocks are infinitely large (ℬ⟶∞), c(b) is a finite positive number that depends on b.

Every block has concurrent local Grover iterations, j, as follows.

    ℐ_L = ⊕_j=1^bℐ_L^j =-(⊕_j=1^bℐ_s^l)ℐ_x

where each ℐ_L^j = -ℐ_s^lℐ_x and inversion on the marked state (query to the oracle) |x⟩ is ℐ_x and the local inversion is presented as ℐ_s^l (Diffusion operator)

    ℐ_s^l = I-2|𝒮_l⟩⟨𝒮_l|,

The uniform superposition of items in a block, |𝒮_l⟩, is represented here as follows.

    |𝒮_l⟩ = 1/√(ℬ)∑_i=0^ℬ-1|z⟩.

Regional repetition ℐ_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 ω_l specified by

    sin^2 ω_l = b/𝒩 = 1/ℬ

Every item in non-target blocks can have its amplitudes eliminated by applying one more global iteration <cit.>.

    𝒟=ℐ_G ℐ_L^j ℐ_G^t|𝒮⟩ = sinω|x⟩ + cosω/√(ℬ-1)∑_𝒮≠ x^ℬ-1|𝒮⟩.

For GRK partial Grover's search, we randomly select (b - 1) blocks and apply Grover's quantum search method to 𝒩(1- 1/b) places inside the selected blocks. This would need π/4√(ℬ(b-1)) = π/4√(𝒩)√(b-1/b) inquiries are needed, and it is faster than a standard full Grover's search <cit.>.



§ BI-DIRECTIONAL GROVER SEARCH ALGORITHM



 A novel approach combining Bi-directional search (BDS) <cit.> and Partial Grover Search (PGS) <cit.> algorithms is proposed and referred to as Bi-directional Grover Search (BDGS) for faster convergence. 
 In the proposed quantum circuit, as shown in Figure <ref>, U_ω 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(√(𝒩)), 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 ℐ_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 ℐ_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 <cit.> to determine the next k= ⌈log_2 b ⌉ bits in forward and backward search in BDGS as follows:

    |X_0X_1⋯ X_iX_i+1_Found□□_Next k⋯⟩
    |X_0X_1⋯ X_iX_i+1_FoundX_i+2X_i+3_Next k⋯⟩


    |⋯□□_Prev. kX_i X_i+1⋯ X_r-1 X_r_Found⟩
    |⋯X_i-2 X_i-1_Prev. kX_i X_i+1⋯ X_r-1 X_r_Found⟩

Here, X_i ∈{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 𝒩 = 2^r

    |⋯⋯_Found l⟩⊗1/√(2^⌊ r/2 ⌋-l-1)⊕_i=0^⌊ r/2 ⌋-l-1 (|0⟩ + |1⟩)


    |⋯⋯_Found l⟩⊗1/√(2^⌊ r/2 ⌋-l)⊕_i=r-1^⌊ r/2 ⌋-l (|0⟩ + |1⟩)

As shown in Figure <ref>, 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⋯ and A_2 = 1111⋯ as follows.

    |0110⟩⊗1/√(2^r/2-4-1)⊕_i=0^⌊ r/2 ⌋-4-1 (|0⟩ + |1⟩)


 
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.




 §.§ Computational Complexity Analysis
 

In bi-directional search, if forward (ℱ) and backward (ℛ) passes to meet the satisfaction criteria 𝒞 =ℱ∧ℛ, it is considered the target item has been found. We can create a database with all r-length pathways (2^r = 𝒩), λ_1-λ_2-⋯λ_r. The subpath ℱ=λ_1-λ_2-⋯λ_⌊r/2k⌋ 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 <ref> sin [(2t +1)ω] =1, i.e., (2t +1)ω =π/2. 


Hence, the maximum number of ℐ_𝒢 iterations at level λ of the bi-directional tree search is evaluated as <cit.>.

    ℐ_𝒢^λ=π/4√(𝒩/2/b^λ)-π/4√(𝒩/2/b^λ +1).

Since (2t +1)ω =π/2, cos[(2t +1)ω] ≈ 0, which implies that regardless of the number of iterations, the amplitudes of non-target blocks are all set to 0 (Ref: Equation <ref>).

For example, as shown in Fig. <ref>, the database requires representing 8 qubits (𝒩=2^r). ℱ is the initial 2 qubits' satisfaction condition and ℛ is the final 2 qubits' satisfaction requirement, with 𝒞 =ℱ∧ℛ. Therefore, b = 2^2 and ℬ = 𝒩/2/b=4. 

According to GRK's partial Grover's search <cit.>, the total number of queries required for BDGS for a single partial Grover search in both forward and backward pass at level λ is π/4(√(𝒩/2/b^λ)-√(𝒩/2/b^λ +1)), assuming, on an average, each pass comprises ⌊N/2⌋ 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 λ. Hence, the total complexity of the proposed BDGS is

    2∑_λ =0^r/2k-1ℐ_G^λ + ℐ_L
    =2∑_λ =0^r/2k-1π/4(√(𝒩/2/b^λ)-√(𝒩/2/b^λ +1))_Partial Grover Search + π/4√(𝒩/2/b^r/2)_GS
    = 2π/4√(𝒩/2) -2π/4√(𝒩/2/b^r/2k) + π/4√(𝒩/2/b^r/2k)
    
    
    
    
       
    = 2π/4√(𝒩/2) -π/4√(𝒩/2/b^r/2k)
    = π/4√(2)√(𝒩)(1-√(1/b^r/2k))
       ≤π/4√(2)√(𝒩)≈ O(√(𝒩))

We deduce that the average number of oracle calls of BDGS is π/4√(2)√(𝒩)(1-√(1/b^r/2k)). Whereas, our BDGS, the DFGS <cit.> and the standard Grover Search <cit.>, attains same the average computational complexity of O(√(𝒩)).




§ 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 <ref>. In general, the database configuration and the quantum resources will significantly impact the value of k. We have also implemented a DFGS <cit.> 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 <cit.>. 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 <ref>. 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 <ref>. In addition, we have also visualized the number of iterations required with an increase in the number of qubits, as shown in Figure <ref>. 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. 





















 



§ DISCUSSION



In this study, we explore a class of structured bi-directional search problems for which the satisfaction criterion 𝒞 =ℱ∧ℛ can be decomposed to ℱ and ℛ, 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 ℱ and ℛ. 

The maximum number of Grover iterations 2∑_λ =0^r/2k-1ℐ_G^λ + ℐ_L for the bi-directional quantum search with a smaller oracle we provided in this work is π/4√(2)√(𝒩)(1-√(1/b^r/2k)).
Our simulation results show that the proposed BDGS algorithms yielded much shorter run times than DFGS <cit.> and standard GS <cit.> 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 𝒞 =ℱ∧ℛ. Hence, the procedure is not a universal search algorithm. 






















§ 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 #2858 FNPDR/2022.



§ CODE AVAILABILITY

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

IEEEtran





























