Divya K Quantum Computers

Seminar 2004

1

Quantum computers

INTRODUCTION The acceleration of computing power never seems slow. With each blink of an eye, there’s a new, faster processor or a better data-storage-intensive hard drive. But for all their computational might, computers as we know them will eventually bump up against the laws of physics. Technology marches on resolutely, shrinking electronic components and cramming more circuitry onto smaller and smaller wafers of silicon. If the current rate of miniaturization continues, computer experts predict that within a decade or two, transistors will dwindle to the size of an atom. But at those dimensions, well-behaved, predictable classical behavior goes out the window, and the slippery, untenable nature of quantum mechanics takes over. In the quantum world, rather than being entities with sharply defined positions and motions, particles are described by spread-out wavefunctions, seemingly existing in many places at once. So it might seem that the power of computers is destined to reach a limit. But scientists usually don't take such pronouncements at face value--in this case, they have long been aware of a way around this apparent constraint. For within the shadowy quantum world there is more potential computing power than the speediest processor could ever dream of. That power stems from quantum particles' capability for existing in more than one state, as well as their ability to become inextricably linked to each other by a phenomenon known as entanglement. Traditional computers perform calculations, however quickly, in a basically sequential manner. Their limitations surface in the simple, yet striking, example of factoring a large number. The time a computer spends searching for a number's factors increases astronomically with the size of the number. To factor a 400-digit number, for example, would take a modern computer billions of years. On the other hand, a computer made of quantum particles has a built-in parallelism because quantum calculations can be performed on the particles' coexisting states simultaneously. A quantum computer, then, might factor that 400-digit number in minutes. Such a completely different approach to computing, it seems, truly earns the designation "paradigm shift."

Department of ECE

GEC, Thrissur

Seminar 2004

2

Quantum computers

MOORE'S LAW AND THE FUTURE OF COMPUTERS

In 1965 Intel co-founder Gordan Moore noted that processing power (number of transistors and speed) of computer chips was doubling each 18 months or so. This trend has continued for nearly 4 decades. The basic processing unit in a computer chip is the transistor which acts like a small switch. The binary digits 0 and 1 are represented by the transistor being turned off or on. Currently thousands of electrons are used to drive each transistor. As the processing power increases, the size of each transistor reduces. If Moore's law continues unabated, then each transistor is predicted to be as small as a hydrogen atom by about 2030. At the size the quantum nature of electrons in the atoms becomes significant. It generates errors in the computation.

Department of ECE

GEC, Thrissur

Seminar 2004

3

Quantum computers

However, rather than be a hindrance, it is possible to exploit the quantum physics as a new way to do computation. And this new way opens up fantastic new computational power based on the wave nature of quantum particles.

PARTICLE-WAVE DUALITY

We normally think of electrons, atoms and molecules as particles. But each of these objects can also behave as waves. This dual particle-wave behaviour was first suggested in the 1920's by Louis de Broglie.

This concept emerged as follows. Thomas Young's experiment with double slits in the early 1800’s show that light behaves as if it is a wave. But, strikingly, Einstein's explanation of the photoelectric effect in 1905 shows that light consists of particles. In 1923 de Broglie suggested this dual particle-wave property might apply to all particles including electrons. Then in 1926 Davisson and Germer found that electrons scattered off a crystal of nickel behaved as if they were waves. Since then neutrons, atoms and even molecules have been shown to behave as waves. The waves tell us where the particle is likely to be found.

This dual particle-wave property is exploited in quantum computing in the following way. A wave is spread out in space. In particular, a wave can spread out over two different places at once. This means that a particle can also exist at two places at once. This concept is called the superposition principle - the particle can be in a superposition of two places.

Department of ECE

GEC, Thrissur

Seminar 2004

4

Quantum computers

SUPERPOSITIONING Superpositioning is a big word for an old concept: that two things can overlap each other without interfering with each other. In classical computers, electrons cannot occupy the same space at the same time, but as waves, they can. 1. Superposition in waves Figure is an illustration of two super-imposed waves A and B To add these waves together numerically, S = A + B, the result would be a wave that looks like neither of its components. However, one could retrieve either wave be subtracting out the other, as shown. (The wave form S, is shown as dotted to indicate that it is only the apparent wave form; the actual wave form is the combination of two different waves. In the quantum world, the combined wave form is a set of amplitude probabilities.)

Department of ECE

GEC, Thrissur

Seminar 2004

5

Quantum computers

2.Superposition in linked list pointers For an example germane to computer programming, one may look at a data structure called a linked list. Each data node in the list contains a reference, or pointer, to the next data node. The program traverses the list by jumping to the next data node indicated by the pointer. In a doubly-linked list, the data node contains two pointers, one for traversing to the top of the list, and another for traversing to the bottom of the list. Another way of implementing a doubly-linked list is to use a single pointer space that contains the exclusive-or (XOR) or the two adjacent pointers. Following Figure shows a linked list node with pointer S that is the XOR of reference A (before) and reference B( after). To traverse the linked list upward, the program XORs the current pointer (S) with the one it just left (B), and the result is the pointer of the next node (A). The same process works when traversing down the list. This superpositioning of node pointers is analogous to the water wave superposition example above, and is how the quantum states are maintained simultaneously in a quantum bit.

Department of ECE

GEC, Thrissur

Seminar 2004

6

Quantum computers

BITS AND QUBITS

The basic data unit in a conventional (or classical) computer is the bit, or binary digit. A bit stores a numerical value of either 0 or 1. An example of how bits are stored is given by a CD ROM: ``pits'' and ``lands'' (absence of a pit) are used to store the binary data. In the solidstate world of classical computers, the bit's value corresponds to the presence or absence of current. Bits can be manipulated by what are known as logic gates, which transform bit values in designed ways. For example, a NOT gate changes a bit from 0 to 1, or vice versa. In fact, everything a computer does, from word processing to modeling the structure of the universe, can be boiled down to various combinations of these simple logic gates operating on bits. We could also represent a bit using two different electron orbits in a single atom. In most atoms there are many electrons in many orbits. But we need only consider the orbits available to a single outermost electron in each atom .The figure on the right shows two atoms representing the binary number 10.The inner orbits represent the number 0 and the outer orbits represent the binary number 1. The position of the electron gives the number We coul

. The figure shows two atoms representing the binary number 10. The inner orbits represent the number 0 and the outer orbits represent the binary number 1. The position of the electron gives the number stored by the atom.

Department of ECE

GEC, Thrissur

Seminar 2004

7

Quantum computers

However; a completely new possibility opens up for atoms. Electrons have a wave property which allows a single electron to be in two orbits simultaneously. In other words, the electron can be in a superposition of both orbits. The figure on the left shows two atoms each with a single electron in a superposition of two orbits. Each atom represents the binary numbers 0 and 1 simultaneously. The two atoms together represent the 4 binary numbers 00, 01, 10 and 11e simultaneously n orbits

To distinguish this new kind data storage from a conventional bit, it is called a quantum bit which is shortened to qubit. Each atom in the figure above is a qubit. The key point is that a qubit can be in a superposition of the two numbers 0 and 1. Superposition states allow many computations to be performed simultaneously, and give rise to what is known as quantum parallelism.

Department of ECE

GEC, Thrissur

Seminar 2004

8

Quantum computers

EXAMPLE OF QUBIT Another example of a qubit is a photon (a particle of light) traveling along two possible paths. Consider what happens when a photon encounters a beam splitter. A beam splitter is just like an ordinary mirror, however the reflective coating is made so thin that not all light is reflected and some light is transmitted through the mirror as well. When a single photon encounters a beam splitter, the photon emerges in a superposition of the reflected path and the transmitted path. One path is taken to be the binary number 0, and the other path is taken to be the number 1. The photon in a superposition of both paths and so represents both 0 and 1 simultaneously.

.

Many quantum-sized systems or particles have two possible configurations that could

correspond to the 0 or 1 of a bit: the up or down spin of an electron or a nucleus, for example, or the polarization of a photon. But here, the quantum system departs from its classical cousin. A quantum bit, otherwise known as a qubit, can be set up to exist in both the 0 and 1 states at the same time. According to rules of quantum mechanics, the qubit will stay in this superposition of values until it is measured, at which point it "collapses" into a definite value.

Department of ECE

GEC, Thrissur

Seminar 2004

9

Quantum computers

ANALYTICAL TREATMENT The basic distinguishing feature of a quantum computer is its ability to operate simultaneously on a collection of classical states, thus potentially performing many operations in the time a classical computer would do just one. Alternatively, this quantum parallelism can be viewed as a large parallel computer requiring no more hardware than that needed for a single processor. On the other hand, the range of allowable operations is rather limited. To describe this more concretely, we adopt the conventional ket notation from quantum mechanics to denote various states. That is, we use

to denote the state of a computer described by

. At a low level of description, the state of a classical computer is described by values of its bits. So for instance if it has n bits, then there are

possible states for the machine, which can be

associated with the numbers

. We then say the computer is in state

values of its bits correspond to the number

when the

. More commonly, a computer is described in terms

of higher level constructs formed from groups of bits, such as integers, character strings, sets and addresses of variables in a program. For example, a state that could arise during a search is corresponding to a set of assignments for variables in a CSP and a value of false for the program variable soln, e.g., used to represent whether a solution has been found. In these higher level descriptions, there will often be aspects of the computer's state, e.g., stack pointers or values for various iteration counters, that are not explicitly mentioned. The states presented so far, where each bit or higher-level construct has a definite value, apply both to classical and quantum computers. However, quantum computers have a far richer set of possible states. Specifically, if

are the possible states for a classical computer, the

possible states of the corresponding quantum computer are all linear superpositions of these states, i.e., states of the form the state

where is a complex number called the amplitude associated with

. The physical interpretation of the amplitudes comes from the measurement process.

When a measurement is made on the quantum computer in state , e.g., to determine the result of the computation represented by a particular configuration of the bits in a register, one of the possible classical states is obtained. Specifically, the classical state

Department of ECE

is obtained with probability

.

GEC, Thrissur

Seminar 2004

10

Quantum computers

Furthermore, the measurement process changes the state of the computer to exactly match the result. That is, the measurement is said to collapse the original superposition to the new superposition consisting of the single classical state (i.e., the amplitude of the returned state is 1 and all other amplitudes are zero). This means repeated measurements will always return the same result. An important consequence of this interpretation results from the fact that probabilities must sum to one. Thus the amplitudes of any superposition of states must satisfy the normalization condition ∑‫׀‬ψi‫׀‬2 =1 Another consequence is that the full state of a quantum computer, i.e., the superposition, is not itself an observable quantity. Nevertheless, by changing the amplitude associated with different classical states, operations on the superposition can affect the probability with which various states are observed. This possibility is crucial for exploiting quantum computation, and makes it potentially more powerful than probabilistic classical machines, in which some choices in the program are made randomly. These superpositions can also be viewed as vectors in a space whose basis is the individual classical states

and is the component of the vector along the i basis element of the

space. Such a state vector can also be specified by its components as understood from context. The inner product of two such vectors is the complex conjugate of . In matrix notation, this can also be written as

when the basis is where denotes where is treated as a

column vector and is a row vector given by the transpose of with all entries changed to their complex conjugate values. For these vectors, the normalization condition amounts to requiring that .

Department of ECE

GEC, Thrissur

Seminar 2004

11

Quantum computers

To complete this overview of quantum computers, it remains to describe how superpositions can be used within a program. In addition to the measurement process described above, there are two types of operations that can be performed on a superposition of states. The first type is to run classical programs on the machine, and the second allows for creating and manipulating the amplitudes of a superposition. In both these cases, the key property of the superposition is its linearity: an operation on a superposition of states gives the superposition of that operation acting on each of those states individually. As described below, this property, combined with the normalization condition, greatly limits the range of physically realizable operations. In the first case, a quantum computer can perform a classical program provided it is reversible, i.e., the final state contains enough information to recover the initial state. One way to achieve this is to retain the initial input as part of the output. To illustrate the linearity of operations, consider some reversible classical computation on these states, e.g.,

which produces a new state

from a given input one. When applied to a superposition of states, the result is

.

Why is reversibility required? Suppose the procedure f is not reversible, i.e., it maps at least two distinct states to the same result. For example, suppose linearity requires that

. Then for the superposition giving

, a superposition that

violates the normalization condition. Thus this irreversible classical operation is not physically realizable on a superposition, i.e., it cannot be used with quantum parallelism. In contrast to this use of computations on individual states, the second type of operation modifies the amplitude of various states within a superposition. That is, starting from the operation, denoted by U, creates a new superposition

. Because the

operations are linear with respect to superpositions, the new amplitudes can be expressed in terms of the original ones by

, or in matrix notation by

. That is, linearity means that an

operation changing the amplitudes can be represented as a matrix. To satisfy the normalization condition, , this matrix must be such that , suppose

is the j unit vector, corresponding to the superposition

where all amplitudes are zero except for the diagonal elements of

Department of ECE

. To see what this implies about the matrix . In this case

which must equal one That is,

must all be equal to one.

GEC, Thrissur

Seminar 2004

For

12

with

Quantum computers

,

This must equal one and we already know that the diagonal terms equal one. Thus we conclude

. A similar argument using

value for the second amplitude, gives matrix, so

, a superposition with an imaginary . Together these conditions mean that A is the identity

, i.e., the matrix U must be unitary to operate on superpositions. Restriction to

linear unitary operations arises directly from the linearity of quantum mechanics and the normalization condition for probabilities. Reversible classical programs, unitary operations on the superpositions and the measurement process are the basic ingredients used to construct a program for a quantum computer. As used in the search algorithm described below, such a program consists of first preparing an initial superposition of states, operating on those states with a series of unitary matrices in conjunction with a classical program to evaluate the consistency of various states with respect to the search requirements, and then making a measurement to obtain a definite final answer. The amplitudes of the superposition just before the measurement is made determine the probability of obtaining a solution. The overall structure is a probabilistic Monte Carlo computation in which at each trial there is some probability to get a solution, but no guarantee. This means the search method is incomplete: it can find a solution if one exists but can never guarantee a solution doesn't exist. An alternate conceptual view of these quantum programs is provided by the path integral approach to quantum mechanics In this view, the final amplitude of a given state is obtained by a weighted sum over all possible paths that produce that state. In this way, the various possibilities involved in a computation can interfere with each other, either constructively or destructively. This differs from the classical combination of probabilities of different ways to reach the same outcome the probabilities are simply added, giving no possibility for interference. Interference is also seen in classical waves But these systems lack the capability of quantum parallelism. The various formulations of quantum mechanics, involving operators, matrices or sums over paths are equivalent but suggest different intuitions about constructing possible quantum algorithms.

Department of ECE

GEC, Thrissur

Seminar 2004

13

Quantum computers

QUBIT SYSTEMS

The following describes some systems currently being developed for use as qubits, the quantum version of bits.

Ion traps An ion is an atom with extra or missing electron. Being electrically charged, individual ions can be trapped using electric and magnetic fields. The linear ion trap pictured uses 4 rod electrodes (light blue) which are fed an AC voltage of about 1 kilovolt at a frequency of a few megahertz. This confines the ions (red dots) along a central line. The end-rings (dark blue) are electrically charged to prevent the ions from escaping at the ends. Finely focused lasers are used to prepare and inspect individual ions. The outer electron of each ion is manipulated to be in two different orbits about the nucleus. Each ion therefore represents a qubit. As an ion scatters photons from the laser it recoils. Its recoil motion is felt by the other ions. This recoil motion is equivalent to the data bus of a classical computer

Department of ECE

GEC, Thrissur

Seminar 2004

14

Quantum computers

Nuclear magnetic resonance (NMR)

The nucleus (blue ball) of an atom can have a magnetic moment (orange arrow), i.e. the nucleus behaves as a tiny permanent magnet. The nucleus displays an unusual behaviour when placed in a strong magnetic field (green arrow). Owing to its quantum nature, the nuclear magnetic moment is aligned either in the same direction as or the opposite direction to the surrounding magnetic field. The orientation of the nucleus is therefore confined to two distinct values and so it represents a qubit. Adjacent nuclei also affect each other through their magnetic moments in the same way as two magnets placed near each other. This interaction allows one nuclear qubit to control an adjacent nuclear qubit. Quantum computation is carried out using radiofrequency fields to flip the nuclear moments. Output data is obtained by measuring the radiofrequency fields generated by oscillating moments. The largest quantum computer built to date is a 7 qubit device based on nuclear magnetic resonance. Unfortunately, technological difficulties limit the size of these devices to about 10 qubits. Nevertheless, nuclear magnetic resonance has been useful for demonstrating the principle operation of a quantum computer.

Department of ECE

GEC, Thrissur

Seminar 2004

15

Quantum computers

Quantum dots

Using advanced lithographic techniques it is possible to etch small structures called quantum dots in semiconductor materials. Each such dot, which can be as small as 30nm across (about 30 times the size of an atom) can confine a single electron in discrete energy levels. Thus the quantum dot behaves like a large artificial atom and can be used as a qubit. A user can access individual quantum dots using focused laser beams which can flip the electron between two discrete energy levels or place it into a superposition of the two levels. The required interaction between qubits occurs through externally applied electric and optical fields.

Department of ECE

GEC, Thrissur

Seminar 2004

16

Quantum computers

QUANTUM PARALLELISM

Quantum Computation is a new field which promises exponential parallelism A one bit memory can store one of the numbers 0 and 1. Likewise a two bit memory can store one of the binary numbers 00, 01, 10 and 11 (i.e. 0, 1, 2 and 3 in base ten) But these memories can only store a single number (e.g. the binary number 10) at a time. As described above, a quantum superposition state allows a qubit to store 0 and 1 simultaneously Two qubits can store all the 4 binary numbers 00, 01, 10 and 11 simultaneously. Three qubits stores the 8 binary numbers 000, 001, 010, 011, 100, 101, 110 and 111 simultaneously. 300 qubits can store more than 1090 numbers simultaneously. That's more than the number of atoms in the visible universe! This shows the power of quantum computers: just 300 photons (or 300 ions etc.) can store more numbers than there are atoms in the universe, and calculations can be performed simultaneously on each of these numbers! A system of 500 qubits, which is impossible to simulate classically, represents a quantum superposition of as many as 2500 states. Each state would be classically equivalent to a single list of 500 1's and 0's. Any quantum operation on that system --a particular pulse of radio waves, for instance, whose action might be to execute a controlled-NOT operation on the 100th and 101st qubits-- would simultaneously operate on all 2500 states. Hence with one fell swoop, one tick of the computer clock, a quantum operation could compute not just on one machine state, as serial computers do, but on 2500 machine states at once! Eventually, however, observing the system would cause it to collapse into a single quantum state corresponding to a single answer, a single list of 500 1's and 0's, as dictated by the measurement axiom of quantum mechanics. The reason this is an exciting result is because this answer, derived from the massive quantum parallelism achieved through superposition, is the equivalent of performing the same operation on a classical number 1. The position of the electron gives the number om.

Department of ECE

GEC, Thrissur

Seminar 2004

17

Quantum computers

INTERFERENCE OF WAVES

When a pebble is dropped into a pond waves travel outwards on the surface from the disturbance. Imagine dropping two pebbles a small distance apart. The waves created by each pebble will eventually intersect.

The answer is that the wave heights of the two waves simply add. Two wave crests (high points of the waves) will add to make an even higher wave when they cross, just like adding two positive numbers. Similarly, two troughs (low points of the waves) will add to make an even deeper trough, just like adding two negative numbers. These two effects are called constructive interference. However, when a tough and a crest cross, they cancel each other, just like adding a positive and a negative number can give zero. This effect is called destructive interference.

Department of ECE

GEC, Thrissur

Seminar 2004

18

Quantum computers

Beam splitter A beam splitter is a mirror with a very thin reflective coating. Because the coating is thin, not all the light is reflected and some is transmitted through the mirror. Typical beam splitters reflect about 50% of the light and transmit the remainder. Angling a beam splitter at 45o to two light beams allows the two beams to be mixed.

places. This property is used in the applet below to simulate a quantum search.

The important point is this: a single photon travels 4 paths simultaneously and examines the entire database in one go. This is the quantum superposition principle

Department of ECE

GEC, Thrissur

Seminar 2004

19

Quantum computers

Limitations The problem with this optical implementation of the search algorithm is that the number of optical paths equals number of elements in database. It would be prohibitive to build a large search engine by this method. This is the scalability problem. For this reason it is called a simulator of a quantum computer. See the section Qubit Systems for different approaches that avoid this problem. Despite its limitations, the simulation demonstrates the basic principles on which quantum computers are based: superposition and interference. The superposition principle allows many operations to occur simultaneously and the interference is how quantum calculations are performed. These effects take different forms in different realizations. For example, in a quantum computer based on atoms, the atoms could be in a superposition of different electronic orbits and the interference could be due to different phases of the electric dipole of the atoms

The table below shows that 300 qubits can store more than 1090 numbers simultaneously.

qubits 1

.

(0 and 1)

Total number 21

2

(0 and 1) (0 and1)

22

3

(0 and 1)(0 and 1)(0 and 1)

23

. 300

Department of ECE

Stores simultaneously

. (0 and 1)(0 and 1)… (0 and 1).

. 2300

GEC, Thrissur

Seminar 2004

20

Quantum computers

Quantum Entanglement

Quantum computers also utilize another aspect of quantum mechanics known as entanglement. One problem with the idea of quantum computers is that if you try to look at the subatomic particles, you could bump them, and thereby change their value. But in quantum physics, if you apply an outside force to two atoms, it can cause them to become entangled, and the second atom can take on the properties of the first atom. So if left alone, an atom will spin in all directions; but the instant it is disturbed it chooses one spin, or one value; and at the same time, the second entangled atom will choose an opposite spin, or value. This allows scientists to know the value of the qubits without actually looking at them, which would collapse them back into 1's or 0's.

Albert Einstein, Boris Podolski, and Nathan Rosen knew that the state vectors of certain quantum systems were correlated, or "entangled" with each other. If one changes the state vector of one system, the corresponding state vector of the other system is also changed, instantaneously, and independently of the medium through which some communicating signal must travel.

Throughout all of history previously, all physical phenomenon was dependent on some force, and some particle to carry that force, and therefore the speed of light restriction applied. For example, electrostatic forces are carried by the electron, gravitational forces are carried by the graviton, etc. However, with entanglement, quantum systems are correlated in some way that does not involve a force, and the speed of light restriction does not apply. The actual mechanism of how one system affects the other is still unknown. Department of ECE

GEC, Thrissur

Seminar 2004

21

Quantum computers

Collapse of the State Vector When two quantum systems are created while conserving some property, their state vectors are correlated, or entangled. For example, when two photons are created, and their spin conserved, as it must, one photon has a spin of 1 and a spin of -1. By measuring one of the state vectors of the photon, the state vector collapses into a knowable state. Instantaneously and automatically, the state vector of the other photon collapses into the other knowable state. When one photon’s spin is measured and found to be 1, the other photon’s spin of -1 immediately becomes known too. There are no forces involved and no explanation of the mechanism.

Quantum Teleportation The principle of entanglement enables a phenomenon called quantum teleportation. This kind of teleportation does not involve moving an entity from one physical location to another, as may be found in many popular science fiction stories, but a destruction of the original and recreation of an identical duplicate at another location

Department of ECE

GEC, Thrissur

Seminar 2004

22

Quantum computers

INEVITABILITY OF QUANTUM COMPUTERS As our technology rushes forward, several factors work together to push us toward the quantum computing world These factors are: scaling in size, energy consumption, economics of building leading edge computers, and new applications that are available with quantum computers that cannot be executed with classical computers. At the current rate of chip miniaturization, energy efficiency, and economics, the classical computer of the year 2020 , would contain a CPU running at 40 GHz with 160 Gb RAM, and run on 40 watts of power. Scaling Our computing world is surrounded by breath-taking innovations, and many of them involve more powerful and smaller chips. Chip capacity has doubled every 18 months, according to Moore’s Law, but the chip size remains constant. The number of transistors on a single chip is rising exponentially also. Keyes extrapolates that if miniaturization continues at the current rate, a bit will be represented by a single atom by the year 2020. This trend inevitably leads us into the micoworld of quantum effects, where classical rules no longer apply. Energy The speed of chips is also rising exponentially. Faster, more densely-packed, and closer transistors cause thermodynamic problems. Advances in energy efficiency are required to keep the chips from melting during use. Fortunately, energy efficiencies are increasing, and the thermodynamic problems are being resolved. These energy advances are also pushing the physics of chips into the quantum realm. Quantum computers are reversible, therefore there is theoretically no net energy consumption. Quantum reversibility means that quantum computers drive themselves forward in infinitesimal (reversible) steps, much the same way that molecules of perfume would diffuse from a perfume bottle. Quantum computer programs are not "run", but are said to "evolve," as they process the program’s inputs to outputs. Incidentally, reversibility also means that the inputs of a quantum computer can be implied from the outputs; the program can be run backwards

Department of ECE

GEC, Thrissur

Seminar 2004

23

Quantum computers

The argument for energy inevitability is a "carrot-and-stick" argument: the energy inefficiencies drive us away from classical computers, and the appeal for energy-free (or at least, much reduced energy consumption) computing drives us toward quantum computers.

Economics Besides the energy factors at the micro level of computing, there are large-scale economic factors pushing us to a more energy-efficient means of computing: 5% of the entire national power production is consumed by computing machinery. With "fossil fuels continuing to dwindle, fission power in disfavor with the public, and fusion power still many decades away, the drain computers impose on our power supply could become significant." The cost to build a semiconductor plant doubles every three years. By extrapolating that trend to the year 2020, a semiconductor plant will cost $1 trillion to build, which is 5% of the U.S. GNP. Based on Motorola’s sales figures, a similar company would need $10 trillion in annual sales to support that kind of construction. Japan, in its bid for software and hardware global dominance, has allocated huge funds for quantum computer research. ***, VP of Hewlett-Packard, reported that 70% of all quantum computer research is being done by the Japanese. They have included quantum computers as an integrated step of their global acquisition strategy

Department of ECE

GEC, Thrissur

Seminar 2004

24

Quantum computers

MODEL QUANTUM COMPUTER:

In this section we describe a simple model for a quantum computer based on a classical computer instructing a machine to manipulate a set of spins. This model has some intrinsic limitations which make designing algorithms in a high-level language somewhat tricky. We discuss some of the rules for writing such quantum computer code as a high-level language and give an example. Consider the following model for the operation of a quantum computer: Several thousand spinparticles (or two-level systems) are initially in some well defined state, such as spin-down. A classical machine takes single spins or pairs of spins and entangles them (performing an elementary one-bit operation

or the two-bit XOR gate); see Fig. 9a, b and c. These stages are

repeated on different pairs of spins according to the instructions of a conventional computer program. Since the spins are entangled, we must not look at the spins at intermediate stages: We must keep the quantum superposition intact. Furthermore, nothing else may interfere with the spins which could destroy their orientation or interrupt their unitary evolution. Once this well-defined cycle of manipulation is complete the orientations of the spins are measured (Fig. 9d). This set of measured orientations is the output of the computation. Given this paradigm for a quantum computer, what might its high-level language (its computer code) look like? The most serious difficulty that must be dealt with is that the quantum information is manipulated by a conventional computer in a completely blind manner--without any access to the values of this quantum information. This means that the program cannot utilize ``shortcuts'' conditional on the value of a quantum variable (or register or bit). For example, loops must be iterated through exactly the same number of times independent of the values of the quantum variables. Similarly, conditional branches around large pieces of code must be broken down into repeated conditions for each step. In addition, each instruction performed upon the quantum bits must be logically reversible.

Department of ECE

GEC, Thrissur

Seminar 2004

25

Quantum computers

Fig. 9 Model quantum computer as pictured by Shor. Initially all particles are spin-down. Stage a) a classical machine takes a single or pair of spins and in stage b) it performs a selected onebit or two-bit operation; in stage c) the ``entangled'' particles are returned to their original locations. These three stages are repeated many times in accord with the instructions given by an ordinary classical computer. When this cycle is complete stage d) consists of measuring the state of the particles (leaving them in some particular bit-string); this bit-string is the result of the computation.

Department of ECE

GEC, Thrissur

Seminar 2004

26

Quantum computers

NEW APPLICATIONS 1.Encryption Technology The speed of quantum computers also jeopardizes the encryption schemes that rely on impracticably-long times to decrypt by brute force methods. Encryption schemes that may take millions of years to guess and check are now vulnerable to quantum computers that may reach a solution within one year. Many governments, included ours, use such encryption schemes for national security. They are very interested in any technology that puts that at risk. As a result, the Office of Naval Research, the CIA, and DARPA, are sinking huge funds into quantum computer research. DARPA is funding $5 million for a Quantum Information and Computing Institute, and the CIA is funding an unknown amount for factoring of large integers, a fundamental part of encryption technology.

2.Ultra-secure and Super-dense Communications It is possible to transmit information without a signal path by using newly-discovered quantum principles, quantum teleportation. There is no way to intercept the path and extract information. Ultra-secure communication is also possible by super-dense information coding, which is a new technology in its own right. Quantum bits can be used to allow more information to be communicated per bit than the same number of classical bits.

3.Improved Error Correction and Error Detection Through similar processes that support ultra-secure and super-dense communications, the existing bit streams can be made more robust and secure by improvements in error correction and detection. Recovering informational from a noisy transmission path will also be a lucrative and useful practice.

Department of ECE

GEC, Thrissur

Seminar 2004

27

Quantum computers

4.Molecular Simulations Richard Feynman showed in 1982 that classical computers cannot simulate quantum effects without slowing down exponentially; a quantum computer can simulate physical processes of quantum effects in real time. Molecular simulations of chemical interactions will allow chemists and pharmacists to learn more about how their products interaction with each other, and with biological processes such as how a drug may interact with a person’s metabolism or disease. Pharmaceutical research offers a big market to such applications. 5.True Randomness Classical computers do not have the ability to generate true random

numbers. The

random number generators on today’s computers are pseudo-random generators—there is always a cycle or a trend, however subtle. Pseudo-random generators cannot simulate natural random processes accurately for some applications, and can not reproduce certain random effects. Quantum computers can generate true randomness, thus give more veracity to programs that need true randomness in their processing. Randomness plays a significant part of applications with a heavy reliance on statistical approaches, for simulations, for code making, randomized algorithms for problems solving, and for stock market predictions, to name a few. With the global forces of computer competition, encryption technology for national security, new applications, and the thermodynamics of computer systems changing as they are, there is a rush toward the new quantum technology to produce the first viable quantum computer. The world is moving toward a place that no classical computer has gone before, nor can go.Although quantum computers were predicted some years ago, the engineering obstacles were considered prohibitive, and quantum computers were not expected to be produced, even in prototype, until sometime in the year 2025. Despite predictions, the first prototype was built by Gershenfeld and Chuang in the summer of 1998 at MIT. Although there are several different designs for quantum computers, Gershenfeld and Chuang chose to use one based on nuclear magnetic resonance (NMR) principles.

Department of ECE

GEC, Thrissur

Seminar 2004

28

Quantum computers

BASIC DESIGN

In an NMR-type quantum computer, the atoms themselves are used as qubits for the system, and Gershenfeld and Chuang chose a liquid CPU containing two ounces of chloroform. The carbon-hydrogen atoms of chloroform each act as XOR gates, or in the jargon of quantum computers, controlled-NOT gates. The atoms are programmed through a sequence of radio pulses, and the answer is read through standard NMR detection techniques. The CPU is a two-bit "circuit" with about 1023 molecules. Each atom has a two-spin state, a "chemical spin" and an "atomic spin". The two kinds of spin used together provides 2-bits, and when used in conjunction with the other atom of the molecule, the molecule provides an effective XOR gate. Each atom acts like a bar magnetic when in an external magnetic field, the atoms aligning parallel (spin 1) or antiparallel (spin 0) to the field. By using a radio pulse, the atoms can be made to flip between states. This is the atom’s so-called chemical spin. The "atomic spin" of an atom causes it to precess in the magnetic field. Depending on its chemical spin alignment, it will rotate either clockwise or counterclockwise, much like a gyroscope.

Department of ECE

GEC, Thrissur

Seminar 2004

29

Quantum computers

CONTROLLED-NOT GATE The Controlled-NOT gate is a better description of the XOR gate because it is a 2-bit gate where one input controls the inversion property of the other input. Call one input line the Control, and the other input line the NOT input. The NOT function will only work if the Control line is set, but any input to the NOT line will be ignored if the Control is not set. The table below shows the truth table for the Controlled-NOT gate. Recall that the XOR gate, or the Controlled-NOT gate,. Is a universal gate, and therefore any circuit can be made from just this one kind of gate. OUTPUT

LINE 1

LINE 2

(Control)

(NOT)

0

0

0

0

1

1

1

0

1

1

1

0

Following Fig. shows a diagram of how a controlled-NOT gate works at the atomic level. The nature of the molecule works for the quantum computer because the chemical spin has slightly more energy in one alignment than the other. The hydrogen atom works like the control input, and the carbon acts like the NOT input. If the carbon is parallel aligned (spin 1) with the magnetic field, then a properly tuned radio signal can cause it to flip to be aligned antiparallel (spin 0) if the hydrogen is in the aligned position (state 1). If the hydrogen atom is in state spin 0, then the carbon will not flip states even with the radio pulse. (Similarly, the carbon atom can be flipped from state 0 to state 1 when hydrogen is in state 1.)

Department of ECE

GEC, Thrissur

Seminar 2004

30

Quantum computers

It actually takes two radio pulses to affect a carbon state transition, one for precessing and one for alignment. In this way, the quantum computer can send a programmed series of radio pulses at the molecules to set and reset the various bits of the "molecular registers". In contrast to the classical computer, which sends bits through gates to perform computation, the quantum computer sends the gates at the qubits to perform computation.

By throwing a programmed set of radio pulses at the molecules, and the numerous quantum gates within, Gershenfeld and Chuang implemented Grover’s search algorithm to select a marked item in an unsorted list of items. Their quantum computer performed the equivalent of opening a two-number combination padlock and in few numbers of average tries than a classical computer would need.

Department of ECE

GEC, Thrissur

Seminar 2004

31

Quantum computers

WHAT ARE THE OBSTACLES? Even within apparently small atomic-scale systems, quantum computation runs on the enormous size of Hilbert space. Quantum computation involves building a trajectory from a standard initial state to a complex final state. The main difficulty is keeping to this trajectory. To fail is to be lost in Hilbert space. The largest problem is hypersensitivity to perturbations, shifting the computational trajectory randomly from its path. Such perturbations come from an unintentional coupling to external noise. It is too soon to predict the gravity of this problem. It appears, though, that there is no fundamental limit to how well we can isolate a quantum system. Currently, several implementations are being considered by theoreticians and experimentalists worldwide One promising scheme involves ion-traps -the next generation of atomic-clock standards. Over the next two decades conventional computers will approach the atomic scale; perhaps quantum computers will get there first. The very thing that makes quantum computing so powerful, its reliance on the bizarre subatomic goings-on governed by the rules of quantum mechanics, also makes it very fragile and difficult to control. For example, consider a qubit that is in the coherent state. As soon as it measurable interacts with the environment it will decohere and fall into one of the two classical states. This is the problem of decoherence and is a stumbling block for quantum computers as the potential power of quantum computers depends on the quantum parallelism brought about by the coherent state . This problem is compounded by the fact that even looking at a qubit can cause it to decohere, making the process of obtaining a solution from a quantum computer just as difficult as performing the calculation itself.

Department of ECE

GEC, Thrissur

Seminar 2004

32

Quantum computers

FUTURE OUTLOOK

At present, quantum computers and quantum information technology remains in its pioneering stage. At this very moment obstacles are being surmounted that will provide the knowledge needed to thrust quantum computers up to their rightful position as the fastest computational machines in existence. Error correction has made promising progress to date, nearing a point now where we may have the tools required to build a computer robust enough to adequately withstand the effects of decoherence. Quantum hardware, on the other hand, remains an emerging field Thereby, quantum computers will emerge as the superior computational devices at the very least, and perhaps one day make today's modern computer obsolete. Quantum computation has its origins in highly specialized fields of theoretical physics, but its future undoubtedly lies in the profound effect it will have on the lives of all mankind.

Quantum computes are coming, and they will require a new way of looking at computing.

Applications that can not be done using classical computers are easily possible

with quantum computers. The spin-off concepts, like quantum teleportation, open vistas only imagined before. Computer science is still immature for it’s barely 80 years, and this radical divergence from the traditional development path is one indicator that.

Department of ECE

GEC, Thrissur

Seminar 2004

33

Quantum computers

17CONCLUSION

With classical computers gradually approaching their limit, the quantum computer promises to deliver a new level of computational power. With them comes a whole new theory of computation that incorporates the strange effects of quantum mechanics and considers every physical object to be some kind of quantum computer. A quantum computer thus has the theoretical capability of simulating any finite physical system and may even hold the key to creating an artificially intelligent computer. The quantum computers power to perform calculations across a multitude of parallel universes gives it the ability to quickly perform tasks that classical computers will never be able to practically achieve. This power can only be unleashed with the correct type of algorithm, a type of algorithm that is extremely difficult to formulate. Some algorithms have already been invented; they are proving to have huge implications on the world of cryptography. This is because they enable the most commonly used cryptography techniques to be broken in a matter of seconds. Ironically, a spin off of quantum computing, quantum communication allows information to be sent without eavesdroppers listening undetected. For now at least, the world of cryptography is safe because the quantum computer is very difficult to implement. The most successful experiments only being able to add one and one together. Nobody can tell if the problems being experienced by researchers can be overcome.The very thing that makes them powerful, their reliance on quantum mechanics, also makes them extremely fragile.

Department of ECE

GEC, Thrissur

Seminar 2004

34

Quantum computers

18.REFERENCES

1 .D. Deutsch, A. Ekert, "Quantum Computation," Physics World, March (1998) 2 .Shor, P. W., Algorithms for quantum computation: Discrete logarithms and factoring, in Proceedings of the 35th Annual Symposium on Foundations of Computer Science, IEEE Computer Society Press (1994).

3 .J. Preskill, "Battling Decoherence: The Fault-Tolerant Quantum Computer," Physics Today, June (1999) 4. ”The Topsy Turvy World of Quantum Computing” by Justin Mullins, IEEE spectrum, February 2001 5. E. Fredkin and T. Toffoli, Int. J. Theor. Phys. 21, 219 (1982). 6. C. H. Bennett, IBM J. Res. Develop. 17, 525 (1973). 7 .C. H. Bennett, SIAM J. Comput. 18, 766 (1989). 8 .D. Coppersmith, ``An approximate Fourier transform useful in quantum factoring,'' IBM Research Report RC19642 (1994). 9. “A comprehensive and inspiring guide to quantum computing” by David Deutsch, Physics World, 1/6/92

Department of ECE

GEC, Thrissur