Why Quantum Computation?Young's double-slit experimentQubits -- Naive introductionMeasurement example I.Two qubits:EntanglementEPR Paradox:Bell's InequalityCS 294-2 Intro, Qubits, Measurements, Entanglement 8/31/04Fall 2004 Lecture 11 Why Quantum Computation?There are several reasons why we might wish to study quantum computation. Here are a few:• Moore’s LawMoore’s Law states that the density of transistors on a chip roughly doubles every eighteen months.Current estimates say that in about a decade this should be down to single electron transistors. Thisis the end of the road for further miniaturization of classical computers based on electronics. Longbefore that chip designers will have to contend with quantum phenomena. Quantum computationprovides a method of bypassing the end of Moore’s Law, and also provides a way of utilizing theinevitable appearance of quantum phenomena.• Factoring, Discrete log, Pell’s equations, etc..There are certain problems that quantum computation allows us to solve more efficiently that anyclassical computational method. A few examples are listed above. We may wish to exploit thisfeature of quantum computation.• CryptographyQuantum computation allows us to do cryptography in a way that doesn’t require assumptions aboutfactoring primes, etc.. It also allows us to break classical cryptography schemas. Obviously, if we areinterested in cryptography, we’ll also have to be interested in quantum computation.Above are the three standard reasons for studying quantum computation. There are other reasons aswell that are perhaps just as compelling.• Quantum Mechanics is a model of computationWe can study quantum mechanics as a model of computation.• Quantum EntanglementIn particular, the detailed study of entanglement is the most important point of departure from more tradi-tional approaches to the subject. For example, quantum computation derives its power from the fact that thedescription of the state of an n-particle quantum system grows exponentially in n. This enormous informa-tion capacity is not easy to access, since any measurement of the system only yields n pieces of classicalinformation. Thus the main challenge in the field of quantum algorithms is to manipulate the exponentialamount of information in the quantum state of the system, and then extract some crucial pieces via a finalmeasurement.Quantum cryptography relies on a fundamental property of quantum measurements: that they inevitablydisturb the state of the measured system. Thus if Alice and Bob wish to communicate secretly, they candetect the presence of an eavesdropper Eve by using cleverly chosen quantum states and testing them tocheck whether they were disturbed during transmission....CS 294-2, Fall 2004, Lecture 1 12 Young’s double-slit experimentLetψ1(x) ∈C be the amplitude if only slit 1 is open. Then the probability density of measuring a photon atx is P1(x) = |ψ1(x)|2. Letψ2(x) be the amplitude if only slit 2 is open. P2(x) = |ψ2(x)|2.ψ12(x) =1√2ψ1(x) +1√2ψ2(x) is the amplitude if both slits are open. P12(x) = |ψ1(x) +ψ2(x)|2. The twocomplex numbersψ1(x) andψ2(x) can cancel each other out – destructive interference.But how can a single particle that went through the first slit know that the other slit is open? In quantummechanics, this question is not well-posed. Particles do not have trajectories, but rather take all pathssimultaneously. This is a key to the power of quantum computation.3 Qubits – Naive introductionThe basic entity of quantum information is a qubit (pronounced “cue-bit”), or a quantum bit. Consider theelectron in a hydrogen atom. It can be in its ground state (i.e. an s orbital) or in an excited state. If this werea classical system, we could store a bit of information in the state of the electron: ground = 0, excited = 1.+01In general, since the electron is a quantum system, it is in a linear superposition of the ground and excitedstate — it is in the ground state (0) with probability amplitudeα∈ C and in the excited state (1) withprobability amplitudeβ∈ C . It is as though the electron “does not make up its mind” as to which of the 2classical states it is in. Such a 2-state quantum system is called a qubit, and its state can be written as a unit(column) vectorαβ∈C2. In Dirac notation, this may be written as:ψ=α0+β1α,β∈C and |α|2+ |β|2= 1The Dirac notation has the advantage that the it labels the basis vectors explicitly. This is very convenientbecause the notation expresses both that the state of the qubit is a vector, and that it is data (0 or 1) to beprocessed. (The {0,1} basis is called the standard or computational basis.)In general a column vector —called a “ket”— is denoted byand a row vector —called a “bra”— isdenoted by|.This linear superpositionψ=α0+β1is part of the private world of the electron. For us to knowthe electron’s state, we must make a measurement. Measuringψin the {0,1} basis yields0withprobability |α|2, and1with probability |β|2.One important aspect of the measurement process is that it alters the state of the qubit: the effect of themeasurement is that the new state is exactly the outcome of the measurement. I.e., if the outcome of themeasurement ofψ=α0+β1yields0, then following the measurement, the qubit is in state0.This implies that you cannot collect any additional information aboutα,βby repeating the measurement.More generally, we may choose any orthogonal basis v,v⊥and measure the qubit in it. To do this, werewrite our state in that basis:ψ=α0v+β0v⊥. The outcome is v with probability |α0|2, andv⊥with probability |β0|2. If the outcome of the measurement onψyieldsv, then as before, the the qubit isthen in statev.CS 294-2, Fall 2004, Lecture 1 201+=1√2(0+1)−=1√2(0−1)45◦θψ= cos θ0+ sin θ1h+|ψih−|ψiFigure 1:3.0.1 Measurement example I.Q: We measureψ=α0+β1in thev,v⊥basis, wherev= a0+b1. What is the probabilityof measuringv?A: First let’s do the simpler case a = b =1√2,
View Full Document