{'fraction_non_alphanumeric': 0.030333619340836823, 'fraction_numerical': 0.011860899409478626, 'mean_word_length': 4.32062298603652, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Optimizing Quantum Search with a Binomial Version of Grover's Algorithm

Amplitude Amplification -- a key component of Grover's Search algorithm -- uses an iterative approach to systematically increase the probability of one or multiple target states. We present novel strategies to enhance the amplification procedure by partitioning the states into classes, whose probabilities are increased at different levels before or during amplification. The partitioning process is based on the binomial distribution. If the classes to which the search target states belong are known in advance, the number of iterations in the Amplitude Amplification algorithm can be drastically reduced compared to the standard version. In the more likely case in which the relevant classes are not known in advance, their selection can be configured at run time, or a random approach can be employed, similar to classical algorithms such as binary search. In particular, we apply this method in the context of our previously introduced Quantum Dictionary pattern, where keys and values are encoded in two separate registers, and the value-encoding method is independent of the type of superposition used in the key register. We consider this type of structure to be the natural setup for search. We confirm the validity of our new approach through experimental results obtained on real quantum hardware, the Honeywell System Model H0 trapped-ion quantum computer.


I. INTRODUCTION
Quantum Search is a fundamental building block of Quantum Computing, providing a quadratic advantage over its classical counterpart.
In any context, searching requires a search space and a search condition. In Quantum Computing, a search space is defined by the state of a quantum system, and a search condition is specified by a quantum oracle, which is required to flip the phases of the target states, which are those satisfying the underlying condition. Alternatively, the marking can consist of setting certain qubits to fixed values. An oracle specific to the target states (search condition) is applied to a superposition state (search space) in order to mark the target states. The Grover Iterate will amplify the probability of the marked state(s).
In general, the oracle has to make some assumptions about how the search space is encoded, based on the problem that needs to be solved. In this paper, we are going to look into ways the oracle can adjust the superposition state to amplify the amplitude of the target states in an efficient way.
One can randomly try different types of superposition that favor a set of states, for example those with a given number of 1s in their binary representations, essentially using a binomial superposition instead of a uniform one. The superposition type can be passed as a parameter to the algorithm.
In this paper, we make the following novel contributions: 1. We outline a method for partitioning the basis states into classes, and amplifying the amplitudes of the states in each partition class in a non-uniform way, before repeatedly applying a Grover Iterate specific to a given search target state. When the partition class to which the target state belongs is sufficiently amplified, the number of times the Grover Iterate needs to be applied can be drastically reduced.
2. This method can provide an additional parameter that can be used to optimize Quantum Search. In particular, in the adaptive version of Grover's Search algorithm, in addition to varying the number of times the Grover Iterate is applied, one can also vary a level of non-uniform amplitude preamplification.
3. We provide the numerical analysis for the partitioning of basis states into classes based on the number of 1s in their binary representation, which essentially leads to a binomial distribution for the partition amplitudes.
4. We show how the method can be applied to set search, array element retrieval, and array element search.

5.
We also successfully validate the results on a real quantum computer, and we believe these to be one of the earliest successful quantum search experiments on 4 and 5 qubits using a quantum computer.
The remainder of this paper is structured as follows: Section II goes over the standard, uniform version of Grover's algorithm, which is contrasted with our contribution-the binomial version-in Section III. Additional analysis and examples are provided in Section IV. Section V presents an empirical evaluation of the novel, binomial version of Grover's Search, side by side with the uniform version. The experimental results are conducted on real hardware. Finally, Section VI concludes the paper.

A. The Grover Iterate
Given an n-qubit quantum system with basis states that correspond to the set S = {0, 1, . . . , 2 n − 1}, a predicate function f : S → {0, 1}, and a set E ⊆ {|0 , |1 , . . . , |2 n − 1 } of good basis states that f maps to 1, the Grover Iterate G is comprised of three components [ 3. The diffusion operator D, which multiplies the amplitude of the |0 n state by −1 Given the above, the Grover Iterate is defined as G = −ADA † O. For the normalized states, defined as follows: where E = S \ E is the complement of E, after applying j iterations of G to A |0 , we obtain: where θ is the angle in [0, π/2] that satisfies sin 2 θ = p(E).

B. Grover's Search Algorithm
The original Grover's Search algorithm was formulated as a particular case of the formalism in Section II A, where A = H ⊗n creates an equal superposition, and there is only one search target, i.e. E consists of a single element, and p(E) = 1 2 n . Theorem 1 (Uniform Amplification). The amplitude of a target state marked by an oracle O after applying j ≥ 0 where θ = arcsin 1 2 n .
Note that we can remove the negative sign in the definition of the Grover Iterate, and then Expression 5 changes to: For a number of Grover iterations j ≥ 0, measuring the state described in Eq. 4 will return the target state with probability Choosing j = [ π 4θ − 1 2 ] will maximally amplify the amplitude of the target state. We will denote this number of iterations by j uniform . Sometimes j = π 4 √ 2 n is used as a simpler approximation [2].

A. Binomial Grover Iterate
In [3,4] we introduced a generalization of the Amplitude Amplification algorithm [1,2], with the following ingredients: • Any unitary operator A, which creates a superposition state • A property-encoding operator B that maps distinct groups of states in different ways • A simple, binary-matching oracle O B , whose purpose is to match the value assigned to the selected states • The diffusion operator D, which multiplies the amplitude of the |0 n state by −1 Based on the above, the Grover Iterate is now defined is the canonical oracle that, by construction, flips the phases of the selected states, and the Amplitude Amplification routine takes the form of BG j A, where j is the number of times the Grover Iterate is applied.
In this paper, we introduce a new form of this type of generalization, where the operator B prepares a binomial distribution before the application of the simple oracle that marks a given target state. The amplitude of a basis state will depend on the number of 1s in its binary representation, and all states with the same number of 1s in their binary representation will have the same amplitude.

B. Binomial Grover's Search Algorithm
As in the standard Grover's Search algorithm, we assume that all the states in the search space are in equal superposition, created by A = H ⊗n . The operator B converts the uniform superposition to a binomial one, where the basis states with the same number of 1s in their binary representation will have the same amplitude. The set of distinct amplitudes is a geometric sequence.
When starting with a uniform superposition, for a given ω such that 0 ≤ ω ≤ π, the Grover Iterate is defined by: When starting with a binomial superposition, created by A = R ⊗n Y (ω), we have: In both the uniform and binomial cases the following result holds: Theorem 2 (Binomial Amplification). Given an n-qubit quantum system, a target state marked by an oracle O, whose binary representation has a number 0 ≤ k ≤ n of 1s, and an angle 0 ≤ ω ≤ π, the amplitude of the target state after applying the modified amplitude amplification procedure with j ≥ 0 Grover iterations G(ω) is where θ(ω) = arcsin sin k ω 2 cos n−k ω 2 .
Proof. The setup is equivalent to the one described in [1] with A = R ⊗n Y (ω). For a single qubit: Therefore, for n qubits: where k(i) denotes the number of 1s in the binary representation of i, also called the Hamming weight of this representation. Note that all amplitudes are non-negative real numbers. Following the argument in [5], if θ denotes the angle between a non-target state vector and the superposition state vector, then sin(θ) equals the amplitude of the target state.
Compared to the uniform version, which uses a fixed angle θ unif orm , in the binomial version we have a parameterized angle θ(ω) that varies in a range that includes θ unif orm .
For a given 0 ≤ k ≤ n, denote the amplitude of a state whose binary representation contains k 1s before the amplification process by: It is easy to check that, for the range of ω that we are interested in: The amplification process is visualized in Figure 1. The angle between the non-target state vector and the superposition state vector is initially θ(ω), and each Grover iteration increases it by 2θ(ω). The best case scenario is to only perform one iteration and make this angle π/2, corresponding to a measurement probability of 1 for the target state, and it occurs when θ(ω) = π/6 and the initial amplitude is 1 2 . Intuitively, this allows for the following improvements: • Taking θ to be the upper bound of the range leads to a larger amplitude and probability of the target state after the same number of iterations as in the uniform version • We can choose a parameter ω such that θ(ω) is π/2 for a well chosen number of iterations.
Note that when ω = π 2 we retrieve Expression 5: As noted in the uniform version, we can remove the negative sign in the definition of the Grover Iterate, and then Expression 9 changes to: In order to minimize the number of Grover iterations, we are interested in maximizing the angle θ(ω). As mentioned before: a k (ω) ≤ 1 2 . When k = 0 we can attain equality with: When k = n we can again attain equality with: This means that for k = 0 or k = n we only need one Grover iteration to amplify the probability of the target state to 1.
For 0 < k < n, if we look at the critical points of a k (ω), whose derivative with respect to ω is: we find out that in this case: For a balanced outcome k = n − k, we retrieve the angle in standard Grover: We will use the notation θ max = θ(ω max ) to refer to the upper range of θ(ω) in the binomial version of the amplitude amplification process, and θ uniform = arcsin 1 2 n to refer to the angle in the uniform version.
After a number of Grover iterations, the angle between the search non-target state vector and the superposition state vector approaches or surpasses π/2. We are interested in finding this particular number of iterations, and adjust ω in order to make the angle match π/2.
For fixed n and k, the procedure can be broken down into 2 steps: • find j ideal , defined as the minimum j such that (2j + 1)θ max ≥ π/2: and define: θ ideal = π 2(2j ideal + 1) • find ω ideal that satisfies: Applying the binomial version of the amplitude amplification process with j ideal iterations will lead to a measurement probability of 1 for the search target state. Since θ max ≥ θ uniform , the number of iterations j ideal is less than or equal to the number of iterations used in the standard Amplitude Amplification procedure to maximize the amplitude of the search target state.

IV. ADDITIONAL ANALYSIS AND EXAMPLES
In this section we analyze the impact of choosing different partitions and numbers of iterations on the final result. We will denote by n the number of qubits in a quantum system, and by k the number of 1s in the binary representation of a search target state.
In the extreme cases when k = 0 or k = n, the binomial version of the amplification process only needs one iteration.
With the binomial version of the amplitude amplification process, we have seen that for a given 0 ≤ k ≤ n, we can amplify the probability of a state whose binary representation has k 1s to the maximum possible of 1. The amplification takes j ideal iterations. In Table 1, we can see how j ideal compares to j uniform , the best number of iterations in the standard amplitude amplification process, for an 8-qubit circuit.  0  12  1  1  12  3  2  12  7  3  12  11  4  12  12  5  12  11  6  12  7  7  12  3  8 12 1   Given that on current quantum hardware the depth of a circuit with more than 2 or 3 Grover iterations is prohibitive, binomial amplification can provide a clear advantage for certain ks. In this case, we have no choice but to fix the maximum number of iterations. Continuing the example in Table 1, we can see how the probabilities compare in the uniform and binomial versions for a given number of iterations in Fig. 3. As a specific example, consider the case with n = 8 qubits and a target state of 10000001 (the binary representation of 129, containing k = 2 1s), with a limitation of j = 6 Grover iterations. We can calculate θ max from ω max . As seen in Fig. 4, we get a higher probability when compared to the uniform approach. In Sec. V, we show additional examples that handle this constraint.
Another strategy for dealing with the limitation on the number of Grover iterations is to use an adaptive ver- sion [6][7][8][9], where a random number of iterations is applied. The binomial version allows one to also randomly choose the partition to which search target states are assumed to belong.
For the case of multiple search state targets, instead of a single partition, we have to allow for multiple ones. Let us denote by T the set of target states, and k(i) as the Hamming weight (number of 1s in the binary representation) of a state |i . The angle θ between the superposition state vector and the non-target state is given by: Note that for ω = π 4 , we retrieve the multi-target uniform version where θ = arcsin(|T | 1 √ 2 n ).

V. EXPERIMENTAL RESULTS
In this section, we will apply the concepts described in the previous sections to examples of quantum search. Each experiment described in this section was run on real quantum hardware-the Honeywell System Model HØ trapped-ion quantum computer with quantum volume 64 [10,11]-with one execution consisting of 1024 shots. No calibration or noise mitigation was applied.

A. Set Element Search
Let us consider an example of set search using binomial Grover, and compare the results with the uniform approach. In Figure 5 we show a 4-qubit circuit implementing the binomial version of Grover's Search algo-rithm with 1 iteration, where the target state is 1101 (the binary representation of 13). Note that we assume an equal superposition to start, and then convert to a binomial distribution. The rotation angle of R Y is dependent on the number of 1s in the label of the target state, as described in Sec. III B. For 10 out of 16 values we can improve the probability using a binomial approach, at the expense of knowing more information about the search target state. The result of this circuit can be seen in Fig. 6.

B. Array Element Retrieval
In [3], we discuss array search, where we can use a Quantum Dictionary [9,12] to index values by a separate register that holds all indices in superposition. In order to retrieve a value, we need to perform a search on the index register. The classical version of associate arrays uses direct memory access, or hashing, to speedup value retrieval. In quantum computing, amplitude amplification is playing a similar role, using an oracle that will mark a desired index. The type of superposition in the index register will affect the speed of the retrieval. Here we are comparing the performance of a uniform and binomial superposition types in the index register.
As an example, consider a Quantum Dictionary circuit that encodes the partial and total sums of the elements in the array [1, −1, 1]. The encoding of the array using the Quantum Dictionary pattern needs a 3-qubit index register and a 2-qubit value register, that can represent negative values using two's complement. Recall that the Quantum Dictionary pattern encodes the array values as periodic signals, whose interference leads to the sums of all possible subsets. A subset is represented by a binary string in the index register, and the corresponding sum is encoded in the value register.
In Figure 9, we consider the case when the target state is 110, the binary representation of 6. The result of this circuit be seen in Figure 7.

C. Array Element Search
When searching for an array element, we need an oracle that will mark a desired value. We also need to correctly estimate the number of times the Grover Iterate has to be applied, in order to maximize the probability of measuring the desired value. Alternatively, we can use the Grover Adaptive Search [6][7][8] algorithm in order to avoid this estimation. The adaptive approach with a small number of iterations may be the only option in the current era of quantum hardware, where the circuit depth is limited.
Using a binomial superposition in the index register allows for the random amplitude amplification of states based on the Hamming weight of the indices. For example, one can first choose a binomial superposition that will favor the indices with more 1s than 0s in their binary representation, and another that will favor those with less 1s than 0s.
This approach is similar to classical binary search algorithms. As an example, if we have 11 qubits, we can choose the binomial distribution given by ω = 15 32 π. This will actually increase the initial amplitudes of all targets with more 0s than 1s in their binary representation compared to the uniform version, as seen in Table 2 Similarly, if we choose the binomial distribution given by ω = 17 32 π, we maximize the the initial amplitudes of all targets with more 1s than 0s in their binary representation, as seen in Table 3.  A higher or lower amplification can be obtained by adjusting the number of ω parameters, and their values.
We ran both the uniform and binomial versions of array element search on a real quantum computer, as seen in Fig. 8. Here, we are searching for negative values using the same array as in Sec. V B.

VI. CONCLUSION
We have outlined the method of splitting the basis states into partitions and amplifying the amplitudes of the states in each partition in a non-uniform way, before repeatedly applying a Grover Iterate specific to a given search target state. When the partition the target state belongs to is sufficiently amplified, the number of times the Grover Iterate needs to be applied can be reduced.
This method can provide an additional parameter that can be used in optimizing quantum search. In particular, in the adaptive version of Grover's Search algorithm, in addition to varying the number of times the Grover Iterate is applied, one can also vary a level of non-uniform amplitude pre-amplification. We have provided the numerical analysis for the partitioning of basis states based on the number of 1s in their binary distribution, which essentially leads to a binomial distribution for the partition amplitudes.
We have shown how the method can be applied to set search, array element retrieval, and array element search. We have also successfully validated the results on a real quantum computer, and we believe these to be one of the earliest successful quantum search experiments on 4 and 5 qubits using a quantum computer.