《quantcomp03.ppt》由会员分享,可在线阅读,更多相关《quantcomp03.ppt(67页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、QUANTUM COMPUTINGanintroduction Jean V.BellissardGeorgiaInstituteofTechnology&InstitutUniversitairedeFranceA FAST GROWING SUBJECT:elementsforahistoryFeynmans proposal:Richard P.Feynman.Quantum mechanical computers.Optics News,11(2):11-20,1985.He suggested in 1982 that quantum computers might have fu
2、ndamentally more powerful computational abilities than conventional ones(basing his conjecture on the extreme difficulty encountered in computing the result of quantum mechanical processes on conventional computers,in marked contrast to the ease with which Nature computes the same results),a suggest
3、ion which has been followed up by fits and starts,and has recently led to the conclusion that either quantum mechanics is wrong in some respect,or else a quantum mechanical computer can make factoring integers easy,destroying the entire existing edifice of publicKey cryptography,the current proposed
4、 basis for the electronic community of the future.Deutschs computer:David Deutsch.Conditional quantum dynamics and logic gates.Phys.Rev.Letters,74,4083-6,(1995).David Deutsch.Quantum theory,the Church-Turing Principle and universal quantum computer.Proc.R.Soc.London A,400,11-20,(1985).Shors algorith
5、m:Peter W.Shor.Algorithm for quantum computation:discrete logarithms and factoring Proc.35th Annual Symposium on Foundation of Computer Science,IEEE Press,Los Alamitos CA,(1994).This algorithm shows that a quantum computer can factorize integers into primes in polynomial time CSS error-correcting co
6、de:A.R.Calderbank&B.P.W.Shor.Good quantum error-correcting codes exist Phys.Rev.A,54,1086,(1996).A.M.SteaneError-correcting codes in quantum theory Phys.R.Letters,77,793,(1996).Topological error-correcting codes:Alex Yu.Kitaev.Fault-tolerant quantumcomputation by anyonsarXiv:quant-phys/9707021,(1997
7、).Books,books,booksAnd much more athttp:/www.nsf.gov/pubs/2000/nsf00101/nsf00101.htm#prefacehttp:/www.math.gatech.edu/jeanbel/4803/reportsarticles,books,journals,list of laboratories,list of courses,list of conferences,QUBITS:aunitofquantuminformationQubits:George BOOLE(1815-1864)usedonlytwocharacte
8、rstocodelogicaloperations 0 1Qubits:John von NEUMANN(1903-1957)developedtheconceptofprogrammingusingalsobinarysystemtocodeallinformation 0 1Qubits:Claude E.SHANNONAMathematicalTheoryofCommunication(1948)-Informationtheory-unitofinformationbit 0 1Qubits:0 quantizing1 1|0 =0 0|1 =1canonicalbasisin C 2
9、1-qubitQubits:1generalqubit a|y =a|0+b|1 bDiracsbraandketinC 2anditsdual y|=(a*,b*)=a*0|+b*=ai|0+bi|1 bi=a1*a2+b1*b2innerproductinC 2usingDiracsnotations Qubits:a1 a2*a1 b2*|y1 y2|)=usingDiracsbra-kets1generalqubitQubits:1generalqubit a|y =a|0+b|1 b=|a|2+|b|2=1onequbit=elementoftheunitsphereinC 2 Qu
10、bits:1generalqubit a|y =a|0+b|1 b|a|2=Prob(x=0)=|2Bornsinterpretationofaqubit|b|2=Prob(x=1)=|2Qubits:1qubit:mixedstates|y =|0|1|0|0|1 tensorbasisin C2nquantizinggeneralN-qubitsstatesQubits:generalN-qubitsstates|y =a(x1,xN)|x1xN|a(x1,xN)|2=1entanglement:anN-qubitstateisNOT atensor productQubits:gener
11、alN-qubitsstates|b00 =(|00+|11)/2entanglement:Bellsstates|b01 =(|01+|10)/2|b10 =(|00-|11)/2|b01 =(|01-|10)/2QUANTUM GATES:computinginquantumworldQuantum gates:U|x U|x 1-qubitgates 01X=10 0-iY=i0 10Z=0-1 10I=01PaulibasisinM2(C)UisunitaryinM2(C)Quantum gates:U|x U|x 1-qubitgates 10S=0i 10T=0eip/4 11H=
12、2-1/21-1Hadamard,phaseandp/8gatesUisunitaryinM2(C)Quantum gates:N-qubitgates|x1 U|x1 x2 xN UisunitaryinM2N(C)|x2|x3|xN|x1 x2 xN =UQuantum gates:|x UisunitaryinM2(C)|y|x Ux|y UcontrolledgatesQuantum gates:|x flippingabitinacontrolledway:theCNOTgate|y|x|x y U=Xx =0 ,1y,1-yCNOTcontrolledgatesQuantum ga
13、tes:|x1 flippingbitsinacontrolledway|y Ux1xn|y|xn|xn|x1 UcontrolledgatesQuantum gates:|x1|y|x1x2 y|x2|x2|x1 controlledgatesflippingbitsinacontrolledwayTheToffoligateQUANTUM CIRCUITS:computinginquantumworldDevice that produces a value of the bit xThe part of the state corresponding to this line is lo
14、st.Quantum circuits:measurementQuantum circuits:teleportation|y|b00|y HXZQuantum circuits:teleportation|y|b00|y HXZ|x00+|x11 2Quantum circuits:teleportation|y|b00|y HXZ|xx0+|x(1-x)1 2Quantum circuits:teleportation|y|b00|y HXZ(|0 x0+(-)x|1x0+|0(1-x)1+(-)x|1(1-x)1)2Quantum circuits:teleportation|y|b00
15、|y HXZ(|0 xx+(-)x|1xx+|0(1-x)x+(-)x|1(1-x)x)2Quantum circuits:teleportation|y|b00|y HXZ(|0 x+|1x+|0(1-x)+|1(1-x)|x 2Quantum circuits:teleportation|y|b00|y HXZ(|00+|11+|01+|10)|x 2QUANTUM COMPUTERS:machinesandlawsofPhysicsComputers:Non equilibrium Thermodynamics,ElectromagnetismQuantum MechanicsCompu
16、ters are machines obeying to laws of Physics:Computers:Over time,the information contained in an isolated system can only be destroyedEquivalently,its entropy can only increaseSecond Law of ThermodynamicsComputers:Coding,transmission,reconstructionComputation,CryptographyComputers are machines produ
17、cing information:Codingtheoryusesredundancytotransmitbinarybitsofinformation0coding1Computers:Codingtheoryusesredundancytotransmitbinarybitsofinformation0coding1Computers:0 000coding1 111Codingtheoryusesredundancytotransmitbinarybitsofinformation0coding1Computers:0 000coding1 111TransmissionCodingth
18、eoryusesredundancytotransmitbinarybitsofinformation0coding1Computers:0 000coding1 111TransmissionTransmissionerrors(2ndLaw)010110Codingtheoryusesredundancytotransmitbinarybitsofinformation0coding1Computers:0 000coding1 111TransmissionTransmissionerrors(2ndLaw)010110ReconstructionCodingtheoryusesredu
19、ndancytotransmitbinarybitsofinformation0coding1Computers:0 000coding1 111TransmissionTransmissionerrors(2ndLaw)010110Reconstructionatreception(correction)000111Computers:States(pure)of a system are given by units vectors in a Hilbert space HObservables are selfadjoint operators on H(Hamiltonian H,An
20、gular momentum L,etc)Principles of Quantum MechanicsComputers:Quantum Physics is fundamentally probabilistic:-theory can only predicts the probability distribution of a possible state or of the values of an observable -it cannot predict the actual value observed in experiment.Principles of Quantum M
21、echanicsComputers:Principles of Quantum Mechanicselectron shows upWhere one specific electron shows up is unpredictableBut the distribution of images of many electrons can be predicted Computers:|2 represents the probability that|y is in the state|f.Measurement of A in a state y is given by =dy(a)f(
22、a)where y is the probability distribution forpossible values of APrinciples of Quantum MechanicsComputers:Time evolution is given by the Schrdinger equation i d|y/dt=H|y H=H*.Time evolution is given by the unitary operator e-itH no loss of information!Principles of Quantum MechanicsComputers:Loss of
23、 information occurs:-in the measurement procedure -when the system interacts with the outside world(dissipation)Computing is much faster:the loss of information is postponed to the last operationPrinciples of Quantum MechanicsComputers:Measurement implies a loss of information(Heisenberg inequalitie
24、s)requires mixed states Mixed states are described by density matrices with evolution dr/dt=-i H,rPrinciples of Quantum MechanicsComputers:Measurement produces loss of information described by a completely positive map of the form E(r)=Ek r Ek*preserving the trace if Ek*Ek=I.Each k represents one po
25、ssible outcome of the measurement.Principles of Quantum MechanicsComputers:If the outcome of the measurement is given by k then the new state of the system after the measurement is given byrk =Ek r Ek*Tr(Ek r Ek*)Principles of Quantum MechanicsComputers:In quantum computers,the result of a calculati
26、on is obtained through the measurement of the label indexing the digital basisThe algorithm has to be such that the desired result is right whatever the outcome of the measurement!Principles of Quantum MechanicsComputers:In quantum computers,dissipative processes(interaction within or with the outsi
27、de)may destroy partly the information unwillingly.Error-correcting codes and speed of calculation should be used to make dissipation harmless.Principles of Quantum MechanicsTO CONCLUDE (PART I):quantumcomputersmayworkTo conclude(part I)The elementary unit of quantum information is the qubit,with states represented by the Bloch ball.Several qubits are given by tensor products leading to entanglement.Quantum gates are given by unitary operators and lead to quantum circuitsLaw of physics must be considered for a quantum computer to work:measurement,dissipation