{'fraction_non_alphanumeric': 0.03804972612312062, 'fraction_numerical': 0.020670378468543606, 'mean_word_length': 4.463546798029556, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Implementation of efficient quantum search algorithms on NISQ computers

Despite the advent of Grover's algorithm for the unstructured search, its successful implementation on near-term quantum devices is still limited. We apply three strategies to reduce the errors associated with implementing quantum search algorithms. Our improved search algorithms have been implemented on the IBM quantum processors. Using them, we demonstrate three- and four-qubit search algorithm with higher average success probabilities compared to previous works. We present the successful execution of the five-qubit search on the IBM quantum processor for the first time. The results have been benchmarked using degraded ratio, which is the ratio between the experimental and the theoretical success probabilities. The fast decay of the degraded ratio supports our divide-and-conquer strategy. Our proposed strategies are also useful for implementation of quantum search algorithms in the post-NISQ era.


Introduction
In recent years, much progress has been made in building quantum processors [1][2][3][4] and demonstrating quantum advantage [5,6]. In fact, quantum algorithms are the reason why quantum computers are so powerful [7]. However, the errors resulting from noisy quantum gates and decoherence make these devices far from perfect. The term "Noisy Intermediate-Scale Quantum" (NISQ) has been coined to describe the current era of noisy quantum computers [8].
Circuit depth is a practical metric for quantum circuits. Circuit depth is defined as the number of consecutive elementary operations required to run a circuit on quantum hardware. For the same circuit, different hardwares may give different depths since the connectivity may vary from machine to machine [9]. Most quantum computers have the elementary single-and two-qubit gates, but the running time of an algorithm on a quantum computer is directly related to the number of two-qubit gates. The two-qubit gates are much harder to realize in experiments (also take more time than single-qubit gates) since they create entanglement and the states become classically intractable [7]. Circuits with longer depths are more susceptible to gate and decoherence errors. Thus, NISQ era algorithms strive for shallow depths [10].
Grover's algorithm is well-known for providing quadratic speedup for unstructured search problem [11,12]. It has wide applications, from exhaustive search for NP-hard problems [13] to quantum machine learning [14]. The theoretical complexity of Grover's algorithm is based on number of queries to oracle, often referred to as the black box. The oracle can identify the target item in a database. Grover's algorithm has been proven to be strictly optimal in the number of queries to the oracle [15,16].
Theoretical computational cost measures based on the oracular complexity, although useful for the theoretical analyses, are not very practical for assessing the performance of a quantum algorithm on real quantum machines. Given the wide-range of applications of Grover's algorithm, a line of research has been directed towards estimating its implementation cost, including its depth and width requirements [17][18][19][20]. While querying the oracle is an important operation, it is not the sole operation in Grover's algorithm. The other important part of Grover's algorithm is the diffusion operator. Previous studies have shown that variants of Grover's algorithm allow different choices for the diffusion operator, while maintaining the quantum speedup [21][22][23]. Partial diffusion operators, also called "local" diffusion operators, act on a subspace of the database. They are the key components in the partial search algorithms [24][25][26]. Interestingly, they can also be applied to the full search problem, decreasing the depth of the quantum search algorithms [27][28][29][30]. Such realizations make them much more viable for the NISQ devices.
Grover's algorithm for up to four-qubit search domain (2 4 = 16 elements) has been implemented previously on the IBM quantum processors [31][32][33] for unstructured search. In this paper, we apply three different strategies to improve the performance of quantum search algorithms on the NISQ devices: (i) the hybrid classical-quantum search, (ii) use of partial diffusion operators to optimize the depth of quantum search algorithms, and (iii) the divide-andconquer search. Here the divide-and conquer means that we find the partial target string at each step. Since we are considering unstructured search problem, we do not recursively apply the divide-and-conquer strategy here. The three strategies can be jointly applied for an enhanced error mitigation. We demonstrate the improved three-and four-qubit search implementations over the standard Grover's algorithm. The success probabilities are higher than previous reported results [31,32]. For the five-qubit cases on IBM quantum processors, the search results from the direct execution of Grover's algorithms are too noisy, no better than the random guess. Our improved version, based on the proposed hybrid classical-quantum strategy, gives higher success probabilities than the purely classical approach (classical linear search). To the best of our knowledge, this is the first time that the five-qubit search algorithm has been successfully executed on IBM quantum processors. Note that the fivequbit search has recently been implemented on the trapped-ion qubits [34]. We benchmark our results using the degraded ratio of success probabilities. The fast decay of the degraded ratio observed in our results implies favoring of shallow depth circuits on IBM quantum processors. This paper is organized as follows. In Sec. 2, we review full and partial search algorithms as well as introduce the notations used in our paper. In Sec. 3, we talk about three different strategies as mentioned above to improve the quantum search algorithms on real quantum devices. We present the results from executing these computational strategies on IBM's quantum computers in Sec. 4. Lastly, the conclusions from our study are presented in Sec. 5. Appendix includes more details on our notations and results presented in the main text.

Quantum search algorithms
First, we give a brief review of Grover's algorithm. Then we introduce the partial diffusion operator, a key component in our paper, that acts only on a subspace of the search domain.

Grover's algorithm
Grover's algorithm is realized by repeatedly applying the Grover operator, denoted as G n , on the initial state |s n [11,12]. The symbol n denotes the number of qubits, which implies that the number of items in the database is N = 2 n . The initial state, |s n , is uniform superposition of computational basis states of the Hilbert space, H ⊗n 2 . It can be realized by applying the Hadamard gate, H, as [7] |s n = H ⊗n |0 ⊗n .
Note that such a highly nontrivial initial state can easily be prepared with depth one. The Grover operator, G n , is a composition of two operators, the oracle and the diffusion operator. The oracle marks the target item and the diffusion operator creates an inversion about the mean. In Grover's algorithm, a query to the phase oracle results in a sign flip on the target state. We denote the oracle operation as Here, |t is the target state representing the target string t. The target state |t is also one of the computational basis states. We also refer to t as the target item or the target string in our paper. Operator 1 1 2 n is the identity operator acting on H ⊗n 2 . For convenience, we assume that there is a unique target state in the database. However, the depth reduction strategies in the next section do not limit to the case with a unique target state. The diffusion operator is independent of the oracle, and is defined as The oracle operator, O t , can be viewed as a reflection in the plane perpendicular to the target state |t . The diffusion operator, D n , reflects the amplitude in the average, since the state, |s n , is the equal superposition of all items in the database. Composed of the oracle, O t , and the diffusion operator, D n , the Grover operator, G n , is given by Starting with the initial state, |s n , and iteratively applying the Grover operator, G n , on subsequent states, gives P n (j) = | t|G j n |s n | 2 = sin 2 ((2j + 1)θ), where P n (j) is the probability finding the target string t after j iterations of the Grover operator on the initial state. The angle θ is defined as sin θ = 1/ √ N . When j reaches j max = π √ N /4 , the probability approaches unity. Thus, the oracular complexity of Grover's algorithm is O( √ N ), which is quadratic speedup compared to the classical complexity, O(N ). The idea behind Grover's algorithm is to increase the amplitude of the target state (approximately) linearly, which leads to a quadratic change in the probability as it is the amplitude squared. Moreover, Grover's algorithm is not limited to a specific initial state, such as the uniformly superimposed state, |s n . As long as some distributions of the database can be efficiently realized, the amplitude of the target state can be amplified via Grover's algorithm. This general version of the algorithm is called the amplitude amplification algorithm [35,36].
Although the general formalism of Grover's algorithm is simple, realizing it on real quantum computers (for unstructured search problems) is a non-trivial question. Different search problems have different realizations of the oracle. Recent studies have shown how to construct the oracle (via the elementary quantum gates) for the AES key search [17,19,37,38] and the MAX-CUT problem [33]. The construction of diffusion operator on real quantum devices is more straightforward. The diffusion operator, D n , and the n-qubit Toffoli gate denoted as Λ n−1 (X), are single-qubit-gate equivalent [7]. The notation X denotes the NOT gate, while n − 1 means that there are n − 1 control qubits. For example, when n = 2, Λ n−1 (X) gives the CNOT gate. The n-qubit Toffoli gate Λ n−1 (X) can be decomposed as a combination of single-and two-qubit gates with the depth linear in n (with ancillary qubits) [39].

Partial diffusion operator
The diffusion operator, D n , defined in Eq. (3), reflects the amplitudes in the average of all items. We can generalize such an operator as with m ≤ n. The diffusion operator, D n,m , only reflects the amplitude in the subspace of the database. As m < n, we refer to D n,m as the local or partial diffusion operator. For convenience, we drop n from the notation to denote D m ≡ D n,m , without any possibility of confusion. Combined with the oracle operator, O t , the local Grover operator is defined as Note that G m is still an n-qubit operator since the oracle acts on the full n-qubit space. The local diffusion operator can naturally solve the partial search problem [24][25][26], which finds the substring of the target state. For example, the target state |t , can be decomposed as |t = |t 1 ⊗ |t 2 . Assume that t 1 is (n − m)-bit length while t 2 is m-bit length. We can think that the database is divided into K = 2 n−m blocks. Each block has b = 2 m number of items (N = bK). Also, each block has the partial target string t 2 . The quantum partial search algorithm (QPSA) finds the target block represented by the target string t 1 . The target string t 2 is not concerned.
The most efficient QPSA (based on the oracular complexity) starts by running the global Grover operators first, followed by running the local Grover operators and lastly, runs a single global Grover operator [40]. Note that the operators, G n and G m , do not commute [41]. Thus, different orders of operators give different success probabilities. The QPSA trades accuracy for speed (based on the oracular complexity). The QPSA finds the target substring t 1 , with fewer queries to the oracle than the full search algorithm. The reduced number of oracles, compared to Grover's algorithm, scales as √ b [24][25][26]. Although QPSA is the main application of the local diffusion operator, Grover introduced the local diffusion operator before the invention of QPSA.
The local diffusion operator, introduced in [27], aims to reduce the total number of gates in the quantum search algorithm. This motivation is easy to see as the partial diffusion operator, D m , can be realized with fewer elementary quantum gates than the global diffusion operator, D n , with n > m. Recent studies have revealed several other ways to reduce the depth of quantum search algorithm by exploiting the partial diffusion operator [28,29]. We will discuss different strategies to improve the performance of quantum search algorithms on real devices in the next section.

Strategies to improve quantum search algorithms
In this section, we present three different strategies to improve accuracy and efficiency of the quantum search algorithm on the NISQ processors. Every strategy utilizes the local diffusion operator, D m , as defined in Eq. (6). In NISQ era, such strategies are important because they reduce the depth of the circuits. In post-NISQ era, such strategies can potentially reduce the physical resources needed for error correction, as well as the running time of the algorithms.

Hybrid search algorithm
The local diffusion operator, D m , only acts on the subset of the given database. We can renormalize the search space in order to exploit D m . Suppose that the search problem is to find the target string t with length n. The oracle can only recognise the target state |t . By renormalizing the search space, we prepare the initial state |t 1 ⊗ |s m , where t 1 is a specific string with length (n − m). If t 1 = t 1 (|t = |t 1 ⊗ |t 2 ), then using Eq. (5), the probability of finding t 2 after j iterations of G m on |t 1 ⊗ |s m is with sin θ b = 1/ √ b and b = 2 m . Let the probability that t 1 is t 1 be P (t 1 = t 1 ). The probability P m (j) is conditioned on the probability P (t 1 = t 1 ). Then the total probability of finding the target string t with j iterations of G m is P n (j) = P (t 1 = t 1 )P m (j).
For the unstructured search problem, the classical probability, P (t 1 = t 1 ), can only be given by randomly guessing on 2 n−m bits, i.e., P (t 1 = t 1 ) = 1/2 n−m . Random guessing does not require any quantum computational resources. We call such a search method as the hybrid classical-quantum search algorithm. The advantage for the hybrid classical-quantum search algorithm is twofold. First, the depth of G m is smaller than G n . If the total depth is fixed, the hybrid classical-quantum algorithm can apply more iterations of oracle. Second, quantum coherence during the algorithm is only required on the subspace H ⊗m 2 . The full search algorithm is based on the coherence on H ⊗n 2 , which is more fragile. Although the theoretical success probability is always smaller than the full search success probability with the same number of oracles, the real success probability could be higher because of its shorter depth and limited coherence between qubits. The theoretical success probability of hybrid search decays exponentially with respect to the number of randomly guessed qubits. Therefore, we do not expect a large number of randomly guessed qubits, especially for a large database. Therefore the hybrid strategy may not be suitable for post-NISQ search problems.

Depth optimization by partial diffusion operators
Grover's algorithm is optimal in the number of queries to the oracle [15,16]. However, the oracular complexity is not the only metric for determining an algorithm's requirement of the physical computational resources (such as the depth and the width of the circuit). The Grover operator is a combination of oracle operator and diffusion operator. The depth of the quantum search circuit can be reduced if we replace the global diffusion operator D n by the local diffusion operator D m . There are different ways to do such replacements [27][28][29][30]. Here, we follow the ideas from [29], which provides a general framework for depth optimization. Suppose that we design the search circuits by the operator Every local diffusion operator acts on the same subspace. To remove the ambiguity of the notation S n,m (j), we require that the last number j q is always for the local Grover operator. For example, S 6,4 ({2, 0}) = G 2 6 and S 6,4 ({1, 1}) = G 6 G 4 . Note that S n,m ({j, 0}) = G j n is the standard Grover's algorithm. We only consider one kind of local diffusion operator here. The idea below can be generalized to multi-type local diffusion operators local diffusion operators acting on different sizes of blocks, which gives the search operator S n,m1,m2,··· ,m k . The success probability of finding the target state by the operator S n,m (j) is P n,m (j) = | t|S n,m (j)|s n | 2 .
Since Grover's algorithm is strictly optimal in number of queries to the oracle [16], a local diffusion operator can only decrease the success probability compared to Grover's algorithm (with the fixed number of oracles). For example, The physical resources of quantum computers are the depth and the width. The depth roughly represents the physical running time of the circuit. We denote the depth of operator U as d(U ). For the same operator, different devices may have different depths due to the different connectivity of the qubits and the different sets of universal gates. Operator S n,m (j) can have lower depth compared to G j n (with the same number of oracles). For example, . We introduce the expected depth of the search circuit S n,m (j)) as Then the depth optimization strategy is to find the minimum of d n,m (j) given by We also optimize the size of the local diffusion operator given by the parameter m. Although we apply the local diffusion operator in S n,m (j), our algorithm is not the partial search algorithm. The minimal expected number of oracles for Grover's algorithm is studied in [15,42]. Recall that the maximal iteration (giving the maximal success probability) is j max = π √ N /4 . However, the minimal expected number of oracles is given by j exp = 0.583 √ N , which is smaller than j max . Incorporating the depth of global Grover operator d(G n ), the optimal iteration number, j exp , can give the minimal expected depth of Grover's algorithm. The significance of d n (given by the partial diffusion operator) is to win over the minimal expected depth of Grover's algorithm. Theoretical study shows that there is a critical depth ratio (the ratio between the depths of the oracle and the global diffusion operator), below which Grover's algorithm is not optimal in depth [29]. Such a critical depth ratio scales as O(n −1 2 n/2 ). For example in the 10-qubit search, the second strategy can be applied if the depth of oracle is smaller than 83.97 times the depth of the 10-qubit Toffoli gate. In practice, we would not have such a large oracle depth. For example, based on the data in [19], the depth of AES-128 oracle is around 10 times the depth of global diffusion operator.

Divide-and-conquer strategy
NISQ devices can only run shallow depth circuits [8]. Recent benchmarking results suggest that the fidelity of a circuit does not linearly decrease with the depth of two-qubit gates [32]. If we can reinitialize the input during the algorithm, then we can prevent the accumulation of errors at subsequent stages. The divide-and-conquer search algorithm is naturally related to QPSA. We can find partial bits of the target item, then renormalize the database to find the rest of the target string.
For simplicity, we consider the two-stage quantum search algorithm. It can be easily generalized into the multi-stage search algorithm. In the first stage, the task is to find the target substring, t 1 , with high probability. The second stage finds the rest target string, t 2 . The second-stage circuit will be dependent on the results from the first stage. The underlying idea behind the two-stage search algorithm is similar to the idea behind the hybrid classical-quantum search algorithm in Sec. 3.1. The difference is that both the stages are realized by quantum search algorithms. Suppose that the first stage is realized by the operator S (1) n,m (j). The initial state for the first stage is |s n . The probability finding the target substring, t 1 , is given by The diffusion operator, D m , in S n,m (j) acts on the qubits within the target substring, t 2 . In other words, we measure the qubits which are not acted upon by D m . Such a circuit design comes from QPSA.
Suppose we find t 1 at the first stage. We prepare the initial state |t 1 ⊗|s m . Then design the operator S (2) n,m with m < m for the second stage. Such a circuit is the normalized version of the full search algorithm. The probability of finding the remaining target string t 2 is with short notation |t 1 , s m = |t 1 ⊗ |s m . The operator S (2) n,m does not change the initial state |t 1 .
The expected depth of the above two-stage search algorithm is The minimal expected depth can be obtained by optimizing the operators and the size of the diffusion operators: We add a subscript 2 in d n,2 to distinguish the minimal expected depth of the full search d n in Eq. (13). It is expected that d n,2 < d n , since the measurement in the middle wipes out the amplified amplitude of the state |t 2 .
Only when the depth of the oracle is comparable to the depth of the global diffusion operator, the two-stage search algorithm can have lower depth than Grover's algorithm [29]. The motivation for the multi-stage circuits is to mitigate the errors. Another advantage of the multi-stage search circuit is its ability to run the quantum search algorithm in parallel [29,42]. We can assign the first stage circuit to different quantum computers. Then each device finds a different part of the target string t. Combining all the results gives the full target string.

Implementation on IBM quantum processors
First, we briefly present the basic setup as well as the circuit design from our implementation of the algorithms on the IBM quantum processors. Then we discuss the results on the three-, four-, and five-qubit search in the following subsections.

Circuit designs
The target item t is encoded in the oracle. We have assumed the uniqueness of the target item. As toy model, we choose the phase oracle presented in [3]. The n-qubit phase oracle is single-qubit-gate-equivalent to the n-qubit Toffoli gate Λ n−1 (X) (or the n-qubit controlled phase gate Λ n−1 (Z)). Note that the diffusion operator D n is also single-qubit-gate-equivalent to the nqubit Toffoli gate Λ n−1 (X) [7]. Although Qiskit provides the built-in n-qubit controlled gate, its fidelity and efficiency are not optimal. In the following, we show the realizations of three-, four-, and five-qubit controlled phase gate Λ n−1 (Z) from our implementation.
It is well-known that the three-qubit controlled phase gate, Λ 2 (Z) (or the Toffoli gate Λ 2 (X)), can be realized by six CNOT gates, with full connectivity between the three qubits [7]. Qubits with linear connectivity need additional SWAP gates for such a realization. In [32], Gwinner et al. provide a way to realize the three-qubit controlled phase gate Λ 2 (Z) via eight CNOT gates on linearly connected qubits, shown below.
Here, T is π/8 gate given by T = diag{1, e iπ/4 } with i = √ −1. The four-qubit gate Λ 3 (Z) can be realized by three Λ 2 (Z) gates in a Vshape design (with one clean ancillary qubit) [39]. As pointed in [43], we can take advantages of the relative-phase Toffoli gate to reduce the resources of nqubit Toffoli gate constructions. The three-qubit controlled Y gate (Y = ZX) can be realized as [44] • with the y-axis rotation gate G = R y (π/4). Then the four-qubit controlled phase gate Λ 3 (Z) can be constructed as with one ancillary qubit |0 . The rightmost CZ gate in the circuit (19) can be cancelled with the CZ gate in Λ 2 (Y † ) when the above Λ 3 (Z) gate is realized. Note that the CZ gate commutes with the Λ 2 (Z) gate. Similar to the realization of Λ 3 (Z) gate, we design the five-qubit controlled phase gate Λ 4 (Z) via two four-qubit controlled-Y gates Λ 3 (Y ) and one threequbit controlled phase gate Λ 2 (Z), in addition to one clean ancillary qubit. The four-qubit controlled gates Λ 3 (Y ) can be decomposed as [43] • Above circuit requires that the target qubit connects all the control qubits. The rightmost four-qubit controlled gate gives a relative phase ∓i to the states |1100 and |1101 , respectively. We do not need to physically realize such gate since it would be cancelled with its inverse in the realization of the Λ 4 (Z) gate, as shown below.
We can also design the Λ 4 (Z) gate via four Λ 2 (Y ) gates and one Λ 2 (Z) gate, which requires two clean ancillary qubits. Although this realization has fewer CNOT gates, its fidelity is lower. Seven-qubit superposition is more fragile than the superposition on the six qubits.

Setup
We run each circuit with randomly chosen target states in 30 trials. In each trial, the circuit is run with 8192 shots to calculate the success probability. We use the same 30 random target states for different search circuits, in order to compare the results between different search circuits. Since in the unstructured search problem, any target state is equally possible. Random choosen target state is more closed to the practical situation. Besides, state |1 relaxes to the ground state |0 with some probability. Therefore, target strings with larger Hamming weights have lower success probabilities on real devices. Random choosen target state can also mitigate such biases. To make sure that the random choosen target states are not biased, we list those target states in Appendix A. IBM provides processors with different number of qubits, ranging from one qubit to sixty five qubits. For our purposes, we implement the three-qubit search circuits on the five-qubit processor, Vigo. The four-qubit search circuits are implemented on both Vigo (the five-qubit backend with "T" connectivity) and Athens (the five-qubit backend with linear connectivity). The five-qubit search circuits are tested on the sixteen-qubit system, Guadalupe. See Figure  1 for the topological layout of the qubits in different processors. Note that the connectivity of Vigo is better than the connectivity of Athens. However, Athens has lower gate error rates in average than Vigo. In terms of the metric quantum volume, which characterizes the largest random circuit of equal width and depth that the computer successfully implements [9], Athens has quantum volume 32 while Vigo has 16.
Besides the success probability of the circuit, we also record the depth of each circuit. The depth is obtained after compiling for each specified backend. The depth obtained in this way represents the real operational length of the circuit. Every quantum processor can only perform four different gates (called the universal gate set) -z-axis rotation gate, X gate, square root X gate and CNOT gate. Oracles encoded different target states have slightly different depths. Combining the success probability and the circuit depth, we calculate the expected depth according to Eqs. (12) and (16), for the single-and twostage circuits respectively.
Recently, Wang et al. introduced the selectivity parameter, S, to quantify how distinct the signal is compared to the next most probable outcome [20]. The selectivity is also separately proposed in [45], called inference strength. It is important for understanding the quality of results obtained by a search algorithm on real devices. For our purposes, we simply treat it as the ratio between P t (the probability of obtaining the target string) and the maximum of P nt (the probability of obtaining the non-target string), defined by Selectivity less than 1 suggests the failure of the implementation. Note that the amplitudes of non-target states are never amplified in the quantum search algorithms. For the classical-quantum hybrid circuit, we only consider the selectivity for the results obtained from the quantum algorithm. In other words, P t is the probability of obtaining the target substring. For the multi-stage circuits, we choose the minimal selectivity among the circuits from the different stages. Note that the selectivity reveals the probabilistic distribution of the implementation results, rather than a theoretical parameter. We also benchmark the results via the degraded ratio, defined as Here, the probability P theo is the theoretical success probability of finding the target string (the theoretical success probability of the search circuit); probability P IBMq is the success probability obtained from the IBM quantum processors. Degraded ratio has been reported to decay exponentially with the number of two-qubit gates in [32]. Such fast degradation is the motivation for our multi-stage strategy.
For different circuits, we use the following notations. The Grover operator with the diffusion operator D m is denoted as Dm. Measurement on p qubits is Mp. If there is a classical initialization on q number of qubits, then it is Gq (see the hybrid search algorithm in Sec. 3.1). Note that the italic notation G m is for the Grover operator defined in Eq. (7). The left to right ordering represents the order in which these operations are carried out. We always specify the search domain for each circuit notations. For example, the three-qubit search circuit G1D2M2 represents the random initialization of one qubit followed by the Grover operator with a two-qubit diffusion operator and then measure these two qubits.
For the two-stage algorithm, we follow the same rules, but each of the stages is separated by a vertical line "|". For example, the three-qubit search circuit D2M1|D2M2 is a two-stage algorithm. In the first stage, the Grover operator G 2 (with two-qubit diffusion operator) is applied, then one of the qubits is measured (acted upon by the diffusion operator). The second stage is to initialize the state according to the results from the first stage (see Sec. 3.3 for details), then apply the Grover operator G 2 (with two-qubit diffusion operator) followed by the measurement on the two qubits (to be searched). A list of explanations on all the circuit notations can be found in Appendix. See Table 4 for the three-qubit search circuits and Table 7 for the four-qubit search circuits.

Three-qubit cases
Three-qubit Grover's algorithm gives the theoretical success probabilities of 0.781 and 0.945 with one and two Grover iterations, respectively. These two circuits are denoted as D3M3 and D3D3M3. We design another two circuits with one oracle, i.e., D2M3 and G1D2M2, which both give the 0.5 theoretical success probabilities. We design two different two-stage three-qubit search circuits. They both find one bit of the target in the first stage. One uses the three-qubit diffusion operator, i.e., D3M1, the other uses the two-qubit diffusion operator, i.e., D2M1. In the second stage, the circuits are equivalent to the two-qubit search, which gives success probability as 1 with just a single   (1) or d (2) is the depth of first or second stage circuit; d vigo theo or d athens theo is the theoretical expected depth of the circuit (given by the theoretical success probability) on Vigo or Athens; d vigo or d athens is the real expected depth of the circuit (given by the real success probability) on Vigo or Athens. Circuit names with black and red colors indicate the circuits with one and two oracles, respectively. The standard Grover's algorithm circuits are boxed. Circuits are ordered according to the magnitude of the expected depth obtained from the Vigo machine (top blue bar). Standard deviations are obtained from 30 trials with random target states. Each trial has 8192 shots.
Grover iteration, i.e., D2M2. The detailed explanations about these six circuits can be found in Appendix (Table 4).
We plot the success probabilities, as well as the selectivities, of the threequbit search circuits in Figure 2. The detailed data, as well as the thirty random target states, can be found in Appendix A. To exclude any possible biases from the random target states, we also provide supplementary data based on the average target states in Appendix B (Table 11). Both on the Vigo and Athens machines, the two-stage circuit D3M1|D2M2 gives the largest success probabilities. Both the two-stage circuits have higher success probabilities than Grover's realization D3D3M3, though D3D3M3 has the largest theoretical success probability. Such results demonstrate the significance of the divide-and-conquer strategy. The circuit G1D2M2 has the largest selectivity, which shows its robustness against the errors. The circuits D2M3 and G1D2M2 have the identical implementations except for the initial states. The success probability of G1D2M2 is slightly higher than D2M3 because the latter is only manipulating the two-qubit superposition states.
Incorporating the circuit depth with their success probabilities, we plot the expected depth in Figure 3. There are three different categories of the depth parameter. The first is the depth of the circuit, such as d(D3M3). The second is the theoretical expected depth, given by the theoretical success probability of the circuits. The last is the expected depth on real machines, given by the success probabilities obtained from the IBM quantum processors. The least expected depth on the Vigo and Athens machines are both given by the circuit G1D2M2. Although G1D2M2 has lower success probability than D3M3, its shallow depth can find the target state more efficiently. The two two-stage circuits have lower expected depth than Grover's D3D3M3, since they have lower depth realizations while maintaining higher success probabilities. Both D3M3 and D3D3M3 are the standard Grover's algorithm. Neither the oneoracle D3M3 nor the two-oracle D3D3M3 gives the optimal expected depth. Depth optimizations for the search algorithm are necessary when running on the real quantum devices.

Four-qubit cases
Four-qubit search has more scope for exploiting the partial diffusion operators than the three-qubit search. Including the standard Grover's algorithm with one and two oracles, we design a total of fourteen different circuits and test them on both the Vigo and Athens processors. See Appendix (Table 7) for detailed explanations on each circuit. Among the fourteen circuits, eight are one-stage circuits and six are two-stage circuits. Success probabilities of the one-stage circuits are plotted in Figure 4. For the two-stage circuits, the success probabilities are plotted in Figure 5. Also see Table 3 in Appendix A for the thirty random target states. The supplementary data on the average target states can be found in Appendix B (Table 12). . Here d (1) or d (2) is the depth of first or second stage circuit; d vigo theo or d athens theo is the theoretical expected depth of the circuit (given by the theoretical success probability) on Vigo or Athens; d vigo or d athens is the real expected depth of the circuit (given by the real success probability) on Vigo or Athens. Circuits are ordered according to the magnitude of the expected depth (top blue bar). Standard deviations are obtained from 30 trials with random target states. Each trial has 8192 shots.
Among the eight one-stage search circuits, D4D4M4 gives the largest theoretical probability 0.908. However, the real success probability is degraded below to 0.2 (both on Vigo and Athens) due to the actual implementation that has longer depth. On Vigo and Athens both, G1D3M3 gives the largest success probability among the one-stage circuits on real machines. On the Vigo machine, the two-oracle circuit D2D4M4 has larger success probability than the Grover's two-oracle circuit D4D4M4. Similar results are found on Athens. Local diffusion operators may decrease the theoretical success probability, but its low depth overcomes such disadvantages on quantum devices.
For more information on the two-stage circuits, see Figure 5. There are two types of two-stage four-qubit circuits. One type finds a target bit at the first stage; then finds the rest of the three target bits in the second stage. The other type searches two target bits in each of the two stages, which provides a higher probability than the first dividing strategy. Circuits implemented on Vigo have quite similar results on Athens. The two-stage circuit, D2M2|D2M2, gives the average success probability of 0.345. The two-oracle Grover's search, D4D4M4, has the average success probability of 0.195. Notably, our divideand-conquer circuit D2M2|D2M2 nearly doubles the success probability of the standard Grover's circuit D4D4M4. Compared to a recent study [32], our success probability for the four-qubit search algorithm exceeds 0.3, which is significant.
For the depth (the circuit depth, the theoretical expected depth and the expected depth on the real devices) of the one-stage and the two-stage fourqubit search circuits, see Figures 6 and 7. Note that because of the better connectivity of the Vigo, every circuit has slightly longer depth on Athens as compared to Vigo. The averaged circuit depth of G2D2M2 is less than the half of one-oracle Grover's circuit D4M4. However, the overall success probability of G2D2M2 is higher than D4M4. The expected depth of circuit G2D2M2 is far shorter than that of D4M4. The circuit G2D2M2 has the shortest theoretical expected depth both on the Vigo and Athens.
In the two-stage circuits, the two-two dividing has shorter depth than the one-three dividing. The two-two dividing exploits the local diffusion operator more efficiently. Note that the one-qubit quantum search algorithm is not well defined therefore we do not have the three-one dividing. The expected depth of two-oracle Grover's circuit D4D4M4 is > 800 (833.99 on Vigo and 1378.31 on Athens). The divide-and-conquer circuit (D2M2|D2M2) suppresses the expected depth below 300 (211.35 on Vigo and 287.58 on Athens).
Quantum algorithms with long circuits can not be directly divided into several stages, with new initialized states during the algorithm. Measurements in the middle will wipe out the established coherence between qubits. Suppose that the long circuit has the success probability of p. Dividing it into two parts gives the success probabilities p 1 and p 2 for each part, respectively. Previous theoretical study shows that p > p 1 p 2 [29]. However, our tests demonstrate that p < p 1 p 2 on real quantum computers. The explanation relies on benchmarking the parameter, the degraded ratio R, defined in Eq. (24). Based on our data from the four-qubit search circuits, we plot the degraded ratio versus the  number of two-qubit gates in Figure 8. The degraded ratio drops dramatically when the circuits have more than 30 two-qubit gates. In other words, if the number of two-qubit gates exceeds thirty, the noises may surpass the amplified amplitude of the target state. The data is fitted by the logistic function Here, x is the number of two-qubit gates and the numbers {a, b, c, d} are the parameters to be fitted. Similar benchmarking results have been reported in [32]. This exponential drop is the motivation for our divide-and-conquer designs and explains why the divide-and-conquer circuits have better performance than the one-stage circuits.

Five-qubit cases
To the best of our knowledge, the five-qubit search algorithm has never been successfully implemented on any of the IBM quantum processors. The five-qubit controlled Toffoli gate Λ 4 (X) requires more gates as well as more connectivity between qubits. We test the standard one-oracle Grover's algorithm D5M5 on the sixteen-qubit processor Guadalupe (only six qubits are used by our circuits). We choose the six qubits with least two-qubit gate errors. The probability of finding the target string is degraded to a lower value than the probability of finding the non-target string. See the results listed in Table 1. The selectivity is below 1, which implies the failure of the algorithm. Classical unstructured search with one oracle can find the target string with the probability 0.0625: randomly pickup a string then verify it with the oracle; if it is not the target string then randomly pickup another one ( 1 2 5 + 2 5 −1 2 5 × 1 2 5 −1 = 0.0625). The quantum search D5M5 (with the averaged success probability of 0.0257) is worse than the classical case. Similar results on the average target states can be found in Table 13 in Appendix B.
Although there are plenty of implementations of the five-qubit one-oracle search via the local diffusion operators, most of them give failed results (selectivity less than 1 and success probability less than classical search). However, we found that the classical-quantum hybrid search circuits G2D3M3 and G3D2M2 have selectivities larger than 1, see Table 1. G2D3M3 gives success probability higher than random pick, but relatively same as the classical search. G3D2M2 gives the average success probability 0.0963, which is higher than the classical algorithm (with one oracle). G3D2M2 randomly chooses three bits to perform the normalized two-qubit search algorithm. Since there are more two-qubit gates acting on the two qubits to be searched, we choose the physical two qubits with least errors of two-qubit gates. In our setup, physical qubits 13 and 14 are choosen, see Fig. 1. The theoretical success probability is 1/8 = 0.125, since the two-qubit search with one oracle has 1 as the success probability. Theoretically, G3D2M2 has only half success probability compared to D5M5. In practical, the success probability of G3D2M2 is three times higher than Grover's algorithm D5M5 because of its shallow depth. In the three-and four-qubit cases, such hybrid classical-quantum circuits always have the largest selectivity (see Figures 2 and 4). Thus, we can expect that the five-qubit search G3D2M2 stands out in the five-qubit search implementations.
Based on the success of G2D3M3 and G3D2M2, we test the divide-andconquer circuits D2M2|D3M3 and D3M3|D2M2, which replace the random guesses in G2D3M3 and G3D2M2 by the quantum partial search algorithms. Although we have selectivities of G2D3M3 and G3D2M2 larger than 1, the selectivities D2M2|D3M3 and D3M3|D2M2 are less than 1. It suggests that the quantum partial search algorithm in the first stage is not efficient, which does not provide quantum speedup.

Conclusion
In this paper, we have implemented the three-, four-and five-qubit search algorithms on the IBM quantum processors. Grover's algorithm does not provide the optimal performance on the NISQ devices. To reduce the noise, we have designed the quantum search circuits using the local diffusion operators. There are three different strategies to exploit the local diffusion operators. We realized the four-qubit search algorithm with the highest success probability compared to other studies. We also successfully ran the five-qubit search algorithm on the IBM quantum devices for the first time. Additionally, the use of multi-stage circuits makes it possible to run the search in parallel. We envision our work still be useful in post-NISQ era, since the lower depth circuits would require less resources for the error corrections. Table 3 Thirty random generated target states for the three-, four-, and five-qubit search algorithms. Thirty random target states   001  101  010  001  001  111  010  111  001  100   Three  011  000  100  111  010  011  110  111  110  011   101  111  110  001  001  000  001  001  001  001   1001  1101  1010  0001  1110  0010  1001  0100  0011  0111   Four  0001  0101  1110  0000  1010  1010  0101  0011  0001  0000   1100  0110  1111  0111  0000  0101  1101  1111  1000 Table 6 Success probabilities, selectivities and depths of the three-qubit search circuits. Circuit names with † are the standard Grover's algorithms. Standard deviations are obtained from 30 trials with random target states. Each trial has 8192 shots.  Table 9 Success probabilities, selectivities and depths of the four-qubit search circuits on IBM's Vigo and Athens machines. Circuit names with † are the standard Grover's algorithms. Standard deviations are obtained from 30 trials with random target states. Each trial has 8192 shots.