Quantum Computation: a Tutorial - monoidal.net

1 Quantum computation : a Tutorial1 Quantum computation : a TutorialBeno t ValironUniversity of Pennsylvania,Department of Computer and Information Science,3330 Walnut Street, Philadelphia, Pennsylvania, 19104-6389, 15 April 2012 AbstractThis Tutorial is the first part of a series of two articles onquantum computation . In this first paper, we present the field of quan-tum computation from a broad perspective. We review the mathematicalbackground and informally discuss physical implementations of quantumcomputers. Finally, we present the main constructions specific to quan-tum computation yielding computation , Quantum Algorithms, QuantumComputers. 1 IntroductionWhether the notion of data is thought of concretely or abstractly, it isusually supposed to behave classically: a piece of data is supposed to be clonable,erasable, readable as many times as needed, and is not supposed to change whenleft computation is a paradigm where data can be encoded witha medium governed by the law of Quantum physics.

2 Although only rudimentarySupported by the Intelligence Advanced Research Projects Activity (IARPA) via Departmentof Interior National Business Center contract number D11PC20168. The Government isauthorized to reproduce and distribute reprints for Governmental purposes notwithstandingany copyright annotation thereon. Disclaimer: The views and conclusions contained herein arethose of the authors and should not be interpreted as necessarily representing the official policiesor endorsements, either expressed or implied, of IARPA, DoI/NBC, or the t Valironquantum computers have been built so far, the laws of Quantum physics aremathematically well described. It is therefore possible to try to understand thecapabilities of Quantum computation , and Quantum information turns out tobehave substantially differently from usual (classical) Sections 2, 3 and 4 of this Tutorial , we describe the mathematicsneeded for Quantum computation together with an overview of the theory ofquantum computation .

3 In Section 5, we briefly present the range of physicalimplementations of Quantum devices. We then discuss in Section 6 three subtlealgorithmic constructions specific to Quantum computation that can be used inorder to design algorithms able, in some case, to outperform classical algorithmson particular paper is the first part of diptych on Quantum computation . Thesecond part20)will be concerned with programmatic perspective on quantumcomputation. 2 One Quantum bitIn classical computation , the smallest unit of data is thebit, element ofthe two-element set{0,1}. In Quantum computation , the smallest unit of datais aquantum bit, orqubit, defined as a ray in a 2-dimensional Hilbert formalismA Hilbert space is a complex vector space equipped with a notion oflengthand a notion oforthogonality, both defined by a scalar product. In thissection, we develop the required notions for the 2-dimensional complex number is of the forma+b i, whereaandbare usual real numbers, and whereiis a special symbol.

4 Complex numbers canbe added and multiplied as follows: (a+b i) + (c+d i) = (a+c) + (b+d) iand (a+b i)(c+d i) = (ac bd) + (ad+bc) i. The symbolihas therefore thepropertyi2= 1. Given a complex number =a+b i, theconjugateof isthe complex number =a b i. Thenormof is| |=a2+b2, also equal to .A complex numbera+b ican be seen as a point in thecomplex planewith coordinates (a,b). One can therefore propose an alternative representationfor complex numbers using polar coordinates: the complex e icorresponds to cos( )+ sin( ) i. If the polar representation of complex numbers does not playQuantum computation : a Tutorial3well with addition, it supports multiplication: ( 1e 1i)( 2e 2i) = ( 1 2)e( 1+ 2)iand conjugation: e i= e i. The angle is called thephaseand theamplitudeof the complex Hilbert set of column vectors ( ) where and are complex numbers can be equipped with a structure of vector space. Ifu= ( ) andv= ( ), thenu+v= ( + + ) and u= ( ).

5 Thescalar productof the vectorsuandvis the operation u|v = + . It can also be seen asthe multiplication of the row-vectoru = ( ) with the column vectorv(u iscalled theconjugate transposeofu): see Figure 1(d). If u|v = 0, we say thatuandvareorthogonal. For example, (10) and (01) are orthogonal; so are (11) and(1 1). The scalar product induces anorm:||u||2= u|u . Anormalized vectoris a vector of norm 1. Abasisis a pair of vectorsuandvthat can generatesthe whole space when linearly combined. The basis isorthonormalifuandvare normalized and orthogonal. For example, (10) and (01) form an orthonormalbasis. So do1 2(11) and1 2(1 1). ray is an equivalence class of vectors stable by (non-zero) scalar mul-tiplication. So ( ) is in the same ray as ( ) and (2 2 ). A corollary is that forevery non-zero vector ( ) it is possible to find a normalized vector whose firstcoordinate is a non-negative real number: if = 1e 1iand = 2e 2i, choose1 21+ 22( 1 2e( 2 1)i).

6 Unitary Quantum computation , a particularly interestingoperation on Hilbert space is theunitary map. It is simply a rotation, achange of orthonormal basis, and it can be efficiently represented by a 2 2matrix: if (10) is sent to ( 1 1) and (01) is sent to ( 2 2), the unitary map isU= ( 1 2 1 2). The transformationUon a particular vector is the applicationof the matrix onto that vector, and the composition of two unitaries is matrixmultiplication (see Figure 1). Quantum bit as vector of informationA Quantum bit is merely a vectoru= ( ) in the 2-dimensional Hilbertspace. In order to make computational sense out of it, we choose the orthonormalbasis (10),(01) that we write|0 ,|1 . The vectorucan then be seen as thequantum superposition of the two classical boolean values true and false: |0 + |1 . The two values|0 and|1 are orthogonal to each t Valiron(a bc d)(x yz t)=(ax+bz ay+btcx+dz cy+dt)(a) matrix-matrix(a bc d)(xz)=(ax+bzcx+dz)(b) matrix-column vector(ac)(x y)=(ax aycx cy)(c) column vector-row vector(a b)(xz)=(ax+bz)(d) row vector-column vectorFig.

7 1 Matrix multiplicationWe will use the convention that|x ,|y ,|z ..refer to base states whilegreek letters:| ,| ,..refer to general Quantum a Quantum system comes equipped with a preferred basis|0 ,|1 ,the operations are described in this first class of operations we can perform is thecreationof a quantumbit out of nothing. Both|0 and|1 can be created at wish. The second classof allowed operations consists in unitaries, Beside theidentityI, some of the usual gates are the not-gate, the Hadamard, the phaseshift and the phase-flip:N=(0 11 0), H=1 2(111 1), V =(100e i), Z=(100 1).The gateNsends|0 to|1 and|1 to|0 : it effectively acts as a negation. TheHadamard gate creates Quantum superposition: it sends|0 to1 2(|0 +|1 ).The gateV does not change the vector|0 but sends|1 toe i|1 .Zis justV .Unitaries are only rotating the state of the Quantum system. In order toget some classical information out, the only available operation is themeasure-ment.

8 It is aprobabilisticoperation defined as follows: ifu= ( ) is a normalizedvector representing a Quantum bit, the measure ofureturns true with probabil-ity| |2and false with probability| |2. Moreover, the state of the Quantum bitwas modified by the measure: the Quantum bit is in state (10) if the result of themeasure was true and (01) is the result was false. We say that the measurementwas performedagainst the basis(10),(01). In general, given a basisu0,u1, ameasurement ofvagainstu0,u1returns true with probability| u1|v |2and falsewith probability| u2|v |2. It turnedvintou1if the measurement returned trueand intou2if it returned computation : a Tutorial5 Note that if we are physically restricted to measurements against thebase (10),(01), it is still possible to simulate a measurement against an arbitrarybasisu0,u1by first applying the unitary sendingu0to (10) andu1to (01) on thevector under consideration, then measuring, then applying the unitary sending(10) and (01) respectively back with one Quantum bit, one can already build a simple experi-ment: the coin-toss.

9 Create a Quantum bit in state|0 , apply the Hadamard gateto change the state of the qubit to1 2(|0 +|1 ), the measure in the canonicalbasis: we get true and false with equal measurement can equivalently be thought ofasdestroyingthe Quantum bit we were considering. In the physical realizationwith photons, this is what happen for example. It is not incompatible with thefirst approach since one can always re-create a Quantum bit in the canonicalbasis to simulate a non-destructive Bloch sphereThe rays ofC2are in one-to-one correspondence with the points on theunit sphere ofR3. In spherical coordinates, a point ( , ) with [0, ], [ , ] is in correspondence with the ray of representativer( , ) =(cos 2ei sin 2).(1)The correspondence is pictured in Figure 2: indexsindicates spherical coordi-nates; indexcindicates 3-dimensional coordinate; indexHindicates coordinatesinC2. This unit sphere is called theBloch the Bloch sphere, one can define three canonical orthogonal bases for a Quantum bit, as follows.

10 (|0z ,|1z ) = (|0 ,|1 ) is thebasis alongz; (|0x ,|1x ) = (1 2(|0 +|1 ),1 2(|1 |1 )) is thebasis alongx; (|0y ,|1y ) = (1 2(|0 +i|1 ),1 2(|1 i|1 )) is thebasis three bases have a peculiar property: measuring|0z and|1z againstboth the bases alongxandyreturns true and false with probability12: in otherwords, two Quantum bits in state|0z and in state|1z cannot be distinguishedby measurement against the basisxandy. This property is also true for thequbits|0x and|1x when measured against the bases alongyandz, and for the6 Beno t Valiron0wwx OOz //y 44 (010)c=( /2 /2)s7 1 2(1i)H##(100)c=( /20)s7 1 2(11)H,,(001)c= (00)s7 (10)H (010)c=( /2 /2)s7 1 2(1 i)H##( 100)c=( /2 )s7 1 2(1 1)H33(00 1)c= (0 )s7 (01)H>>Fig. 2 The Bloch |0y and|1y measured against the bases general, two rays inC2are orthogonal if and only if their representa-tions on the Bloch sphere are BB84 algorithmWe can use two of the bases described in Section to securely createsecret keys for one-time pad encryption.