chapter 20 Introduction to Quantum Computing If you do not expect the unexpected, you will not find it. —Heraclims 20.1 INTRODUCTION All modem day computers use two-state binary logic in data processing (or information processing). The size of the modem 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 foiuis: 1. The computing pawer 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 hefore we may have extremely small sized computing devices. Aud with that cauciely small size of computing devices, the components will he 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 (ic. the computer) wes 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 com- Putation. Iu fact, quantum computation is seen as a formulation for fuluie quantum computers. We shall introduce the readers to quantum computation in this chapter. But, firstly, we shall discuss the preliminaries of classical computation: binary umber systems, (classical) logic gates, and ‘Turing machine. We shall, then, introduce quantum bits (qubits) and quantum logic gates. 4 Scanned by CamScanner492 | Principles of Quantum Mechanics 20.2 BINARY NUMBER SYSTEMS. Itis 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 I relate to two separate Voltage levels. Typically the number 0 corresponds to a voltage near zero and the number I to a voltage near 5 volts. In binary code, either of these two different states (of logic gates), represented by a zero ang 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: 3709.41 =3 x 10347 102+ 0 10! +9 x 109 +4 x 1071 + 1 x 10% (20.1) 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 | only. For example, the binary repre- sentation of few numbers, say 5, 10, 25.5 are S-1x24+0x2!41% 20-101 (20.2a) 10=1%2°+0%27 +1 x2! +0%2= 1010 (20.28) DISLXM+IXP+OX2+0X2' 41x 24121 = N00 (20.2c) 1. Amethod 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 inary representation hy the following sequence of divisiuns by 2. Step 1: = 65,- 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, Step2: 9=32, with remainder 1 32 sn emai Step 3: 32=16, with remainder 0 16 “in ceri step4: 1 =8, with remainder 0 Step 5: g with remainder 0 step 6:, $ with remainder 0 Step 7: 2 1, with remainder 0 1 a . Step 8: with remainder 1 Scanned by CamScannerIntroduction to Quantum Computing | 493, we get 131 = 10000011 One may notice that to write a number x in binary code, one will require tog, x number of bits (i.e. number of 0 s and 1s), In the language of computer, the number of bits needed ta store the value of xis log, x, 2. Amethod 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 04x2=08 0 The 0 (before decimal) in the above expression gives the first number (after decimal) in binary representation of 0. Step2: 0.8x2=16 1 Step 3: Change 1.6 to 0.6 and repeat the process 06x2=12 1 step4: 02x2=04 0 Step 5: 04x2=08 0 Step6: 0.8x2=16 1 Step 7: 0.6x%2-1. 1 so 0.4=0.0110011 OK ITH TKDE 1X IF +OKI4 KOKI HTX IO HL KIT = 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 4°as 4, How snuch infonuation you have got? Auswer to this question depends on what you already knew about X. For example, if you already knew 5X was equal to 4, you have got no information from your friend in this context. On the other hand if you only knew that has an integral value in hetween | and 10. then to leam 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 ‘is defined to be SPO) =-Y, P@Ilog2 Pe) 203) ‘We can easily sec that Sis always positive since probabilities p(x) are less than unity. The standard practice is to use symbol 5 (X) for S {{p(x)]}. S(X) merely means the information content of the variable ¥ fand 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 eas Scanned by CamScanner A494. | Principles of Quantum Mechanies Example 1 If-Yis given by the toss of a coin, then p(x) = } for x € [head, tail]. So Pott ye pestoxs 0) =-[ 3 logs 5 +5 logs 5 |=! (20,4) -M Example 2 If-Xis given by the throw of a symmetric die, then p(x) =f forx€ (1, 2,3.4,5,6).5, 1 log, - 4...(6 terms in a] = log, 6 = 2.58 (20.5) Example 3 If X can take N different values with equal probability [ p(x) = (1/N)], then y P(x)log, p(x) - logN (20.6) One observes that the maximum information which could be stored by a variable X, which may take on N different values is S(Y)= log, N. When variable X takes two values with equal probability (Example ), we have S(X) = 1. this may be taken as fundamental unit of information. So a two-valued variable ur 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 » Wo be the probability that 4 = 1, then the probability is (1 - p) for X'=0, and the information may be written as a function of p alone: ‘S(p)=— plog, p — (1 ~p) log, (1 ~ p) (20.7) 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’, In Figure 20.1a, there is a continuous range of values of voltages—ealled as analog signal. The electronic circuits using analog signals are called analog cireuits. In Figure 20.1b, the voltage is in a pulse wave- form, where only discrete values of voltages are possible. The high level is termed as ‘1’ and low level as “0” (sce 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 | | 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 poten- tial 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 varions gates. 20.3.2 Structure and Functioning of Various Gates |. OR Gate: An OR gate has two or more inputs and one output. An OR gate with two inpulS | A and B and an output X is constructed with two p-n junction diodes D, and D, (Figure 203). The circuit evaluates the function Y= 4 OR B, ix. X= A+ B, For two input O gate, we have following four different cases, a Scanned by CamScannerInlroduction fo Quantum Computing | 495 " WV Cn 3 Level 1 ) 3 $s Figure 20.1 (a) Continuous (b) Pulse signal ( 0.2 v#0.2V Figure 20.2 Range of voltages corresponding to level ‘0 und level ‘1’ (i) A=0, B=0: There is no potential difference anywhere in the circuit so. X= 0. (ii) 40, B= 1: The potential is zero at A and is SV at B, The diode D, is forward biased and conducts. Thus the potential at ¥'is sume as that at B, So.X'= 1. (iii) A= 1, B=0: Now D, conduets and X= 1. 1: Both the diodes D, and D, will conduct and potential and X is same as that at 5V.SoX=1 Scanned by CamScanner496 | Principles of Quantum Mechanics Thus circuit gives X as 1 when input A or B or both are | and gives Xas 0 when both A and B are 0, This statement can also be given in the form of truth table given as follows: 2. AND Gate: In a two input AND gate, the output X is | if both the inputs 4 and & have state | (Figure 20.4). So we have following four different cases. (i) (i Gi) (iv) A dD, A e + : My x ° o— 5 4 oie a ) (b) Figure 20.3 (a) Realization of two input OR gate with p-n diodes D, and D, (b) Symbol for OR gate Truth Table for Two Input OR Gate X=AORB=A+B A 0 0 1 1 lo lo] = 0 1 1 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 Xis same as that at A or B. So.X—0. A=0,B=1: The diode D, provides a short circuit i.e, the low resistance path, so potential at Xis same at that at A. So.X'=0, 4A~1,B~-0: Now D, provides short circuit, so X= 0. A=1,B=1: None of the diodes D, and D, would conduct as potentials at both A and B are SV. As there will be no current through R, so voltage drops across R and the potential at will be SV. SoX= 1. A Do, A - K — _| x . KI __| a De o — x-aanos TASB av (@) (b) Figure 20.4 (0) Two inputs AND gate with diodes D, and D, (b) Symbol for AND gate Scanned by CamScannerIntroduction to Quantum Computing | 497 Truth Table of AND gate ee A | 8 | X=AANDB=A-B 0 I es ee 2 | 1 o 1 0 I 0 Truth Table of NOT gate =NOTA=A a 0 I 1 I Se 4 NOT gate connot be realized with diodes. For realizing this, we have to use a simple transistor inverter chown in Figure 20.5. Let us firstly take the case 4 = 0. In this case the emitter-base junction is jased, so no curren jt As a result there is no current through the resistance. R,.. Under this dision the potential at V is same as that at positive terminal of the battery, 1€. 9V. So ‘if = 0, we neXt take the case when potential 4 is 5V. In this situation the base-emitter junction is lrge current inthe circuit the direction of current is from base to emitter @ ® Figure 20.5 (0) Realization of NOT gate through transistor inverter circuit (b) Symbol for NOT gate Scanned by CamScanner498 | Principles of Quantum Mechanics Aw —_ 3 [ X= NOT (AAND 8) = AeB or simply Aa \p—e X Sit Figure 20.6 NAND gate 4. NAND Gate: With two inputs 4 and B, the output function X=NOT (4 AND 8) is called NAND function. It is written as Y= A NAND B = AB. 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: A B AAND B= A-B X= AB ° oO 0 | _t oO 1 o ] 1 o 0 1 1 1 1 0 5. NOR gate: For inputs A and B, the function ¥ = NOT (4 OR A) is called a NOR function, It is written as X= A NOR B=A+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: =|-lolo] > =lo|=|o} » lojolo}~ A : ee NOT (AOR 8) =ANORB +6 Figure 20.7 NOR gate 6. XOR gate: The exclusive OR gate is labeled as XOR gate. For inputs 4 and B, the output Xof 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 |, is 0. The symbol for an XOR operative is @ which designates addition mod (2). The truth tl is given below: Scanned by CamScannerIntroduction to Quantum Computing | 499 Truth table for XOR gate B X=A0B oO 0 1 o 1 =|=]o}o] > of-|— 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 ofa Turing machine (illustrated in Figure 20.8). Finite state oon control Read-write head [= Ls fone Figure 20.8 Basic elements of single tape Turing machine 1. A Program 2. A Finite State Control, consisting of a finite sct of internal states 4), y>, -.. yp, and acting like a microprocessor. The operatian of Turing machine is determined by the primitive program. The finite state control is always in one of the states q,, ... 7,5 which can be regarded as positions in a program. In addition to the states (q,, ... q,,), there are also two special internal states labeled as q, and q,, 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 celll is scanned by a tead-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. Fach cell on the tape contains a symbol drawn from symbol I. The cell on the left edge of the tape has symbol >. All other cells contain one of the symbols 0, 1, 6; 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 T, which appear on the cells of the tape. The program works in such a Scanned by CamScanner500 | Principles of Quantum Mechanics way that in each eyele of the machine, the Turing machine searches fora program line containing (gx, ise, searches for a Tine like (q, 5's *)- Here q and, cegpectively, show the current internal state ofthe tnachine and the symbol being read on the tape. In case such & progrant line is iat ound the maching halts operation as in (his case the internal state of the machine is changed to gy, However, if the saiq program line is found, the program line is executed in following steps: 1. The internal state of the machine is changed to, say, 4”. 2. ‘The symbol x on the cell is overwritten, say, by symbol >’. : 3 The tapered moves lft, right or stands still depending on whether» is = 1, +1 or & respective, Only when the tape-head is at the left most cel of the tape and s =~. the tape-head does not move, ‘These steps of Turing machine are used to compute @ function. The importance of the Turing ma- chine in computing lies in the Church—Turing theorem: Any Algorithinic Process ca be simulated efficiently using a Turing machine. 20.5 QUBITS Qubit stands for quantum binary digit. Qubitis the elementary unit of quantum information, just ike 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 (ii) 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 |f) 1 0 : t( 4) and (°) or|0) and|1)] form the basis unit vectors in the two-dimensional spin } linear vector space. Therefore the quantui (spin) state of an electron (j.. the basis state |0) or |1)) may be taken aca qubit (just like a classical bit 0 or 1 represents a specific voltage threshold). However, there is a funda- inental difference between the qubits (as unit veetors |0) and |1)) and hits (as 0 and 1). Whereas in case of bits, there is no significance of the linear combination of bits 0 and | (a.0 + b.1), in case of qubits, the linear combination of unit vectors |0) or |1) (a10) + b11)) is also a unit vector in the same vector space and therefure is a qubit. Ifa measurement is donc on an electron in spin state (a|0) + b]1)) (say using the Stern-Gerlach experiment), the electron is found only in ane af the (spin np |0) ar spin down |1)) states with probabilities laf? 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 (a|0) | 5[1)), the qubit is found to be |0) or 1) with probability |a[? and [d/ respectively (laf +|[?= 1). Once measured, the qubit continues to remain in the state measured. If we consider an ensemble of N identical quhits, each in same state (a|0)-+ b|1)), the measurement on all qubits shall give Naf? number of qubits in state |0) and N |b? number in state |1), ‘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 | if at least onc 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 ete. In quantum case if we want to have, for example, a NOT gate (whose purpose is to change the basis state |0) to |1) and vice-versa), we shall have to seck u linear operator (2 x 2 matix) in the corresporiding 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 sh discuss about linear operators working as quantum gates on qubits in Section 20.7. But firstly we discuss multiple qubit system. — Scanned by CamScanner