## 3 The Two Search Algorithms
### Search for the Existence of a String or String-Fragment in an Unknown, Unsorted Superposition  
Here, we again suppose that in the \(M\)-bit INBL system, the unknown and unsorted superposition consists of an arbitrary sum of \(M\)-long product-strings. This method is the generalization of the scheme described in Section 2.1. It is exponentially, \(\frac{2^{M}}{M}\), faster than known classical alternatives, and \(\frac{2^{M}}{M!^{5}}\) faster than [PERSON]'s for the problems in this section. We note that with a suitably complex oracle, [PERSON]'s algorithm can be applied to other problems outside the scope of the method presented here. _Method_:  
The whole search process is carried out during a clock period \(t\) when the original superposition is non-zero, \(S(t)\
eq 0\). (I) Ground the reference wires of the inverse bit values of the search term;  
(II) Check if the remaining superposition is non-zero. If it is nonzero, the search string or string fractions exist in the superposition. _Example-1, full string search_: Suppose that \(M=4\) and the job is to find out if the \(1(1),0(2),1(3),0(4)\) string (represented by the \(R_{11}(t)R_{20}(t)R_{31}(t)R_{40}(t)\) product) is an element of the otherwise unknown superposition \(S(t)\). Let us assume that the superposition is  
\[S(t)\ =\ R_{11}(t)R_{20}(t)R_{31}(t)R_{40}(t)+R_{10}(t)R_{20}(t)R_{31}(t)R_{40}( t)+R_{10}(t)R_{21}(t)R_{31}(t)R_{40}(t). \tag{9}\]  
The inverse of the \(1(1),0(2),1(3),0(4)\) string is \(0(1),1(2),0(3),1(4)\); therefore, we ground the corresponding reference wires, see Figure 8:  
\[R_{10}(t)\ =\ 0;\ R_{21}(t)\ =\ 0;\ R_{30}(t)\ =\ 0;\ R_{41}(t)\ =\ 0. \tag{10}\]  
In any of the other possible \(M\)-long strings in the \(M\)-bit system, at least one of the reference noises listed in Equation (10) will be present. That means that only the search string is non-zero, and if the remaining superposition is non-zero, such as in this case, the search string is present in the superposition. The operation requires \(M=4\) switching operations; thus, the time complexity is O(\(M\)) = 4. The maximum size of the superposition is \(2^{M}\) = 16. The speedup is \(2^{M}/M\ =\ 4\). _Example-2, string fragment search with single string result_: Search for the \(0(1),0(2),\ \text{AND}\ 0(4)\) string fragments in the superposition. The inverse bit values are \(1(1),1(2),1(4)\); therefore we ground the corresponding reference wires:  
\[R_{11}(t)\ =\ 0;\ R_{21}(t)\ =\ 0;\ R_{41}(t)\ =\ 0 \tag{11}\]  
The superposition in Equation (9) will be non-zero (because of the second term) indicating the simultaneous existence of the searched string fragments within at least one of the strings. _Example-3, string fragment search with superposition result_: Search for the same, \(0(1),0(2),\ \text{AND}\ 0(4)\), string fragments in this modified superposition:  
\[\begin{array}{l}S^{\prime}(t)\ =\ R_{11}(t)R_{20}(t)R_{31}(t)R_{40}(t)+R_{10}(t)R_ {20}(t)R_{31}(t)R_{40}(t)+\\ \Search for the existence of the string-fragment that is identical to \(N_{i}(t)\), that is, ground the reference wires of the inverse bit values of \(N_{i}(t)\). Then the \(S_{\text{PB}}(t)\) original superposition wave collapses into the single string, the \(B_{i}(t)\ =\ N_{i}(t)S_{i}(t)\) product. This operation requires \(N\) switching operations (\(N\) groundings). Then, while keeping those \(N\) references wires grounded, ground _one by one_ the \(2S\) reference wires of the phone number database and record which bit value groundings result in \(B_{i}(t)\ =\ 0\). These bit values constitute the phone number string \(S_{i}(t)\). The time and hardware complexity of this search algorithm is \(\text{O}\big{[}\log_{2}n+2S\big{]}\) in general, where \(n\) is the size of the database and \(S\) is the bit resolution of the phone numbers and it is \(\text{O}\big{[}3\log_{2}n\big{]}\) when \(S\ =\ \log_{2}s\). In the case of one-to-one correspondence between the names and phone numbers (\(n=s\)), the algorithm obviously offers inverse phonebook search, too.