T(n)=T(∣n/2∣)+1,
where T(n) denotes the run time of the comparison technique, T(∣n/2∣) is the time required to perform an operation on the left/right half of the n-qubit strings, n is the length of the qubit strings, and a constant 1 (one) is the time for midpoint qubit operation of the qubit string.
Algorithm 3.1 Algorithm of the comparison technique.
| INPUT: INPUT: Two n-qubit strings ∣A〉 = ∣An〉∣An−1〉 ⋯ ∣A0〉 and ∣B〉 = ∣Bn〉∣Bn−1〉 ⋯ ∣B0〉 |
| OUTPUT: ∣A〉 > ∣B〉 or ∣A〉 < ∣B〉 or ∣A〉 = ∣B〉 |
| 1: Begin |
| 2: ∣A[i]〉 = array containing n qubits of the first string |
| 3: ∣B[i]〉 = array containing n qubits of the second string |
| 4: ∣SA[i]〉 = sorted ∣A[i]〉 |
| 5: ∣SB[i]〉 = sorted ∣B[i]〉 |
| 6: n = size of array |
| 7: mid=∣n2∣ |
| 8: Ex‐OR[mid]=∣SA[mid]⟩⊕∣SB[mid]⟩ |
| 9: If .Ex-OR[mid] = 0 then |
| 10: Find Ex-OR values of the left half of ∣SA[i]〉 and ∣SB[i]〉 s.t.i < mid |
| 11: If Ex-OR of the left side ∣SA[i]〉 and ∣SB[i]〉 is 0 then |
| 12: Find Ex-OR values of the left half of ∣A[i]〉 and ∣B[i]〉 s.t.i < mid |
| 13: If Ex-OR of any position is 1 and ∣A[i]〉 > ∣B[i]〉, then |
| 14: ∣A〉 > ∣B〉 |
| 15: Else If Ex-OR of any position is 1 and ∣A[i]〉 < ∣B[i]〉, then |
| 16: ∣B〉 > ∣A〉 |
| 17: Else goto Step 19 |
| 18: End If |
| 19: Repeat Steps 12 to 16 for right side, i.e. mid < i < = n |
| 20: Else goto Step 26 |
| 21: End If |
| 22: End If |
| 23: Else |
| 24: Repeat Steps 10–20 for the right half of the numbers ∣SA[i]〉 and ∣SB[i]〉 s.t.i > mid |
| 25: End Else |
| 26: If Ex-NOR of both halves of ∣A[i]〉 and ∣B[i]〉 is 1, where ∣SA[mid]⟩⊕∣SB[mid]⟩ = 0, then |
| 27: ∣A〉 = ∣B〉 |
| 28: End If |
| 29: End |
Guess
It is assumed that the solution of the recurrence is T(n) = O(logn), i.e. it is true iff T(n) ⩽ c(log(n)), where c > 0 is a constant.
Proof by substitution. Assume that this bound holds for all positive m < n in the particular m = [n/2], where n is the number of qubits and m is a constant term. It yields that
T(n/2)⩽c(log(∣n/2∣)).
By substituting into the recurrence, we obtain
T(n)⩽c(log(∣n/2∣))+1=c(log(n))−c(log(2))+1=c(log(n))−c+1⩽c(log(n))aslongasc⩾1.
Thus, T(n)⩽c(log(n)), that is, T(n)=O(logn). Therefore, the total time complexity of the comparison algorithm in the best case is sorting time + comparison time + array of position access time + array of unsorted qubits access time
=O(logn)+O(logn)+O(2)+O(2)=O(2(2+logn)).
Thus this completes the proof and property 3.3 is true.
The design of a quantum comparator consists of two circuits: the midpoint qubit comparison (MQC) circuit and the rest qubit comparison (RQC) circuit. First, the most significant quantum bits using the MQC circuit are compared. Second, the rest of the qubits using the RQC circuit are compared, where each qubit comparison is performed by one RQC circuit. In figure 3.4, the MQC circuit consists of two controlled-E gates, one controlled-E+ gate, three CNOT gates, and one XN gate. This circuit generates the following three outputs as presented in equation (3.1) and produces one garbage output which is ∣g1〉:
∣En/2〉=∣An/2〉⊙∣Bn/2〉∣Gn/2〉=∣An/2Bn/2¯∣Ln/2〉=∣An/2¯Bn/2〉.(3.1)
Figure 3.4. The MQC circuit. Reproduced with permission from [2]. Copyright 2017 IEEE.
In figure 3.5, the RQC circuit consists of four controlled-E gates, three controlled-E+ gates, one XN gate, and eight CNOT gates. This circuit generates three outputs, as presented in equation (3.2). It also produces two garbage outputs which are ∣g1〉 and ∣g2〉:
∣AGBn/2−1〉=∣Gn/2〉+∣En/2〉.∣An/2−1Bn/2−1¯〉∣ALBn/2−1〉=∣Ln/2∣En/2〉.∣An/2−1¯Bn/2−1〉∣AEBn/2−1〉=∣AGBn/2−1〉⊙∣ALBn/2−1〉.(3.2)
Figure 3.5. The RQC circuit. Reproduced with permission from [2]. Copyright 2017 IEEE.
3.3.1 Example
To construct a two-qubit quantum comparator circuit, one MQC circuit and one RQC circuit are needed to perform the greater than, less than, and equality operations. In figure