Quantam Computing Essay, Research Paper
What is quantum computing?
Quantum Computing is something that could have been thought up a long time ago – an idea whose time has come. For any physical theory one can ask: what sort of machines will do useful computation? or, what sort of processes will count as useful computational acts? Alan Turing thought about this in 1936 with regard (implicitly) to classical mechanics, and gave the world the paradigm classical computer: the Turing machine.
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 seeing what quantum mechanics means for computers and computing.
In a trivial sense, everything is a quantum computer. (A pebble is a quantum computer for calculating the constant-position function – you get the idea.) And of course, today’s computers exploit quantum effects (like electrons tunneling through barriers) to help do the right thing and do it fast. For that matter, both the computer and the pebble exploit a quantum effect – the “Pauli exclusion principle”, which holds up ordinary matter against collapse by bringing about the kind of degeneracy we call chemistry – just to remain stable solid objects. But quantum computing is much more than that.
The most exciting really new feature of quantum computing is quantum parallelism. A quantum 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 which classical-like state it’s “really” in. If that was all the superposition meant, you could drop all but one of the classical-like states (maybe only later, after you deduced retrospectively which one was “the right one”) and still get the time evolution right. But actually you need the whole superposition to get the time evolution right. The system really is in some sense in all the classical-like states at once! If the superposition can be protected from unwanted entanglement with its environment (known as decoherence), a quantum computer can output results dependent on details of all its classical-like states. This is quantum parallelism – parallelism on a serial machine. And if that wasn’t enough, machines that would already, in architectural terms, qualify as parallel can benefit from quantum parallelism too – at which point the mind begins to seriously boggle!
Why is Quantam Computing an exciting prospect:
Quantum computation is an exciting prospect, because a quantum computer (if it could be built) would be
exponentially faster than a classical computer on some problems. For example, a quantum computer could
find prime factors in polynomial time instead of the exponential time required by a classical computer,
thereby breaking conventional cryptographic codes.
The problem with building a quantum computer is that the quantum bits (called qubits) simultaneously
need to be protected from the environment so that they retain their quantum phase, but they need to be
coupled to the environment so that initial conditions can be loaded, the calculation applied, and the results
read out. Because of these apparently contradictory constraints, it’s taken a heroic experimental effort to
make just a 2 bit quantum computer. This has been done in systems such as trapped ions, or cavity
quantum electrodynamics, that carefully isolate the qubits and cool them to their ground state.
Neil Gershenfeld and Isaac Chuang have developed an entirely new approach to quantum computation
that promises to solve many of these problems. Instead of carefully isolating a small number of qubits, we
use a large thermal ensemble (such as a cup of coffee). Such a system has ~10^23 degrees of freedom;
by applying RF pulses that excite nuclear magnetic resonances, we can create a tiny deviation from
equilibrium that acts just like a much smaller number of pure qubits.
The nuclear spin is beautifully isolated from the environment; its spin coherence can last for thousands of
seconds. By representing the effective computational qubits in such an ensemble, we get these very long
coherence times permitting thousands of logical operations before coherence is lost. Further, because the
bits are represented in an ensemble, it is possible to continuously read out the quantum state (somthing
that is of course impossible for individual quantum degrees of freedom). Best of all, the most important
part of the experimental apparatus is built by nature in the form of ordinary molecules.
Implementing such a quantum computer requires the mature techniques of multiple pulse spin resonance.
Using existing NMR spectrometers it will be straightforward to reach about 10 qubits, enough to
demonstrate for the first time quantum superfast algorithms and quantum error correction, and to prepare
a range of unusual quantum states that have never been realized before (such as the
Greenberger-Horne-Zeilinger states that maximally violate Bell’s Theorem). The required instrumentation
even promises to scale down to the desktop, so that everyone could have a quantum co-processor.
what makes quantum computers so different from their classical counterparts
we begin the explanation by having a closer look at a basic chunk of information namely one bit. From a physical point of view a bit is a physical system which can be prepared in one of the two different states representing two logical values — no or yes, false or true, or simply 0 or
1. For example, in digital computers, the voltage between the plates in a capacitor represents a bit of information: a charged capacitor denotes bit value 1 and an uncharged capacitor bit value 0. One bit of information can be also encoded using two different polarisations of light or two different electronic states of an atom. However, if we choose an atom as a physical bit then quantum mechanics tells us that apart from the two distinct electronic states the atom can be also prepared in a coherent superposition of the two states. This means that the atom is both in state 0 and state 1. To get used to the idea that a quantum object can be in `two states at once’ it is helpful to consider the following experiment (Fig.A and B)
Let us try to reflect a single photon off a half-silvered mirror i.e. a mirror which reflects exactly half of the light which impinges upon it, while the remaining half is transmitted directly through it (Fig. A). Where do you think the photon is after its encounter with the mirror — is it in the reflected or in the transmitted beam? It seems that it would be sensible to say that the photon is either in the transmitted or in the reflected beam with the same probability. That is one might expect the photon to take one of the two paths choosing randomly which way to go. Indeed, if we place two photodetectors behind the half-silvered mirror in direct lines of the two beams, the photon will be registered with the same probability either in the detector 1 or in the detector 2. Does it really mean that after the half-silvered mirror the photon travels in either reflected or transmitted beam with the same probability 50%? No, it does not ! In fact the photon takes `two paths at once’. This can be demonstrated by recombining the two beams with the help of two fully silvered mirrors and placing another half-silvered mirror at their meeting point, with two photodectors in direct lines of the two beams (Fig. B). With this set up we can observe a truly amazing quantum interference phenomenon.
If it were merely the case that there were a 50% chance that the photon followed one path and a 50% chance that it followed the other, then we should find a 50% probability that one of the detectors registers the photon and a 50% probability that the other one does. However, that is not what happens. If the two possible paths are exactly equal in length, then it turns out that there is a 100% probability that the photon reaches the detector 1 and 0% probability that it reaches the other detector 2. Thus the photon is certain to strike the detector 1! It seems inescapable that the photon must, in some sense, have actually travelled both routes at once for if an absorbing screen is placed in the way of either of the two routes, then it becomes equally probable that detector 1 or 2 is reached (Fig. 1c). Blocking off one of the paths actually allows detector 2 to be reached; with both routes open, the photon somehow knows that it is not permitted to reach detector2, so it must have actually felt out both routes. It is therefore perfectly legitimate to say that between the two half-silvered mirrors the photon took both the transmitted and the reflected paths or, using more technical language, we can say that the photon is in a coherent superposition of being in the transmitted beam and in the reflected beam. By the same token an atom can be prepared in a superposition of two different electronic states, and in general a quantum two state system, called a quantum bit or a qubit, can be prepared in a superposition of its two logical states 0 and 1. Thus one qubit can encode at a given moment of time both 0 and 1.
Now we push the idea of superposition of numbers a bit further. Consider a register composed of three physical bits. Any classical register of that type can store in a given moment of time only one out of eight different numbers i.e the register can be in only one out of eight possible configurations such as 000, 001, 010, … 111. A quantum register composed of three qubits can store in a given moment of time all eight numbers in a quantum superposition (Fig. 2). This is quite remarkable that all eight numbers are physically present in the register but it should be no more surprising than a qubit being both in state 0 and 1 at the same time. If we keep adding qubits to the register we increase its storage capacity exponentially i.e. three qubits can store 8 different numbers at once, four qubits can store 16 different numbers at once, and so on; in general L qubits can store 2L numbers at once. Once the register is prepared in a superposition of different numbers we can perform operations on all of them. For example, if qubits are atoms then suitably tuned laser pulses affect atomic electronic states and evolve initial superpositions of encoded numbers into different superpositions. During such evolution each number in the superposition is affected and as the result we generate a massive parallel computation albeit in one piece of quantum hardware. This means that a quantum computer can in only one computational step perform the same mathematical operation on 2L different input numbers encoded in coherent superpositions of L qubits. In order to acomplish the same task any classical computer has to repeat the same computation 2L times or one has to use 2L different processors working in parallel. In other words a quantum computer offers an enormous gain in the use of computational resources such as time and memory.
But this, after all, sounds as yet another purely technological progress. It looks like classical computers can do the same computations as quantum computers but simply need more time or more memory. The catch is that classical computers need exponentially more time or memory to match the power of quantum computers and this is really asking for too much because an exponential increase is really fast and we run out of available time or memory very quickly. Let us have a closer look at this issue.
In order to solve a particular problem computers follow a precise set of instructions that can be mechanically applied to yield the solution to any given instance of the problem. A specification of this set of instructions is called an algorithm. Examples of algorithms are the procedures taught in elementary schools for adding and multiplying whole numbers; when these procedures are mechanically applied, they always yield the correct result for any pair of whole numbers. Some algorithms are fast (e.g. multiplication) other are very slow (e.g. factorisation, playing chess). Consider, for example, the following factorisation problem
? x ? = 29083
How long would it take you, using paper and pencil, to find the two whole numbers which should be written into the two boxes (the solution is unique)? Probably about one hour. Solving the reverse problem
127 x 129 = ? ,
again using paper and pencil technique, takes less tha
Skipping details of the computational complexity we only mention that computer scientists have a rigorous way of defining what makes an algorithm fast (and usable) or slow (and unusable). For an algorithm to be fast, the time it takes to execute the algorithm must increase no faster than a polynomial function of the size of the input. Informally think about the input size as the total number of bits needed to specify the input to the problem, for example, the number of bits needed to encode the number we want to factorise. If the best algorithm we know for a particular problem has the execution time (viewed as a function of the size of the input) bounded by a polynomial then we say that the problem belongs to class P. Problems outside class P are known as hard problems. Thus we say, for example, that multiplication is in P whereas factorisation is not in P and that is why it is a hard problem. Hard does not mean “impossible to solve” or “non-computable” — factorisation is perfectly computable using a classical computer, however, the physical resources needed to factor a large number are such that for all practical purposes, it can be regarded as intractable (see inset 1).
It worth pointing out that computer scientists have carefully constructed the definitions of efficient and inefficient algorithms trying to avoid any reference to a physical hardware. According to the above definition factorisation is a hard problem for any classical computer regardless its make and the clock-speed. Have a look at Fig.3 and compare a modern computer with its ancestor of the nineteenth century, the Babbage differential engine. The technological gap is obvious and yet the Babbage engine can perform the same computations as the modern digital computer. Moreover, factoring is equally difficult both for the Babbage engine and top-of-the-line connection machine; the execution time grows exponentially with the size of the number in both cases. Thus purely technological progress can only increase the computational speed by a fixed multiplicative factor which does not help to change the exponential dependance between the size of the input and the execution time. Such change requires inventing new, better algorithms. Although quantum computation requires new quantum technology its real power lies in new quantum algorithms which allow to exploit quantum superposition that can contain an exponential number of different terms. Quantum computers can be programed in a qualitatively new way. For example, a quantum program can incorporate instructions such as `… and now take a superposition of all numbers from the previous operations…’; this instruction is meaningless for any classical data processing device but makes lots of sense to a quantum computer. As the result we can construct new algorithms for solving problems, some of which can turn difficult mathematical problems, such as factorisation, into easy ones!
The story of quantum computation started as early as 1982, when the physicist Richard Feynman considered simulation of quantum-mechanical objects by other quantum systems[1]. However, the unusual power of quantum computation was not really anticipated untill the 1985 when David Deutsch of the University of Oxford published a crucial theoretical paper[2] in which he described a universal quantum computer. After the Deutsch paper, the hunt was on for something interesting for quantum computers to do. At the time all that could be found were a few rather contrived mathematical problems and the whole issue of quantum computation seemed little more than an academic curiosity. It all changed rather suddenly in 1994 when Peter Shor from AT&T’s Bell Laboratories in New Jersey devised the first quantum algorithm that, in principle, can perform efficient factorisation[3].This became a `killer application’ — something very useful that only a quantum computer could do. Difficulty of factorisation underpins security of many common methods of encryption; for example, RSA — the most popular public key cryptosystem which is often used to protect electronic bank accounts gets its security from the difficulty of factoring large numbers. Potential use of quantum computation for code-breaking purposes has raised an obvious question — what about building a quantum computer.
In principle we know how to build a quantum computer; we can start with simple quantum logic gates and try to integrate them together into quantum circuits. A quantum logic gate, like a classical gate, is a very simple computing device that performs one elementary quantum operation, usually on two qubits, in a given period of time[4]. Of course, quantum logic gates are different from their classical counterparts because they can create and perform operations on quantum superpositions (cf. inset 2). However if we keep on putting quantum gates together into circuits we will quickly run into some serious practical problems. The more interacting qubits are involved the harder it tends to be to engineer the interaction that would display the quantum interference. Apart from the technical difficulties of working at single-atom and single-photon scales, one of the most important problems is that of preventing the surrounding environment from being affected by the interactions that generate quantum superpositions. The more components the more likely it is that quantum computation will spread outside the computational unit and will irreversibly dissipate useful information to the environment. This process is called decoherence. Thus the race is to engineer sub-microscopic systems in which qubits interact only with themselves but not not with the environment.
Some physicists are pessimistic about the prospects of substantial experimental advances in the field[5]. They believe that decoherence will in practice never be reduced to the point where more than a few consecutive quantum computational steps can be performed. Others, more optimistic researchers, believe that practical quantum computers will appear in a matter of years rather than decades. This may prove to be a wishful thinking but the fact is the optimism, however naive, makes things happen. After all it used to be a widely accepted “scientific truth” that no machine heavier than air will ever fly !
So, many experimentalists do not give up. The current challenge is not to build a full quantum computer right away but rather to move from the experiments in which we merely observe quantum phenomena to experiments in which we can control these phenomena. This is a first step towards quantum logic gates and simple quantum networks.
Can we then control nature at the level of single photons and atoms? Yes, to some degree we can! For example in the so called cavity quantum electrodynamics experiments, which were performed by Serge Haroche, Jean-Michel Raimond and colleagues at the Ecole Normale Superieure in Paris, atoms can be controlled by single photons trapped in small superconducting cavities[6]. Another approach, advocated by Christopher Monroe, David Wineland and coworkers from the NIST in Boulder, USA, uses ions sitting in a radio-frequency trap[7]. Ions interact with each other exchanging vibrational excitations and each ion can be separately controlled by a properly focused and polarised laser beam.
Experimental and theoretical research in quantum computation is accelerating world-wide. New technologies for realising quantum computers are being proposed, and new types of quantum computation with various advantages over classical computation are continually being discovered and analysed and we believe some of them will bear technological fruit. From a fundamental standpoint, however, it does not matter how useful quantum computation turns out to be, nor does it matter whether we build the first quantum computer tomorrow, next year or centuries from now. The quantum theory of computation must in any case be an integral part of the world view of anyone who seeks a fundamental understanding of the quantum theory and the processing of information.
How quantum mechanics can be used to improve computation.
Our challenge: solving an exponentially difficult problem for a conventional computer—that of factoring a large number. As a prelude, we review the standard tools of computation, universal gates and machines. These ideas are then applied first to classical, dissipationless computers and then to quantum computers. A schematic model of a quantum computer is described as well as some of the subtleties in its programming. The Shor algorithm [1,2] for efficiently factoring numbers on a quantum computer is presented in two parts: the quantum procedure within the algorithm and the classical algorithm that calls the quantum procedure. The mathematical structure in factoring which makes the Shor algorithm possible is discussed. We conclude with an outlook to the feasibility and prospects for quantum computation in the coming years.
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 way to quantify how quickly a particular algorithm may solve a problem is to ask how the number of steps to complete the algorithm scales with the size of the “input” the algorithm is fed. For the factoring problem, this input is just the number N we wish to factor; hence the length of the input is . (The base of the logarithm is determined by our numbering system. Thus a base of 2 gives the length in binary; a base of 10 in decimal.) `Reasonable’ algorithms are ones which scale as some small-degree polynomial in the input size (with a degree of perhaps 2 or 3).
On conventional computers the best known factoring algorithm runs in steps [3]. This algorithm, therefore, scales exponentially with the input size . For instance, in 1994 a 129 digit number (known as RSA129 [3']) was successfully factored using this algorithm on approximately 1600 workstations scattered around the world; the entire factorization took eight months [4]. Using this to estimate the prefactor of the above exponential scaling, we find that it would take roughly 800,000 years to factor a 250 digit number with the same computer power; similarly, a 1000 digit number would require years (significantly lon ger than the age of the universe). The difficulty of factoring large numbers is crucial for public-key cryptosystems, such as ones used by banks. There, such codes rely on the difficulty of factoring numbers with around 250 digits.
Recently, an algorithm was developed for factoring numbers on a quantum computer which runs in steps where is small [1]. This is roughly quadratic in the input size, so factoring a 1000 digit number with such an algorithm would require only a few million steps. The implication is that public key cryptosystems based on factoring may be breakable.
To give you an idea of how this exponential improvement might be possible, we review an elementary quantum mechanical experiment that demonstrates where such power may lie hidden [5]. The two-slit experiment is prototypic for observing quantum mechanical behavior: A source emits photons, electrons or other particles that arrive at a pair of slits. These particles undergo unitary evolution and finally measurement. We see an interference pattern, with both slits open, which wholely vanishes if either slit is covered. In some sense, the particles pass through both slits in parallel. If such unitary evolution were to represent a calculation (or an operation within a calculation) then the quantum system would be performing computations in parallel. Quantum parallelism comes for free. The output of this system would be given by the constructive interference among the parallel computations.