Quantum Computing. Hafiz Md. Hasan Babu
Читать онлайн книгу.
total time complexity in the best case is O(logn). Each string is divided into half (n/2) of the original string when the comparison technique works in each time. Thus it reduces the working space by half. In the worst case, the comparison technique operations need to be executed on both the left and right halves of the two n-qubit strings, where the time required for one half is the run time (T(∣n/2∣)) for half (n/2) of the n-qubit string using the comparison technique, and the time required for the other half is the same time which is treated as the time for copying the same operations in the other half of the string. In contrast, in the best case only the left/right half operations need to be executed. The positions of the qubit strings are stored in two different arrays. When comparing two qubits, the two arrays containing the qubit positions need to be accessed in parallel and the complexity of an array access is O(1). According to the algorithm, Ex-OR of midpoint of the sorted strings is performed and depending on the result, the left/right half of the unsorted strings is used for comparison. Hence we need to access the two unsorted array of strings again and this also has time complexities. Thus the recurrence of the comparison technique in the best case can be specified as
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