Home > issue 5 > The Essence of Quantum Computing

The Essence of Quantum Computing Part 2 of 3 Part Series It can be shown that the function so defined is a well-defined inner product. From this inner product, the inner product space V⊗W inherits other familiar structures, such as notions of adjoint, unitarity43, normality, and Hermiticity.

A.5.7 Congruence Modulo

The expression a ≡ b mod m is read as “a is congruent to b modulo m.” Let m ≠ 0 be an integer. We say two integers a and b are congruent modulo m if there is an integer k such that a-b = km, i.e., (a-b)/m is an integer. A familiar example of this form of arithmetic is the clock. Clocks use modular arithmetic with modulus 12 for displaying hours (as there are 12 hours on the clock face), and modulus 60 for displaying minutes (as there are 60 minutes in an hour).

Note that here the symbol ‘≡’ is not equality but congruence44, and the ‘mod m’ signifies the number by which b must be divided to get k and the remainder a. The remainders can be 0, 1, 2,… , m-1. Integer numbers thus get classified into m residue classes (also called congruence classes) labelled, respectively, by the remainders 0, 1, 2,… , m-1. For m = 2, the classes are:

 = {…, 4, 2, 0, 2, 4, …}
 = {…, 3, 1, 1, 3, 5, …}

Modulo arithmetic is done, digit by digit, on binary numbers. Each digit is considered independent of its neighbors. Numbers are not carried or borrowed.

0 + 0 ≡ 0 (mod 2),   0 + 1 ≡ 1 (mod 2),   1 + 0 ≡ 1 (mod 2),   1 + 1 ≡ 0 (mod 2).

In modulo 2 arithmetic, the addition operation is the XOR (or Cnot) operation. It is carried out on the corresponding binary digits of each operand according to the following rule: The above rules may also be interpreted as “the sum of even numbers is even”, “the sum of an even number and an odd number is odd”, “the sum of an odd number and an even number is odd”, and “the sum of two odd numbers is even”, respectively, in modulo 2 arithmetic.

The following multiplication rules for multiplying two binary numbers are also obvious:

0 x 0 ≡ 0 (mod 2),      0 x 1 ≡ 0 (mod 2),      1 x 0 ≡ 0 (mod 2),      1 x 1 ≡ 1 (mod 2).

In modulo 2 arithmetic, the multiplication operation is the Boolean AND operation45:

0 ^ 0 = 0,      0 ^ 1 = 0,      1 ^ 0 = 0,      1 ^ 1 = 1.

Thus, we have a system with addition and multiplication, but in which the only numbers that can exist are 0 and 1.

43 A n×n matrix U is unitary if U†U = UU† = I, where I is the unit matrix. This condition means that U is unitary if and only if it has an inverse which is equal to its conjugate transpose U†.
44 Coinciding exactly when the remainders are compared.
45 The symbol ∧ represents the word “AND”.

Pages ( 13 of 14 ): « Previous1 ... 1112 13 14Next »