Chapter 20

Introduction to Quantum Computing

If you do not expect the unexpected, you will not find it.

—Heraclitus

20.1  INTRODUCTION

All modern day computers use two-state binary logic in data processing (or information processing). The size of the modern day computers (we shall call these as classical computers, as their size is macroscopic) is decreasing day-by-day at the rate predicted by Moore. Moore’s law may be stated in various forms:

1. The computing power will double for constant cost roughly every two years.
2. The number of components (transistors) in silicon ICs will roughly double every two years.
3. Minimum feature size of an IC chip halves roughly every two years.
4. The computer size halves roughly every two years.

So at this exponential speed, it will not be long before we may have extremely small sized computing devices. And with that extremely small size of computing devices, the components will be still smaller, may be of nano-size. The laws of classical mechanics may not be valid at such extremely small sizes. Therefore, we cannot go beyond a certain limit (without invoking laws of quantum mechanics in the process of computing).

In fact, well before arising such a situation, Feynman way back in 1982 suggested shifting to a completely different theoretical framework of computing that uses laws of quantum mechanics throughout. Feynman noted that quantum systems may not be efficiently simulated on a classical computer. He hypothesized that it might be possible to simulate quantum systems more efficiently, if the simulator (i.e. the computer) was itself quantum mechanical in nature. The suggestion led to a lot of rethinking about the basic models of computation and the physics behind the computation. A number of physicists suggested the possibility of using the dynamics of quantum systems to perform computation in a more efficient way. Soon, a concrete mathematical model—a quantum Turing machine, and quantum circuits (quantum logic gates)—was proposed by some physicists; thus laying the foundation of quantum computation. In fact, quantum computation is seen as a formulation for future quantum computers.

We shall introduce the readers to quantum computation in this chapter. But, firstly, we shall discuss the preliminaries of classical computation: binary number systems, (classical) logic gates, and Turing machine. We shall, then, introduce quantum bits (qubits) and quantum logic gates.

20.2  BINARY NUMBER SYSTEMS

It is very useful to work in the binary number system in context with computation which uses electronic logic circuits (logic gates). In electronic logic gates, the number 0 and 1 relate to two separate voltage levels. Typically the number 0 corresponds to a voltage near zero and the number 1 to a voltage near 5 volts. In binary code, either of these two different states (of logic gates), represented by a zero and one, is called a bit. Before discussing the details of classical logic gates and their operations on bits, we discuss, briefly, the construction of binary numbers.

20.2.1  Construction of Binary Numbers

In the decimal number system, the base is 10 and positions of numbers in the sequence represent powers of 10, while the coefficients run from 0 to 9. It will become clear in the following example:

 

 

On the other hand, in the binary number system, the base is 2, and positions of numbers in the sequence represent powers of 2, while the coefficients are 0 and 1 only. For example, the binary representation of few numbers, say 5, 10, 25.5 are

 

 

1. A method of converting the decimal number system greater than one to the binary number system: Let the number be 131. This number may be converted in the binary representation by the following sequence of divisions by 2.

   Step 1:	with remainder 1.
   This reminder 1 is the entry to the far right of binary representation of 131. Repeating the division by 2 in following way,
   Step 2:	with remainder 1
   Step 3:	with remainder 0
   Step 4:	with remainder 0
   Step 5:	with remainder 0
   Step 6:	with remainder 0
   Step 7:	with remainder 0
   Step 8:	with remainder 1

   we get

   131 = 10000011

    

   One may notice that to write a number x in binary code, one will require log₂x number of bits (i.e. number of 0 s and 1s). In the language of computer, the number of bits needed to store the value of x is log₂x.

2. A method of converting the decimal number system less than one to the binary number system: Let the number be 0.4.

   Step 1:	Carrying a multiplication by 2 0.4 × 2 = 0.8    0
   The 0 (before decimal) in the above expression gives the first number (after decimal) in binary representation of 0.4.
   Step 2:	0.8 × 2 = 1.6    1
   Step 3:	Change 1.6 to 0.6 and repeat the process 0.6 × 2 = 1.2   1
   Step 4:	0.2 × 2 = 0.4   0
   Step 5:	0.4 × 2 = 0.8   0
   Step 6:	0.8 × 2 = 1.6   1
   Step 7:	0.6 × 2 = 1.2   1
   so
   	0.4 = 0.0110011 = 0 × 2–1 + 1 × 2–2 + 1 × 2–3 + 0 × 2–4 × 0 × 2–5 + 1 × 2–6 + 1 × 2–7 = 0.3984375

20.2.2  Measure of Information

It is very important in information theory to obtain a measure of information, that is, the amount of information. Suppose your friend tells you the value of a number X as 4. How much information you have got? Answer to this question depends on what you already knew about X. For example, if you already knew X was equal to 4, you have got no information from your friend in this context. On the other hand if you only knew that X has an integral value in between 1 and 10, then to learn its value is to gain information. In fact, we may say that amount of information is a measure of ignorance. Let us consider a random variable X, such that it has value x with probability p(x). In this case, the information content of X is defined to be

We can easily see that S is always positive since probabilities p(x) are less than unity. The standard practice is to use symbol S(X) for S {[p(x)]}. S(X) merely means the information content of the variable X [and S(X) does not mean a function of X]. The quantity S(X) is sometimes referred to as entropy (e.g. in statistical mechanics).

Let us evaluate the information content S(X) in some particular cases.

Example 1   If X is given by the toss of a coin, then for x ∊ [head, tail]. So

Example 2   If X is given by the throw of a symmetric dice, then for x ∊ [1, 2, 3, 4, 5, 6]. So

Example 3   If X can take N different values with equal probability [p(x) = (l / N)], then

 

One observes that the maximum information which could be stored by a variable X, which may take on N different values is S(X) = log₂ N. When variable X takes two values with equal probability (Example 1), we have S(X) = 1. this may be taken as fundamental unit of information. So a two-valued variable or binary variable may contain one unit of information. This unit is called a bit. In binary code it is equal to either 0 or 1. Eight bits comprise a byte.

The two values of the variable X are written as 0 and 1. In this case of binary variable, if we define p to be the probability that X = 1, then the probability is (1 – p) for X = 0, and the information may be written as a function of p alone:

 

20.3  CLASSICAL LOGIC GATES

20.3.1  Digital Electronics and Logic Gates

Let us consider two forms of time-dependent voltages in a circuit, as shown in Figure 20.1a and b. In Figure 20.1a, there is a continuous range of values of voltages—called as analog signal. The electronic circuits using analog signals are called analog circuits. In Figure 20.1b, the voltage is in a pulse waveform, where only discrete values of voltages are possible.

The high level is termed as ‘1’ and low level as ‘0’ (see Figure 20.2). The two levels of a signal may be used to represent the binary digits 0 and 1 (called bits). The digital electronics process the 0 and 1 level signals in a specific manner. Logic gates are the basic building blocks of the digital electronics.

The electronic circuit of a logic gate has one or more input terminals and an output terminal. A potential of zero denotes the logical value 0 and a fixed potential V (say ~ + 5V) denotes the logical value 1. Here we describe the structure and functioning of various gates.

20.3.2  Structure and Functioning of Various Gates

1. OR Gate: An OR gate has two or more inputs and one output. An OR gate with two inputs A and B and an output X is constructed with two p-n junction diodes D₁ and D₂ (Figure 20.3). The circuit evaluates the function X = A OR B, i.e. X = A + B. For two input OR gate, we have following four different cases.

Figure 20.1 (a) Continuous signal (analog signal) (b) Pulse signal (digital signal)

Figure 20.2 Range of voltages corresponding to level ‘0’ and level ‘1’

1. A = 0, B = 0: There is no potential difference anywhere in the circuit so X = 0.
2. A = 0, B = 1: The potential is zero at A and is 5V at B. The diode D₂ is forward biased and conducts. Thus the potential at X is same as that at B. So X = 1.
3. A = 1, B = 0: Now D₁ conducts and X = 1.
4. A = 1, B = 1: Both the diodes D₁ and D₂ will conduct and potential and X is same as that at A and B, i.e. 5V. So X = 1.

Figure 20.3 (a) Realization of two input OR gate with p-n diodes D₁ and D₂ (b) Symbol for OR gate

Thus circuit gives X as 1 when input A or B or both are 1 and gives X as 0 when both A and B are 0. This statement can also be given in the form of truth table given as follows:

 

A	B	X = A OR B = A + B
0	0	0
0	1	1
1	0	1
1	1	1

2. AND Gate: In a two input AND gate, the output X is 1 if both the inputs A and B have state 1 (Figure 20.4). So we have following four different cases.

1. A = 0, B = 0: the potentials at A and B are zero so both the diodes D₁ and D₂ are forward biased (nearly short circuiting). The potential at X is same as that at A or B. So X = 0.
2. A = 0, B = 1: The diode D₁ provides a short circuit i.e. the low resistance path, so potential at X is same at that at A. So X = 0.
3. A = 1, B = 0: Now D₂ provides short circuit, so X = 0.
4. A = 1, B = 1: None of the diodes D₁ and D₂ would conduct as potentials at both A and B are 5V. As there will be no current through R, so voltage drops across R and the potential at X will be 5V. So X = l.

Figure 20.4 (a) Two inputs AND gate with diodes D₁ and D₂ (b) Symbol for AND gate

 

A	B	X = A AND B = A · B
0	0	0
0	1	0
1	0	0
1	1	1

3. NOT Gate: It is a single input (A) and single output (X) gate. If the input is 1 the output is 0 and vice-versa. The truth table is given below.

 

A	X = NOT A = Ā
0	1
1	0

A NOT gate cannot be realized with diodes. For realizing this, we have to use a simple transistor inverter circuit shown in Figure 20.5. Let us firstly take the case A = 0. In this case the emitter–base junction is unbiased, so no current through it. As a result there is no current through the resistance. R_c. Under this condition the potential at X is same as that at positive terminal of the battery, i.e. 5V. So if A = 0, we get X = 1. Let us next take the case when potential A is 5V. In this situation the base–emitter junction is forward biased. So there is large current in the circuit; the direction of current is from base to emitter i.e. from right to left in resistance R_c. The whole potential, thus, drops across R_c and the potential X is zero. So if A = 1, we get X = 0.

Figure 20.5 (a) Realization of NOT gate through transistor inverter circuit (b) Symbol for NOT gate

Figure 20.6 NAND gate

4. NAND Gate: With two inputs A and B, the output function X = NOT (A AND B) is called NAND function. It is written as X = A NAND B = . A NAND gate can be realized by an AND gate followed by a NOT gate, as shown in Figure 20.6. The truth table is given below:

5. NOR gate: For inputs A and B, the function X = NOT (A OR B) is called a NOR function. It is written as X = A NOR B = . A NOR gate can be realized by an OR gate followed by a NOT gate, as shown in Figure 20.7. The truth table is given below:

A	B
0	0	1
0	1	0
1	0	0
1	1	0

Figure 20.7 NOR gate

6. XOR gate: The exclusive OR gate is labeled as XOR gate. For inputs A and B, the output X of this gate is 1 if one of two inputs is 0 and the other is 1. If both the inputs are 0 or both are 1, X is 0. The symbol for an XOR operative is ⊕ which designates addition mod (2). The truth table is given below:

 

A	B	X = A ⊕ B
0	0	0
0	1	1
1	0	1
1	1	0

20.4  TURING MACHINE

Turing machine is a powerful abstract model of computing device. This model is believed to do everything that a real computer can do. There are four basic elements of a Turing machine (illustrated in Figure 20.8).

Figure 20.8 Basic elements of single tape Turing machine

1. A Program
2. A Finite State Control, consisting of a finite set of internal states q₁, q₂, … q_m and acting like a microprocessor. The operation of Turing machine is determined by the primitive program. The finite state control is always in one of the states q₁, … q_m, which can be regarded as positions in a program. In addition to the states (q₁, … q_m), there are also two special internal states labeled as q_s and q_h, which represent the starting state and halting state, respectively.
3. A tape, is a one-dimensional object that extends to infinite to the right. The tape is marked off into cells, each of which holds one of a finite number of tape symbols. The cell is scanned by a read–write head.
4. A read–write tape head, connecting to the position of the tape which is currently readable. The read-write head can move both to the left and to the right.

Each cell on the tape contains a symbol drawn from symbol Γ. The cell on the left edge of the tape has symbol ▷. All other cells contain one of the symbols 0, 1, b; b denotes a blank space. The operation of the machine starts with the finite state control being in a given state and the read–write head being at the left-edge cell. The machine then proceeds according to the given program, step-by-step. The program is really a finite ordered list of program-lines of the form (q, x, q′, x′, s). The first parameter q in the program line represents a state from the internal state of the machine. The second parameter x is taken from the alphabet symbol Γ, which appear on the cells of the tape. The program works in such a way that in each cycle of the machine, the Turing machine searches for a program line containing (q, x), i.e. searches for a line like (q, x, ·, ·, ·). Here q and x, respectively, show the current internal state of the machine and the symbol being read on the tape. In case such a program line is not found, the machine halts operation as in this case the internal state of the machine is changed to q_h. However, if the said program line is found, the program line is executed in following steps:

1. The internal state of the machine is changed to, say, q′.
2. The symbol x on the cell is overwritten, say, by symbol x′.
3. The tape-head moves left, right or stands still depending on whether s is –1, +1 or 0, respectively. Only when the tape-head is at the left most cell of the tape and s = –1, the tape-head does not move.

These steps of Turing machine are used to compute a function. The importance of the Turing machine in computing lies in the Church–Turing theorem: Any Algorithmic process can be simulated efficiently using a Turing machine.

20.5  QUBITS

Qubit stands for quantum binary digit. Qubit is the elementary unit of quantum information, just like a bit is elementary unit of classical information. In fact, qubit may be considered as a unit vector in a two-dimensional linear vector space. For example (i) state of polarization of a photon, (ii) state of an electron in an atom with just two energy levels (iii) state of spin of an electron (which we shall take in the present discussion). In Chapter 12, we had seen that the spin eigenstates of an electron and [or and , or and ] form the basis unit vectors in the two-dimensional spin linear vector space. Therefore the quantum (spin) state of an electron (i.e. the basis state or ) may be taken as a qubit (just like a classical bit 0 or 1 represents a specific voltage threshold). However, there is a fundamental difference between the qubits (as unit vectors and ) and bits (as 0 and 1). Whereas in case of bits, there is no significance of the linear combination of bits 0 and 1 (a.0 + b.1), in case of qubits, the linear combination of unit vectors or is also a unit vector in the same vector space and therefore is a qubit.

If a measurement is done on an electron in spin state (say using the Stern–Gerlach experiment), the electron is found only in one of the (spin up or spin down ) states with probabilities |a|² and |b|², respectively. This is the famous quantum phenomenon of collapse of the wave function upon measurement. Therefore when a measurement is made on a qubit, represented by the normalized quantum state the qubit is found to be or with probability |a|² and |b|², respectively (|a|² + |b|² = 1). Once measured, the qubit continues to remain in the state measured. If we consider an ensemble of N identical qubits, each in same state , the measurement on all qubits shall give N |a|² number of qubits in state and N |b|² number in state .

We know, in classical case, the NOT gate changes the bit 0 to 1 and vice-versa. The OR gate gives output 0 if the two input bits are 0 each. The OR gate gives output 1 if at least one of the two input bits is 1. In classical case we know about the electronic circulatory for the logic gates operating as NOT and OR etc. In quantum case if we want to have, for example, a NOT gate (whose purpose is to change the basis state to and vice-versa), we shall have to seek a linear operator (2 × 2 matrix) in the corresponding two-dimensional linear vector space. Similarly the (quantum) gate corresponding to OR gate of classical case, should also be a linear operator (2 × 2 matrix) in the said vector space. We shall discuss about linear operators working as quantum gates on qubits in Section 20.7. But firstly we discuss multiple qubit system.

20.5.1  Multiple Qubit Systems

Let us consider two quantum systems with their basis states as and When these two systems are considered as a single combined system, the resultant state space (of the combined system) is obtained through the tensor product, resulting in the basis set of states.

Thus, if two state spaces of dimensions m and n combine through the tensor product, the resultant space has dimensions mn (for details see Section 7.8). As an example consider two electrons, each in same two-dimensional basis state Then there are 2² = 4 basis states of the two electron system; we may write these as

or simply as

or in further simplified notations as

The four basis states may also be written in the column matrix form, realizing that and

These two electrons may also exist in a state which is linear superposition of the four bases states like in state , defined as

20.6  ENTANGLEMENT

Let us consider a 2-qubit state, known as the EPR singlet pair,

The state may be obtained from state of Eq. (20.9e) for a₁ = a₄ = 0, a₂ = –a₃ = Let us see if this state can be expressed as a tensor product of two single qubit states. We have,

One may note that for no values of a’s and b’s can this expression be written in the EPR pair form, [Eq. (20.10)] Such states which can not be split into separate single qubit states are called entangled states. One may write other 2-qubit entangled states as well. For example, one may easily check that the 2-qubit state

is an entangled state. Also, there may be, in general a number of n-qubit entangled states. These entangled states (of the combined system) can not be specified by specifying the states of the constituent systems. The presence of entangled states is a consequence of the principle of linear superposition of basis states: a purely quantum mechanical phenomenon. Therefore the systems with entangled states have no analogue in the macroscopic world where we know the description of any system may be broken down into that of its parts.

Let us see more carefully what happens when a measurement is made on the bits of an entangled state.

Example 1   Let us consider the entangled state of the EPR pair.

which specifies that the 2-qubit state is a superposition of two states: and where in state the first qubit is in state and second qubit in state, while in state , first qubit is in state and second one in state . When a measurement is made on, say, first qubit and we find it in state , we know for definite the state of second qubit is . So a measurement on one qubit determines completely the state of the other qubit. This property is called maximum entanglement.

Example 2   Let us consider an entangled state

Let the first qubit be measured and found to be . The probability of measurement of the second qubit as changes from (before the measurement on first qubit) to (after the measurement on first qubit), as seen below.

Before the measurement on first qubit, the state of the 2-qubit system is The probability of measurement of the second qubit as is . Now after the first qubit measured as , the state of the 2-qubit system collapses to (Remember, after the measurement process, the amplitudes change abruptly and the changed state is again normalized). Now the probability of measurement (on state ) of the second qubit as is obviously .

Example 2 is the case of partial entanglement. So, entangled states may also be defined as those states in which the measurement of one qubit changes the results of measurements of the other qubits.

20.7  QUANTUM LOGIC GATES

In case of classical computer, the gates operate on bits and transform them. There are electronic circuits for all gates. For example there is a particular electronic circuit which works as a NOT gate and changes the state 0 to 1 and 1 to 0. Now we proceed to seek the gates in quantum case. In case of qubits, we would like to have (quantum) gates which transform qubits, i.e. we should have transformation of quantum system from one state to the other state as an action of quantum gates. And we know the dynamics of quantum system is governed by the Schrodinger equation. In this transformation of states, dictated by the Schrodinger equation, the set of basis states remains unchanged (and remains orthonormal) throughout. Since a quantum state is linear superposition of basis states, any linear transformation of the quantum state, really, does not alter basis states; only changes the coefficients of basis states. Such linear transformations (which preserve the orthonormal basis states) are called unitary transformations (for details see Chapter 7). Therefore the quantum gates are unitary operators.

20.7.1  Single Qubit Gates

We know, there is only one classical single-bit gate: the NOT gate, which flips the state (changes 0 to 1 and 1 to 0). The classical gate is deterministic. In quantum computing the analogue of classical bits are quantum bits, the qubits, which are really the quantum states of a system, as discussed in Section 20.5. Now if we want to transform a quantum state [i.e. a state vector, say, or ], we shall have to have a transformation operator which transforms state to some other state (say ). We know from our experience in quantum mechanics that the said transformation operator has to be a 2 × 2 matrix operating on the state in 2-dimensional vector space. As a trial, let us take the matrix Then we have

and

So the operator transforms to and to Obviously is playing same role in quantum case as NOT gate plays in classical case. So is termed as quantum NOT gate and is, generally, denoted by Below we write some simple single-qubit gates and their operations:

1. Identity gate,
   
2. NOT gate,
   
3. Phase shift gate,
   
4. Combination of NOT and phase shift gate,
   
5. Hadamard gate,

It may be noted here that all the matrices and Ĥ are unitary and, therefore, we say all these single qubit gates work as unitary operators resulting in unitary transformations of (qubit) states.

If we consider a single-qubit in state then the above mentioned single qubit gates have following operations on this qubit;

20.7.2  Two-qubit Gates: Controlled Operations

One of the most useful operations in computing is the controlled operation of quantum gates. It can be stated as “If A is true, then do B”. The most important of the two-qubit gate, in this category, is CNOT (controlled NOT) gate. CNOT flips the second qubit (known as target qubit) if the first qubit (known as control qubit) is , otherwise leaves the second qubit unchanged. This operation of CNOT may be summarized as:

The CNOT operation may also be shown graphically as follows:

Here top line represents the control qubit and the bottom line the target qubit. More generally, if we take as an arbitrary single qubit unitary operator, then controlled gate is a two-qubit operation, with a control qubit and a target qubit. Just like CNOT, if the control qubit is then is applied to the target qubit, otherwise the target qubit is left as such. The controlled operation may be shown as follows:

Here again top line represents the control qubit and the bottom line the target qubit. The CNOT operation shown in Eq. (20.17) may be applied to four different cases as follows:

20.7.3  Reversibility and Irreversibility of Gates

We note the classical NOT gate is a reversible gate. However, classical AND, OR, NAND and NOR are irreversible gates. Consider, for example the AND gate. It takes as input two bits and gives a single bit as output. Given the output of the gate, it is not possible to get information about the input uniquely; that is why AND gate is irreversible. The NOT is a reversible gate because given the output of the NOT gate, it is possible to find the input uniquely.

We see that irreversibility is connected with the information loss. In an irreversible logic gate, some of the information input to the gate is lost, when the gate operates. Conversely, we may say that in a reversible computation process, no information is lost during the process of computation. Now there is an intimate connection between the energy consumption and irreversibility in computation. Landauer’s principle speaks about the connection. According to Landauer’s principle, if a computer erases a single bit of information, the amount of energy lost to the environment is at least kT log_e 2 (where k is the Boltzmann’s constant and T is the temperature of the environment). Alternatively, at the loss of a single bit of information, the entropy of the environment increases by at least k ln2(ln = log_e).

In a quantum computer, the quantum gates are nothing but unitary operators. And unitary operators transform state vectors (qubits) to another state vectors in a reversible way. Therefore a quantum computation may always be reversed. For example, in the quantum version of AND gate, four outputs are required to get the information about input state uniquely from the output state. It may, however, be noted here that a transformation operator such as a measurement is not unitary and therefore the measurement transformation is not reversible. As discussed in Chapter 19, during the process of measurement the process of collapse of the state take place and therefore the quantum state upon measurement is destroyed and cannot be recovered.

20.7.4  Multiple Qubit Gates

In order to get reversible gate, we sometimes need to have multi-bit gate. For example controlled–controlled NOT gate (CCNOT or the Toffoli gate) works as reversible AND gate. The Toffoli gate flips the third input if the first two are both . It is shown graphically as

The Toffoli gate operating on 3-qubits shall give output shown below:

It is possible to construct a reversible AND gate using Toffoli gate. Having reversible AND and NOT gates in our hand, it is possible to realize any Boolean function by using arrays of these gates.

20.8  QUANTUM COMPUTATION

20.8.1  Preparing a Quantum State

We have learnt that in quantum mechanics, the states of different systems are put together by tensor product whereas in classical mechanics it is done by Cartesian product. If we consider two different quantum systems, having the sets of basis states (in n-dimensional vector space) and (in m-dimensional vector space), then the composite quantum system is described by the set of basis states obtained by the tensor product of and i.e.

The resulting basis states are the state vectors of m n dimensional vector space.

For example, let us consider two single-qubit systems

and

Then the composite two-qubit system is described by state vector:

So the state space of 2-qubit system is 2² = 4-dimensional. In fact, the state space of quantum system grows exponentially with the increase in physical size (i.e. with the increase of number of individual quantum units (qubits here) comprising total quantum system). A quantum system consisting of n-qubits is to be described in the 2ⁿ-dimensional state space.

Let us consider a system of n-qubits where Hadamard Gate [i.e. operator Ĥ of Eq. (20.14e)] is applied to each of the qubits. This can be expressed as the tensor product.

Using the tensor product algebra (discussed in Chapter 7 in details) this operation may also be expressed as

Here tensor product of all Ĥ operators is applied on the state vector (of the composite system) obtained as tensor product of state vectors of individual qubits.

We know the operation of Hadamard gate Ĥ on a single qubit:

So if we want to prepare a single qubit in state we shall start with state and shall operate gate Ĥ on it. Similarly to prepare state we shall operate gate Ĥ on state . Let us next consider a 2-qubit system. If we want to prepare a 2-qubit system in state we shall see below, we should start with state and get tensor product Ĥ ⊗ Ĥ operated on :

The state is

and operator Ĥ ⊗ Ĥ is [see Eq. (7.94)].

Operation of Ĥ ⊗ Ĥ on gives

So by operating Ĥ ⊗ Ĥ on the state , one gets a state having equal probability amplitude of all the (four) basis states and of 2-qubit system. Extending it to n-qubit system, let the operator Ĥ operate on each of the n-qubits, where each qubit is in its state, one shall get

which represents all the numbers from 1 to 2ⁿ. Thus one gets the final state having equal probability amplitude of all the 2ⁿ basis states. A measurement on the final (superposition) state shall give one of these 2ⁿ basis states as output. Thus making a measurement at this stage is not of any use, as one gets any single (random) state with equal probability. A quantum algorithm (to be discussed in Section 20.8.3) may apply a particular transformation on this superposition state such that the probability of a desired result increases when a measurement on the final (transformed) state is made.

20.8.2  Conceptual Quantum Computer

In Section 20.7, we discussed about the quantum logic gates, which are really building blocks of quantum computer. Quantum computer is a machine which is a theoretical construct of a Turing machine. This machine establishes Church–Turing principle. The essence of a quantum computer may be stated as follows:

Figure 20.9 Quantum circuit where and are unitary operators and is the measurement operator

1. Each of the n-qubits, can be prepared in some known state.
2. Each qubit can be measured in the basis states and .
3. A set of quantum logic gates may be applied to any subset of the qubits.
4. The qubits do not evolve other than via above transformations, where these evolve according to Schrodinger equation.

Figure 20.9 shows a quantum circuit where are unitary operators (i.e. quantum logic gates) and is the measurement operator. Obviously, the quantum circuit is different from a classical circuit where logic gates are spread out in space on a classical circuit board in both feed–forward and feed–backward manner. In Figure 20.9 one observes that the logic gates are applied sequentially to a set of qubits. The gate operators may also be applied on a part of the qubit.

20.8.3  Quantum Algorithm

As mentioned in Section 20.8.1, a quantum algorithm may apply a particular transformation on the prepared superposition state. Here we shall discuss, in brief, an introduction to two important quantum algorithms: (1) Shor’s factoring algorithm and (2) Grover’s search algorithm.

1. Shor’s Factoring Algorithm

   It may be mentioned that the most important discovery in quantum computing to date is that quantum computers may perform some task so efficiently, that are not really feasible on a classical computer. For example, finding factorization of an n-bit integer requires number of operations increasing exponentially with n, in a classical computer. The quantum computer on the other hand shall require number of operations proportional to roughly n².

   The Shor’s algorithm for factoring a number M on a quantum computer starts with finding the period of the sequence.

    

   f(n) = aⁿ (mod M)        (20.31)

    

   where a and M are relatively prime. Let us consider the sequence 2ⁿ (mode 15). We have

   

   This periodic sequence has the period 4. Let r be the period of function f(n) [of Eq. (20.31)]. We notice that f(0) = 1. Hence f(r) = 1, which implies that M divides (a^r – 1). For an even number r, if the condition a^r/2 (mode M) = ±1 is not satisfied, then a factor of M may be obtained as the g c d (greatest common divisor) of (a^rl2 – 1), (a^r/2 + 1) and M [as (a^r – 1) = (a^r/2 – 1) (a^r/2 + 1)]. The key point here is to find the period r for very big integer M whose prime factors we are going to search. This period may be found efficiently by using quantum discrete Fourier transforms.

   We know the usual (classical) discrete Fourier transform takes as input a vector of complex numbers x₀, x₁, ··· x_{N – 1} (N is a fixed number). The output is a vector of complex numbers y₀, y₁, ··· y_{N – 1} defined by

   

   The quantum discrete Fourier transform is a similar transformation. However, the quantum Fourier transform on orthonormal basis states is a linear operator with the following action on the basis states:

   

   Operation (20.34) may be used in expressing an arbitrary state vector as

   

   where the probability amplitudes b_k are the discrete Fourier transform of the probability amplitudes a_j. This transformation is a unitary transformation and thus could be implemented by a combination of various quantum logic gate operations in the quantum computer.

   Now for the integer M to be factorized, one chooses the values of a and n [Eq. (20.31)]. One then finds the period r using quantum discrete Fourier transform. One then finds g c d (greatest common divisor) of (a^r/2 – 1), (a^r/2 + 1) and M by using the well known Euclid’s algorithm. Thus a nontrivial common divisor, say h, is a factor of M. Then if M/h is a nonprime integer, one may start the procedure again to find the next factor, and so on.

2. Grover’s Search Algorithm

   Suppose we have a map showing a number of cities and we have to find the shortest route passing through all the cities indicated on the map. A simple obvious algorithm to find the shortest route is to search all possible routes, keeping record of which route has shortest length. With N possible routes, the classical computer shall have O(N) operations to determine the shortest route. On the other hand, a quantum search algorithm, due to L. Grover, requires the quantum computer to have only operations to determine the shortest route.

   In general, we have to search through a search space of N elements. We have to find an element in this space satisfying a given property/condition. Let us index these elements with numbers 0 to N – 1 and set N = 2ⁿ, such that the information is stored in n bits.

   The search algorithm is a sequence of unitary operations on a pure state (i.e. a state which is a linear superposition of basis states) followed by the measurement operation. As mentioned above let N = 2ⁿ (n is total number of qubits) and let be the solution state. We have the following steps of operations:

   Step 1: To prepare the initial state by applying Hadamard transform on all state.

   

   Here initial state, so prepared, is a linear superposition of all basis states with equal amplitude

   Step 2: To apply Oracle operation

   

   where f(x) may be 0 or 1. In fact, Oracle operation is designed in such a way that if f(x) for a particular basis state (say ) is 1, then it inverts that state. In other words, we wish to state that the Oracle can recognize a solution and inverts the phase of that solution. The result of total Oracle operation is to leave all basis states unchanged while inverting the particular (recognized) state . So one gets

   

   Step 3: To apply ‘inversion about mean’ operation to make the probability amplitude of the solution state high, which can be realized by the ‘inversion about mean’ operator,

   

   where I is the unit matrix of dimension N. By this operation the probability amplitude of state increases at the cost of all other (N – 1) basis states, (see Figure 20.10).

   

   Figure 20.10 Graphical representation of Grover’s algorithm

   Step 4: To repeat Steps 2 and 3, r times.

   Step 5: To make a measurement.

   It is claimed that the searching is successful for

EXERCISES

Exercise 20.1

Convert following decimal numbers to their binary equivalents:

• 0.008
• 0.5
• 115.2
• 1857

Exercise 20.2

Convert following binary numbers to their decimal equivalents.

• 0.01011
• 11000.1
• 10111
• 111000

Exercise 20.3

In an asymmetric coin, the probability of getting head in a throw is What is the information measure when tossing the coin and getting the result?

Exercise 20.4

In an asymmetric dice, the six faces with numbers 1, 2, ..., 6 have probabilities respectively to appear in a throw. What is the amount of information gained when throwing the dice and getting the result?

Exercise 20.5

Consider the Boolean variables A, B, C. Use the rules of truth tables of Section (20.3) and demonstrate the relations.

1. (A + B) · (A + C) = A + B · C
2. A · (B + C) = A · B + A · C

through truth tables.

Exercise 20.6

What is the Boolean relation corresponding to the equation.

1. Z = A or B or C
2. Z = A and B or C

Show the corresponding truth tables.

Exercise 20.7

A logic gate has N input components. How many rows does the corresponding truth table have?

Exercise 20.8

Consider two spin particles (say, electrons) such that

1. each one is in spin state
2. each one is in spin state
3. One is in state and the other in state

Find the tensor product of spin states (in the tensor product space) for the above three cases.

Exercise 20.9

In the above case of two spin particles, write the tensor product of the corresponding spin operators.

Exercise 20.10

1. Verify that Hadamard Gate matrix Ĥ is unitary
2. Verify that Ĥ² = I
3. Find eigenvalues and eigenstates of Ĥ.

Exercise 20.11

What are respective periods of the sequences.

1. 5ⁿ (mod 16)
2. 11ⁿ (mod 25)
3. 3ⁿ (mod 20)
4. 2ⁿ (mod 7)

SOLUTIONS

Solution 20.3

The information measure is

Solution 20.4

Solution 20.5

1. The said relation is demonstrated in the following truth table:
   
2.  
   

Solution 20.6

1. Z = A + B + C
2. Z = A · (B + C)
   

Solution 20.7

2^N

Solution 20.8

1. Tensor product of spin states and of two electrons
   
2.  
   
3.  
   

   and

   

Solution 20.9

Tensor product of spin operators

Solution 2.10

1. A matrix  is said to be unitary if

    

   Â^† Â = I
   

   and we have

   Ĥ^† Ĥ = I

   so Ĥ is unitary and

2. Ĥ² = I
3. One can easily find that Ĥ has

   eigenstate with eigenvalue +1

   eigenstate with eigenvalue –1

Solution 20.11

REFERENCES

1. Nielsen, M.A. and Chuang, I.L. 2002. Quantum Computation and Quantum Information. Cambridge, U.K.: Cambridge University Press.
2. Liboff, R.L. 1992. Introductory Quantum Mechanics. Mass: Addison-Wesley.
3. Feynman, R.P. 1982. Simulating Physics with Computers. Int. J. Theor. Phys. 21, 467.
4. Bennett, C.H. 1995. Quantum Information and Computation. Phys. Today, 48, 24.
5. Grover, L.K. 1997. Quantum Mechanics helps in Searching for a Needle in a Haystack. Phys. Rev. Lett. 79, 325.
6. Ekert, A. and Jones, R. 1996. Quantum Computation and Shor’s Factoring Algorithm. Rev. Mod. Phys., 68, 1.