Читать книгу Quantum Computing - Hafiz Md. Hasan Babu - Страница 24

There are two important properties to define a quantum gate which are as follows.

Property 3.1. Each quantum gate has an unique unitary matrix. A complex square matrix U is unitary only if

U*U=UU*=I,

where I is the identity matrix and U^* is the conjugate transpose of U.

Property 3.2. A quantum state is represented by a state vector in a Hilbert space over complex numbers.

The matrices for the controlled-E and controlled-E⁺ gates are

Mcontrolled‐E=−i/2−i/2−i/2i/2;Mcontrolled‐E+=i/2i/2i/2−i/2.

The conjugate transpose of Mcontrolled‐E is Mcontrolled‐E+ and vice versa. After multiplying Mcontrolled‐E and Mcontrolled‐E+, we obtain an identity matrix which is

Mcontrolled‐E×Mcontrolled‐E+=−i/2−i/2−i/2i/2×i/2i/2i/2−i/2=1001=I.

The controlled-E and controlled-E⁺ gates have a unique matrix which is unitary. Figures 3.2(a) and (b) show the diagrams of the controlled-E and controlled-E⁺ gates.

Figure 3.2. Controlled gate. (a) Controlled-E⁺ gate. (b) Controlled-E gate.

The matrices for the XN (MXN) gate and its conjugate transpose (MXN*) are

MXN=0100100000100001MXN*=0100100000100001.

After multiplying MXN and MXN*, we obtain an identity matrix which is

MXN×MXN*=0100100000100001×0100100000100001=1000010000100001=I.

Thus the XN gate has a unique matrix which is unitary. Figure 3.3 shows the diagram of the XN gate.

Figure 3.3. The XN gate.

Algorithm 3.1 describes the computational process for the designed method for the proof of the time complexity. The technique of comparison of the comparator has four basic steps. First, sort the two numbers and also calculate their middle bit position. Second, find Ex-OR of the middle bit position and decide based on that value whether to go to the left half or to the right half of the numbers. Third, repeat the second step after entering into the left or right half and also calculate Ex-OR of the other bits at the same time. Finally, take a decision if any value of Ex-OR is ∣1〉 as to which number is greater, otherwise carry out Ex-NOR to find whether they are equal or not.

Property 3.3. Algorithm for the comparison technique for an n quantum bit string comparator which requires a time complexity of O(2(2+logn)).

Proof. Let n be the number of qubits of two strings. To sort two strings of n qubits in parallel using merge sorting, the 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.