Why Quantum Computation?Basic Quantum MechanicsThe superposition principleMeasurement PrincipleQubitsMeasurement example I.Measurement example II.Two qubits:EPR Paradox:Bell's InequalityCS 294-2 Introduction, Axioms, Bell Inequalities 1/17/07Spring 2007 Lecture 11 Why Quantum Computation?• Quantum computers are the only model of computation that escape the limitations on computationimposed by the extended Church-Turing thesis. These theoretical limitations will soon have practicalconsequences as Moore’s Law (the doubling every eighteen months in transistor density on chips andthe resulting increase in computer speed) is expected in a decade or so to run into inherent (classical)physical limits such as transistors scaling down to the size of elementary particles.• Quantum computers would have a profound effect on complexity based cryptography, via the poly-nomial time quantum algorithms for factoring and discrete logs. Understanding how to meet thesethreats by designing quantum resistant cryptosystems or by resorting to quantum cryptography is amajor challenge.• Quantum computation has brought about a renaissance in the examination of the foundations of quan-tum mechanics: highlighting phenomena such as entanglement and the resulting exponential powerinherent in quantum physics, and showing that quantum error-correcting codes may be used to bringstability into the seemingly inherently unstable quantum world.• Lastly, the study of quantum computation has helped broaden and deepen our insights into complexitytheory (and tools such as Fourier analysis and information theory), and in a few cases helped resolveopen questions in classical complexity theory.2 Basic Quantum MechanicsThe basic formalism of quantum mechanics is very simple, though understanding and interpreting the re-sults is much more challenging. There are three basic principles, enshrined in the three basic postulates ofquantum mechanics:• The superpostion principle: this axiom tells us what the state of a quantum system looks like.* An addendum to this axiom tells us given two subsystems, what the allowable states of the compostesystem are.• The measurement principle: this axiom governs how much information about the state we can access.• Unitary evolution: this axiom governs how the state of the quantum system evolves in time.2.1 The superpositio n principleConsider a system with k distinguishable states. For example, the electron in an atom might be either in itsground state or one of k −1 excited states, each of progressively higher energy. As a classical system, wemight use the state of this system to store a number between 0 and k −1. The superposition principle saysthat if a quantum system is allowed to be any one of number of different states then it can also be placed in aCS 294-2, Spring 2007, Lecture 1 1linear superposition of these states with complex coefficients. Thus the quantum state of the k-state systemabove is described by a sequence of k complex numbersα0,...,αk−1∈ C .αjis said to be the (complex)amplitude with which the system is in state j. We will require that the amplitudes are normalized so that∑j|αj|2= 1. It is natural to write the state of the system as a k dimensional vector:α0α1..αk−1The normalization on the complex amplitudes means that the state of the system is a unit vector in a kdimensional complex vector space — called a Hilbert space.In quantum mechanics it is customary to use the Dirac’s ket notation to write vectors. As we shall see later,this is a particularly useful notation in the context of quantum computation. In the ket notation, the abovestate is written as:ψ=k−1∑j=0αjjHere0=10..0andk −1=00..1. The Dirac notation has the advantage that the it labels the basisvectors explicitly. This is very convenient because the notation expresses both that the state of the quantumsystem is a vector, while at the same time it represents a number (in superposition) describing the physicalquantity of interest (energy level, spin, polarization, etc). In the context of quantum computation and quan-tum information it is data (0 or 1) to be processed. The {0,1,...,k−1} basis is called the standardbasis.2.2 Measurement PrincipleThis linear superpositionψ=∑k−1j=0αjjis part of the private world of the electron. For us to know theelectron’s state, we must make a measurement. Measuringψin the standard basis yields j with probability|αj|2.One important aspect of the measurement process is that it alters the state of the quantum system: the effectof the measurement is that the new state is exactly the outcome of the measurement. I.e., if the outcomeof the measurement is j, then following the measurement, the qubit is in statej. This implies that youcannot collect any additional information about the amplitudesαjby repeating the measurement. Thisproperty forms the basis of quantum cryptography where the presence of an eavesdropper necessarily altersthe quantum state being transmitted.Intuitively, a measurement provides the only way of reaching into the Hilbert space to probe the quantumstate vector. In general this is done by selecting an orthonormal basise0,...,ek−1. The outcome of themeasurement isej(or j) with probability equal to the square of the length of the projection of the statevectorψonej. A consequence of performing the measurement is that the new state vector isej. Thusmeasurement may be regarded as a probabilistic rule for projecting the state vector onto one of the vectorsof the orthonormal measurement basis.CS 294-2, Spring 2007, Lecture 1 22.3 QubitsThe basic entity of quantum information is a qubit (pronounced “cue-bit”), or a quantum bit. This corre-sponds to a 2-state quantum system, and its state can be written as a unit (column) vectorαβ∈ C2. InDirac notation, this may be written as:ψ=α0+β1α,β∈C and |α|2+ |β|2= 1This 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 yields 0 withprobability |α|2, and 1 with probability |β|2.As we noted above, the
View Full Document
Unlocking...