Quantum computation is by far one of the mostpopular subjects in physics nowadays. Although it isa relatively young field of study, there is no denyingthat we have accomplished a fair amount of progress,with new developments and results presented every week.The basic idea of quantum computation is to finda system which can do anything a classical computerwould do – mainly, perform calculations and store theresults of those calculations – but using the incrediblyhuge potential of quantum physics, and then working onhow to implement algorithms in that quantum computer.The idea was first introduced in the 1980s, and we couldsay the matter became of real interest with Feynman’slecture in 1981. But why are quantum computers sodesirable?Classical computers can perform a wildly large numberand variety of operations. However, as we will discuss,they also have their limitations, particularly regardingto time. Although computer science tells us that a sys-tem as simple as a Turing machine can work out anyproblem that’s computable, in practice some algorithmswould take such humongous periods of time – we are talk-ing about millions of years – that we can consider themunfeasible or useless for our purposes. Quantum comput-ers can bring a solution to this. It can be proved thatquantum computers with just a few tens of qubits – wewill come to them later on – are as powerful as, or evenmore powerful than some of the most advanced comput-ers in the world, which need millions upon millions of bitsto operate. Developing an energy-efficient, full-workingquantum computer is then the goal of many researchersand international companies, as it would allow as to opento a wide range of new possibilities, making these – untilnow – impossible problems solvable once and for all.?Electronic address: [email protected]†Electronic address: [email protected]‡Electronic address: [email protected]§Electronic address:II. POSTULATES OF QUANTUM MECHANICSIn this section, we will just introduce the basicpostulates of quantum mechanics that we will be usingalong this short explanation of quantum computation.On its own, quantum mechanics just provides a mathe-matical and conceptual framework for the developmentof physical laws. That is, it does not tell you what lawsof physics will a particular system obey: each case hasits own laws and each quantum theory (Quantum Elec-trodynamics, Quantum Chromodynamics, etc) shouldprovide them. It will become clearer as we investigatethese postulates.First, we will introduce the postulate related to thestates that a system can be in and the space of thosestates:Postulate 1. Associated to any isolated physical systemthere is a separable Hilbert space known as the state spaceof the system. The system is completely described by itsstate vector, which is a unit vector in the system’s statespace.Quantum mechanics itself does not tell us for a givenphysical system what the state space of the system is.Figuring that out for a specific system is a difficult prob-lem for which there are many rules. For example, an as-pect of quantum electrodynamics is that it tells us whatstate spaces to use to give a quantum description of light-matter interaction. The most simple quantum systemthat can be considered is the qubit. A qubit lives ina two-dimensional state space and, assuming {|0i, |1i}form an orthonormal basis for that space, the most gen-eral state of that space can be written as:|?i = cos?2|0i + sin?2ei? |1i, (2.1)where ?, ? ? R. This can be seen as a vector in the Blochsphere, that is, the two free parameters can be regardedas angles and can be visualized as:2Figure 1: Bloch sphere for a qubit.We will take this qubit as our fundamental quantummechanical system and we will work with it for the firstsections. Then, we will see in the last section that, infact, there are systems that can be described in terms ofqubits.Also, this postulate reveals one of the peculiaritiesof quantum mechanics: quantum superposition. Clas-sically, a bit has to be in one of the two states 0 or1. However, in quantum mechanics that doesn’t holdany more: we can have 0 or 1 but also we can havestates like |?i = ?12(|0i + |1i) which have no classicalcounterpart. This is the first fundamental thing thatmakes quantum mechanics so counterintuitive, and itgives us the opportunity of making algorithms thatare more efficient than classical ones at solving someproblems.The next postulate, concerns the evolution of a quan-tum system:Postulate 2. The evolution of a closed system is de-scribed by a unitary transformation. That is, the state ofthe system at time t1 (|?(t1)i) is related to the state attime t2 (|?(t2)i) by a unitary operator U which dependsonly on times t1 and t2: |?(t2)i = U(t1, t2)|?(t1)i.Just as quantum mechanics doesn’t tell us the state ofspace, nor does it tell us which unitary operators descibereal world quantum dynamics. However, it turns outthat in the case of single qubits any unitary operator atall can be realized in realistic systems.This last postulate, relates the quantum state of aclosed quantum system at two different times. More gen-eral, this postulate can be extended to continous time (asit is presented generally in literature ) and can be refor-mulated by saying that the state of a closed quantumsystem is described by the Schr ?odinger equation:i~ddt |?(t)i = H |?(t)i, (2.2)where H is the Hamiltionian operator (which must behermitian) and ~ is Planck’s constant. That is, given|?(0)i we can solve the differential equation in orderto have the state of the system at arbitrary time. Inthe most simple case, the hamiltonian is independent oftime and then, the unitary operator that appears in thesecond postulate will just be U(t1, t2) = e?iH(t2?t1)~ . Itcan be checked easily that U is unitary since H must behermitian, and so the exponential of an anti-hermitianoperator is necessarily unitary. In the general case thatH = H(t) and the commutator of the hamiltonian atdifferent times is not zero ( H(t1), H(t2) 6= 0 ) theexpression becomes more complicated (it involves theordered product of the exponential of the integral of thehamiltonian) and we will not treat it.Once we have the states and its evolution, the next pos-tulate answers a question that emerges naturally : whatwe will found when we perform a measurement in our sys-tem? There exist a general theory concerning measure-ments, which includes not just what we will introducehere but a more general framework including POVMs asexplained in 1. Also, what is called the measurementproblem in quantum mechanics is far to be a closed topic,existing many different approaches which are consistentwith the experimental results.Postulate 3. Given a physical system, observables arerepresented by self-adjoint operators (or Hermitian whichin the case of finite dimensional spaces, those we willmainly treat, is the same). When a measure of an ob-servable represented by the operator A is performed onthe state |?i, the possible outcomes are the eigenvalues{ai} of A, with probability Pk| hai,k|?i |2each, wherethe sum is over the whole proper subspace associated tothe eigenvalue. After a measurement is performed, thestate is left in the projection of the initial state onto theproper subspace of the eigenvalue and normalized to theunit as Postulate 1 requires.Once we know this, the last postulate which can beconsidered as an addition to the first one, just tells ushow to combine different systems in order to describethem in the framework of quantum mechanics. How-ever, this postulate contains the second thing that canjust be explained by quantum mechanics: the non-localcorrelations which turn out to be a consequence of entan-glement, a concept in the heart of quantum mechanics,quantum information and quantum technologies such asquantum computation. We will explain it after present-ing the fourth postulate:Postulate 4. The state space of a composite physicalsystem is the tensor product of the state spaces of thecomponent physical subsystem. Moreover, if we have sys-tems numbered 1 through n, and system i is prepared in3the state |?ii, then the joint state of the total system is|?1i ? |?2i ? … ? |?ni.We will use indistinctively these notations:|uvi ? |vi |ui ? |ui ? |vi. Also, the nature of en-tanglement is the fact that there are states in V ? W(where V and W are both vector spaces) that can notbe expressed as |vi ? |wi with |vi ? V and |wi ? W.When that happens to a particular state, we say it isentangled. Because of that, the whole state cannot bedescribed in general in terms of independent vectors:just one vector describes the whole state. That is theother peculiarity of quantum mechanics that took manyyears to be assimilated: since the publication of the threepapers that consolidated quantum mechanics in the halftwenties by Jordan, Heisenberg and Born to Aspect’sexperiments showing what Bell predicted: quantummechanics had non-local correlations that couldn’t beexplained classically and were stronger than the classicalones.Quantum mechanics can be reformulated in terms ofthe so called density matrices, which are operators thatdescribe the state of systems. Its importance is that theycodify what we might call the classical uncertainty (inthe same way as the probability density used in classicalstatistical mechanics), that is, they do not introduceanything new from a conceptual point of view. If thereis no such uncertainty, the formalism of density matrixand the vector state are equivalent (since ? = |?i h?|for that case) so we will not use them. These cases arecalled pure states in contrast to the mixed states thatcan not be described by state vectors. One notoriousproperty is the fact that if we have a composite systemin an entangled state, we can just focus on a subsystemat the prize of having a mixed state for it. Therefore,we cannot describe it by a state vector anymore and wehave to use this new tool we have conceptually described.Equipped with the formalism of quantum mechanics,we will now move on to classical computing for a whilebefore showing how to take advantage of this frameworkin order to perform calculations that for a classical com-puter would take more than the age of the universe todo.III.