[attachment=8929]
Quantum Computing
Abstract
Imagine a computer whose memory is exponentially larger than its apparent physicalsize; a computer that can manipulate an exponential set of inputs simultaneously; acomputer that computes in the twilight zone of Hilbert space. You would be thinking of aquantum computer. Relatively few and simple concepts from quantum mechanics areneeded to make quantum computers a possibility. The subtlety has been in learning tomanipulate these concepts. Is such a computer an inevitability or will it is too difficult tobuild?The subject of quantum computing brings together ideas from classical informationtheory, computer science, and quantum physics. This review aims to summarize not justquantum computing, but the whole subject of quantum information theory. It turns outthat information theory and quantum mechanics fit together very well. In order to explaintheir relationship, the review begins with an introduction to classical information theoryand computer science, including Shannon's theorem, error correcting codes, Turingmachines and computational complexity. The principles of quantum mechanics are thenoutlined, and the EPR experiment described. The EPR-Bell correlations and quantumentanglement in general, form the essential new ingredient which distinguishes quantumfrom classical information theory, and, arguably, quantum from classical physics. Basicquantum information ideas are described, including key distribution, teleportation, datacompression, quantum error correction, the universal quantum computer and quantumalgorithms. The common theme of all these ideas is the use of quantum entanglement as acomputational resource. Experimental methods for small quantum processors are brieflysketched, concentrating on ion traps, high Q cavities, and NMR. The review concludeswith an outline of the main features of quantum information physics, and avenues forfuture research.
Introduction
What is quantum computing?
It's something that could have been thought up a long timeago - an idea whose time has come. For any physical theory one can ask: what sort ofmachines will do useful computation? or, what sort of processes will count as usefulcomputational acts? Alan Turing thought about this in 1936 with regard (implicitly) toclassical mechanics, and gave the world the paradigm classical computer: the Turingmachine.But even in 1936 classical mechanics was known to be false. Work is now under way -mostly theoretical, but tentatively, hesitantly groping towards the practical - in seeingwhat quantum mechanics means for computers and computing.The basic idea behind quantum computing in the merging of computer science,information theory and quantum mechanics from classical physics for better efficiency ofoperation of systems. Information is the most important element of any system.Information can be represented in many ways. It can be analyzed provided we know howit was encoded. For example, the two statements ``the quantum computer is veryinteresting'' and ``l'ordinateur quantique est tres interessant'' have something in common,although they share no words. The thing they have in common is their informationcontent. Essentially the same information could be expressed in many other ways, forexample by substituting numbers for letters in a scheme such as a -> 97, b -> 98, c -> 99and so on, in which case the English version of the above statement becomes 116 104101 32 113 117 97 110 116 117 109... . It is very significant that information can beexpressed in different ways without losing its essential nature, since this leads to thepossibility of the automatic manipulation of information: a machine need only be able tomanipulate quite simple things like integers in order to do surprisingly powerfulinformation processing, from document preparation to differential calculus, even totranslating between human languages. We are familiar with this now, because of theubiquitous computer, but even fifty years ago such a widespread significance ofautomated information processing was not foreseen.However, there is one thing that all ways of expressing information must have incommon: they all use real physical things to do the job. Spoken words are conveyed byair pressure fluctuations, written ones by arrangements of ink molecules on paper, eventhoughts depend on neurons (Landauer 1991). The rallying cry of the informationphysicist is ``no information without physical representation!'' Conversely, the fact thatinformation is insensitive to exactly how it is expressed, and can be freely translated fromone form to another, makes it an obvious candidate for a fundamentally important role inphysics, like energy and momentum and other such abstractions. However, until thesecond half of this century, the precise mathematical treatment of information, especiallyinformation processing, was undiscovered, so the significance of information in physicswas only hinted at in concepts such as entropy in thermodynamics. It now appears thatinformation may have a much deeper significance. Historically, much of fundamentalphysics has been concerned with discovering the fundamental particles of nature and theequations which describe their motions and interactions. It now appears that a differentprogramme may be equally important: to discover the ways that nature allows, andprevents, information to be expressed and manipulated, rather than particles to move. Forexample, the best way to state exactly what can and cannot travel faster than light is toidentify information as the speed-limited entity. In quantum mechanics, it is highlysignificant that the state vector must not contain, whether explicitly or implicitly, moreinformation than can meaningfully be associated with a given system. Among otherthings this produces the wave function symmetry requirements which lead to BoseEinstein and Fermi Dirac statistics, the periodic structure of atoms, and so on.The history of computer technology has involved a sequence of changes from one type ofphysical realization to another --- from gears to relays to valves to transistors tointegrated circuits and so on. Today's advanced lithographic techniques can squeezefraction of micron wide logic gates and wires onto the surface of silicon chips. Soon theywill yield even smaller parts and inevitably reach a point where logic gates are so smallthat they are made out of only a handful of atoms. On the atomic scale matter obeys therules of quantum mechanics, which are quite different from the classical rules thatdetermine the properties of conventional logic gates. So if computers are to becomesmaller in the future, new, quantum technology must replace or supplement what we havenow. The point is, however, that quantum technology can offer much more thancramming more and more bits to silicon and multiplying the clock-speed ofmicroprocessors. It can support entirely new kind of computation with qualitatively newalgorithms based on quantum principles!A bit is a fundamental unit of information, classically represented as a 0 or 1 in yourdigital computer. Each classical bit is physically realized through a macroscopic physicalsystem, such as the magnetization on a hard disk or the charge on a capacitor. Adocument, for example, comprised of n-characters stored on the hard drive of a typicalcomputer is accordingly described by a string of 8n zeros and ones. Herein lies a keydifference between your classical computer and a quantum computer. Where a classicalcomputer obeys the well understood laws of classical physics, a quantum computer is adevice that harnesses physical phenomenon unique to quantum mechanics (especiallyquantum interference) to realize a fundamentally new mode of information processing.In a quantum computer, the fundamental unit of information (called a quantum bit orqubit), is not binary but rather more quaternary in nature. This qubit property arises as adirect consequence of its adherence to the laws of quantum mechanics which differradically from the laws of classical physics. A qubit can exist not only in a statecorresponding to the logical state 0 or 1 as in a classical bit, but also in statescorresponding to a blend or superposition of these classical states. In other words, a qubitcan exist as a zero, a one, or simultaneously as both 0 and 1, with a numerical coefficientrepresenting the probability for each state. This may seem counterintuitive becauseeveryday phenomenon is governed by classical physics, not quantum mechanics -- whichtakes over at the atomic level.To explain what makes quantum computers so different from their classical counterpartswe begin by having a closer look at a basic chunk of information namely one bit. From aphysical point of view a bit is a physical system which can be prepared in one of the twodifferent states representing two logical values --- no or yes, false or true, or simply 0 or 1For example, in digital computers, the voltage between the plates in a capacitorrepresents a bit of information: a charged capacitor denotes bit value 1 and an unchargedcapacitor bit value 0. One bit of information can be also encoded using two differentpolarizations of light or two different electronic states of an atom. However, if we choosean atom as a physical bit then quantum mechanics tells us that apart from the two distinctelectronic states the atom can be also prepared in a coherent superposition of the twostates. This means that the atom is both in state 0 and state 1.
Experimental validation
In an experiment like that in figure a, where a photon is fired at a half-silvered mirror, itcan be shown that the photon does not actually split by verifying that if one detectorregisters a signal, then no other detector does. With this piece of information, one mightthink that any given photon travels vertically or horizontally, randomly choosing betweenthe two paths. However, quantum mechanics predicts that the photon actually travelsboth paths simultaneously, collapsing down to one path only upon measurement. Thiseffect, known as single-particle interference, can be better illustrated in a slightly moreelaborate experiment, outlined in figure b.Figure b depicts an interesting experiment that demonstrates the phenomenon of singleparticleinterference. In this case, experiment shows that the photon always reachesdetector A, never detector B! If a single photon travels vertically and strikes the mirror,then, by comparison to the experiment in figure a, there should be an equal probabilitythat the photon will strike either detector A or detector B. The same goes for a photontraveling down the horizontal path. However, the actual result is drastically different.The only conceivable conclusion is therefore that the photon somehow traveled bothpaths simultaneously; creating interference at the point of intersection that destroyed thepossibility of the signal reaching B. This is known as quantum interference and resultsfrom the superposition of the possible photon states, or potential paths. So although onlya single photon is emitted, it appears as though an identical photon exists and travels the'path not taken,' only detectable by the interference it causes with the original photonwhen their paths come together again. If, for example, either of the paths are blockedwith an absorbing screen, then detector B begins registering hits again just as in the firstexperiment! This unique characteristic, among others, makes the current research inquantum computing not merely a continuation of today's idea of a computer, but rather anentirely new branch of thought. And it is because quantum computers harness thesespecial characteristics that give them the potential to be incredibly powerfulcomputational devices.The most exciting really new feature of quantum computing is quantum parallelism. Aquantum system is in general not in one "classical state", but in a "quantum state"consisting (crudely speaking) of a superposition of many classical or classical-like states.This superposition is not just a figure of speech, covering up our ignorance of whichclassical-like state it's "really" in. If that was all the superposition meant, you could dropall but one of the classical-like states (maybe only later, after you deduced retrospectivelywhich one was "the right one") and still get the time evolution right. But actually youneed the whole superposition to get the time evolution right. The system really is in somesense in all the classical-like states at once! If the superposition can be protected fromunwanted entanglement with its environment (known as decoherence), a quantumcomputer can output results depending on details of all its classical-like states. This isquantum parallelism - parallelism on a serial machine. And if that wasn't enough,machines that would already, in architectural terms, qualify as parallel can benefit fromquantum parallelism too - at which point the mind begins to seriously boggle!
The Potential and Power of Quantum Computing
Let us start by describing the problem at hand: factoring a number N into its prime factors(e.g., the number 51688 may be decomposed as ). A convenient wayto quantify how quickly a particular algorithm may solve a problem is to ask how thenumber of steps to complete the algorithm scales with the size of the ``input'' thealgorithm is fed. For the factoring problem, this input is just the number N we wish tofactor; hence the length of the input is . (The base of the logarithm is determined byour numbering system. Thus a base of 2 gives the length in binary; a base of 10 indecimal.) `Reasonable' algorithms are ones which scale as some small-degree polynomialin the input size (with a degree of perhaps 2 or 3).On conventional computers the best known factoring algorithm runs insteps. This algorithm, therefore, scalesexponentially with the input size . For instance, in 1994 a 129 digit number(known as RSA129) was successfully factored using this algorithm on approximately1600 workstations scattered around the world; the entire factorization took eight months .Using this to estimate the prefactor of the above exponential scaling, we find that itwould take roughly 800,000 years to factor a 250 digit number with the same computerpower; similarly, a 1000 digit number would require years (significantly lon ger thanthe age of the universe). The difficulty of factoring large numbers is crucial for publickeycryptosystems, such as ones used by banks. There, such codes rely on the difficulty