September 19, 2008

QUANTUM COMPUTING

During the past forty years astounding advances have been made in the manufacture of computers. The number of atoms needed to represent a bit in memory has been decreasing exponentially since 1950. Likewise the numbers of transistors per chip, clock speed, and energy dissipated per logical operation have all followed their own improving exponential trends. Despite these fantastic advances, the manner in which all computers function is essentially identical. This rate of improvement cannot be sustained much longer, at the current rate in the year 2020 one bit of information will requite only one atom to represent it. The problem is that at that level of miniaturization the behavior of the components of a computer will become dominated by the principles of quantum physics. (Williams, Clearwater)

With the size of components in classical computers shrinking to where the behavior of the components may soon be dominated more by quantum physics than classical physics researchers have begun investigating the potential of these quantum behaviors for computation. Surprisingly it seems that a computer whose components are able to function in a quantum are more powerful than any classical computer can be.

It is the physical limitations of the classical computer, and the possibilities for the quantum computer to perform certain useful tasks more rapidly than any classical computer that drive the study of quantum computing.

During the past forty years astounding advances have been made in the manufacture of computers. The number of atoms needed to represent a bit in memory has been decreasing exponentially since 1950. Likewise the numbers of transistors per chip, clock speed, and energy dissipated per logical operation have all followed their own improving exponential trends. Despite these fantastic advances, the manner in which all computers function is essentially identical. This rate of improvement cannot be sustained much longer, at the current rate in the year 2020 one bit of information will requite only one atom to represent it. The problem is that at that level of miniaturization the behavior of the components of a computer will become dominated by the principles of quantum physics. (Williams, Clearwater)

With the size of components in classical computers shrinking to where the behavior of the components may soon be dominated more by quantum physics than classical physics researchers have begun investigating the potential of these quantum behaviors for computation. Surprisingly it seems that a computer whose components are able to function in a quantum are more powerful than any classical computer can be.

It is the physical limitations of the classical computer, and the possibilities for the quantum computer to perform certain useful tasks more rapidly than any classical computer which drive the study of quantum computing.

1.1 AN ANALOGY

Ø Newtonian physics is an approximation to Einsteinian physics (general relativity).

Ø Classical physics is an approximation to quantum mechanics.

Ø Classical information is an approximation to quantum information.

Ø In each case, the approximation excludes important details but serves well for many purposes.

Ø In each case, removing the approximation requires deeper understanding and harder math, but results in a truer picture of Nature and may enable new technologies.

Ø Yes, Nature: we are beginning to understand that information is a physical concept.

1.1.1 APPROXIMATIONS THAT WE REMOVE

Ø Relativity: we remove (among others) the approximation that we are traveling much slower than light.

Ø Quantum mechanics: we remove (among others) the approximation that we are manipulating things much larger than atoms.

Ø Quantum computation: we remove (among others) the approximation that the elements of information are independently manipulable.

1.1.2 THE REASONS

Ø That approximation means that we can look at one bit in a register without affecting the other bits.

Ø Why remove that approximation? Because it limits the power of the computer.

Ø Also, getting ahead of uss, that approximation turns out to be troublesome in representing information quantum mechanically.

1.1.3 WE ARE RUNNING OUT OF PARTICLES

Ø The insulators in CMOS transistors can’t get much smaller or the insulating layers will stop insulating (at around 6 atoms thick). (Maybe before 2010.)

Ø In optical fiber, we use ten thousand or so photons to represent a bit. There’s a Moore’s law for fiber, too, and we’ll soon run out of photons. (Maybe before 2010.)

Ø Quantum mechanical effects will become important in just a few years!

Ø Currently, we work in the classical information regime. That won’t last. We’d better come to understand quantum information.

Ø Of course, this version of the story isn’t how quantum computation came to be. (Keep in mind the analogies.) So let’s back up and tell a more historical story, to introduce the ideas.

1.2 FEASIBILITY OF QUANTUM COMPUTING

Is it feasible for a computer to simulate a physical system perfectly? The answer appears to be, "No". A classical computer seems to need time exponential in n to predict precisely the behavior of a general quantum mechanical system of n particles. (Yet nature manages to do it in real time.) Briefly, a quantum mechanical system of n particles is represented by a wave function in a Hilbert space of dimension exponential in n. We really do need that much dimensionality to r

1.1 QUANTUM MECHANICS

1.1.1 SLIDE 1

The state of a QM system is described by its wave function, y, an oscillating complex valued

function defined over all of space. y can interfere with itself.

Quantum mechanics is linear. We can create y by linear combination, e.g.:

y=aupyup + adownydown

For well defined states, e.g. up, we use the notation ïup>, so

y=aup ïup> + adown ïdown>

The as are complex coefficients that must normalize; if the ï> states are orthogonal, the as must satisfy:

S ïai ï2 = 1

These are called probability amplitudes and ïai ï2 (note the square) is the probability that if we make a measurement of the system, we will find it in state ïi>.

1.1.2 SLIDE 2

The quantum measurement postulate in math:

If we make a measurement on a system with wave function

y= Si ai ïi>s

and find it’s in state i, the wave function is now

y=ïi>.

Math aside: the i are the eigen values corresponding to eigenvectors ïi> of the operator (e.g. energy) defining the measurement.

1.1.3 SEE FOR YOURSELF

Light can be linearly polarized: its vibrations can lie in a plane, say horizontally or vertically. Represent these two possibilities as אַ> and ﭯ>. We call these orthogonal states a basis of the system.

Plain light is a mixture of these polarizations and in fact a single photon can be a mixture. For example, light polarized at 45° is 1/_`2 (אַ> + ï­¯>).

Light can also be circularly polarized: circular polarization can be created from linear as follows:

ïrcp> = 1/_`2 (אַ> + iï­¯>)

ïlcp> = 1/_`2 (אַ> - iï­¯>)

This is another orthogonal basis of the polarization.

We can demonstrate that light obeys the quantum measurement postulate using three linear polarizing filters and an overhead projector....

1.1.4 WAVE FUNCTIONS

  1. Quantum mechanics is a linear theory: we can create linear superpositions of wave functions, provided we keep the probability amplitudes normalized.
  2. The quantum measurement postulate can be described as the wave function ‘collapsing’ to the basis state corresponding to the outcome of the experiment.
  3. We cannot discover the full quantum state of a system, only the squared probability amplitudes ïaï2. The a are the projections of the system onto the basis states and are complex valued.

THE QUANTUM COMPUTER


2.1 QUANTUM PHYSICS

When considering the possible power of a computer which makes use of the results of quantum physics, it is helpful to know a little of quantum physics itself. Quantum physics arose from the failure of classical physics to offer correct predictions on the behavior of photons and other elementary particles. Quantum physics has since been under intense scrutiny, as some of its predictions seem very strange indeed. Nevertheless experiments verify the same strange behavior which leads skeptics to challenge the veracity of Quantum physics.

2.2 THE CLASSICAL BIT

To understand the ways in which a quantum computer is different from a classical computer you must first understand the rudiments of the classical computer. The most fundamental building block of a classical computer is the bit. A bit is capable of storing one piece of information, it can have a value of either 0 or 1. Any amount of information can be encoded into a list of bits. In a classical computer a bit is typically stored in a silicone chip, or on a metal hard drive platter, or on a magnetic tape. About 10 10 atoms are currently used to represent one bit of information. The smallest conceivable storage for a bit involves a single elementary particle of some sort. For example, for any particle with a spin -1/2 of particle, which can be characterized by its spin value, which when measured is either +1/2 or –1/2. We can thus encode 1 to be +1/2 and 0 to be –1/2, and if we assume we can measure and manipulate the spin of such a particle then we could theoretically use this particle to store one bit of information. If we were to try to use this spin-1/2 particle as a classical bit, one that is always in the 0 or 1 state, we would fail. We would be trying to apply classical physics on a scale where it simply is not applicable. This single spin-1/2 particle will instead act in a quantum manner. (Williams, Clearwater) S

This spin -1/2 particle which behaves in a quantum manner could be the fundamental building block of a Quantum computer. We could call it a qubit, to denote that it is analogous in some ways to a bit in a classical computer. Just as a memory register in a classical computer is an array of bits, a quantum memory register is composed of several spin -1/2 particles, or qubits. There is no particular need for the spin-1/2 particle, equally well we could use a Hydrogen atom, and designate its electron being measured in the ground state to be the 0 state, and it being in the first excited state to be the 1 state. There are a multitude of possible qubit representations that will work. For simplicity I will discus only the spin-1/2 particle from here on, but analogous arguments could be made for many things.

2.3 STATE VECTORS AND DIRAC NOTATIONS

We wish to know exactly how the behavior of the spin-1/2 particle, our qubit, differs from a that of a classical bit. Recall that a classical bit can store either a 1 or a 0, and when measured the value observed will always be the value stored. Quantum physics states that when we measure the spin-1/2 particles state we will determine that it is in the +1/2 state, or the spin -1/2 state. In this manner our qubit is not different from a classical bit, for it can be measured to be in the+1/2, or 1 state, or the -1/2, or 0 state. The differences between the qubit and the bit come from what sort of information a qubit can store when it is not being measured.

According to quantum physics we may describe that state of this spin-1/2 particle by a state vector in a Hilbert Space. In general the mathematical term space refers to a something which depends on many independent coordinates which can be defined by a set of perpendicular axes, one for each independent variable. For example you are probably familiar with the x, y, z coordinate system where the x, y, and z axes are mutually perpendicular real number lines, which coincide at the point x=0, y=0, z=0.

A Hilbert Space is a special kind of space, it has the properties that it is a complex vector space, and it is a linear vector space.

The fact that it is a complex vector space means that the lengths of the vectors within the space are described with complex numbers. Complex numbers are numbers which take the form a+i*b, where a and b are real numbers, and I is defined to be the square root of negative one.

The fact that it is a linear vector space means that you may add and multiply vectors that lie in a given Hilbert Space and the resulting vector will still lie within that Hilbert Space. (Williams, Clearwater)

In the Hilbert Space for our state vector, which describes the state of our spin-1/2 particle, these perpendicular axes will correspond to each possible state that the system can be measured in. So our Hilbert Space for a single qubit will have two perpendicular axes, one corresponding to the spin-1/2 particle being in the +1/2 state, and the other to the particle being in the -1/2 state. These states which the vector can be measured to be are referred to as ``eigenstates.'' The vector which exists somewhere in this space which represents the state of our spin-1/2 particle is called the ``state vector.'' The projection of the state vector onto one of the axes shows the contribution of that axes' eigenstate to the whole state. This means that in general, the state of the spin-1/2 particle can be any combination of the base states. In this manner a qubit it totally unlike a bit, for a bit can exist in only the 0 or 1 state, but the qubit can exist, in principle, in any combination of the 0 and 1 state, and is only constrained to be in the 0 or 1 state when we measure the state.

Now I will introduce the standard notation for state vectors in Quantum physics. The state vector is written with the following way and called a ``ket vector'' 1y>. Where y is a list of numbers, which contain information about the projection of the state, vector onto its base states. The term ket and this notation come from the physicist Paul Dirac who wanted a concise shorthand way of writing formulas that occur in Quantum physics. These formulas frequently took the form of the product of a row vector with a column vector. Thus he referred to row vectors as ``bra vectors'' represented as, and would be referred to as a ``bracket.'' (Williams, Clearwater)

There is nothing special about this vector notation, you may think of any state vector being written as a letter with a line over it, or as a bold letter, as vectors are normally denoted. If you do further reading into this area you will almost assuredly come across the bra and ket notation, which is why it is presented.

2.4 SUPERPOSITION AND EIGENSTATES

Earlier I said that the projection of the state vector onto one of the perpendicular axes of its Hilbert Space shows the contribution of that axes' eigenstate to the whole state. You may wonder what is meant by the ``whole state.'' You would think (and rightly so, according to classical physics) that our spin-1/2 particle could only exist entirely in one of the possible +1/2 and -1/2 states, and accordingly that its state vector could only exist lying completely along one of its coordinate axes. If the particle's axes are called x and y, and the state vector's x coordinate which denotes the contribution to the +1/2 , or 0 state, and y coordinate which denotes the contribution to the –1/2 , or 1 state, should only be (1,0), or (0,1).

That seems perfectly reasonable, but it simply is not correct. According to quantum physics a quantum system can exist in a mix of all of its allowed states simultaneously. This is the Principle of Superposition, and it is key to the power of the quantum computer. While the physics of superposition is not simple at all, mathematically it is not difficult to characterize this kind of behavior.

2.5 THE QUANTUM QUBIT

Back to our qubit, our spin -1/2 particle. Now that we know that while it can only be measured to have a spin of +1/2 or –1/2, it may in general be in a superposition of these states when we are not measuring it. We could refer to its state in the following manner.

Let x1 be the eigenstate corresponding to the spin +1/2 state, and let x0 be the eigenstate corresponding to the spin -1/2 state. Let X be the total state of our state vector, and let ω1 and ω0 be the complex numbers that weight the contribution of the base states to our total state, then in general:

|X>=ω0*|x0> + ω1*|x1 >


At this point it should be remembered that ω0 and ω1, the weighting factors of the base states are complex numbers, and that when the state of X is measured, we are guaranteed to find it to be in either the state:

\begin{displaymath}0 * \vert x_{0} \rangle + w_{1} * \vert x_{1} \rangle \equiv (0,w_{1})\end{displaymath}


or the state

\begin{displaymath}w_{0} * \vert x_{0} \rangle + 0 * \vert x_{1} \rangle \equiv (w_{0},0)\end{displaymath}


This is analogous to a system you should be more familiar with, a vector with real weighting factors in the a two dimensional plane. Let the base states for this two dimensional plane be the unit vectors $x$, and $y$. In this case we know that the state of any vector $V$can be described in the following manner:

\begin{displaymath}V = x_{0} * x + y_{0} * y \equiv (x_{0},y_{0})\end{displaymath}

Our state vector is a unit vector in a Hilbert space, which is similar to vector spaces you may be more familiar with, but it differs in that the lengths of the vectors are complex numbers. It is not necessary from a physics perspective for the state vector to be a unit vector (by which I mean it has a length of 1), but it makes for easier calculations further on, so I will assume from here on out that the state vector has length 1. This assumption does not invalidate any claims about the behavior of the state vector. To see how to convert a state vector of any length to length 1 see appendix A.

With all this in mind we have fully defined the basic building block of our quantum computer, the qubit. It is fundamentally different from our classical bit in that it can exist in any superposition of the 0 and 1 states when it is not being measured. (Barenco, Ekert, Sanpera, Machiavello)

2.6 QUANTUM PARALLELISM

Given that our quantum memory register differs from a classical one in that it can store a superposition of the base states of the register, one might wonder what this implies as to the power of quantum computing. The study of quantum computing is relatively new, most give credit to Richard Feynman for being the first to suggest that there were tasks that a quantum computer could perform exponentially better than a classical computer. Feynman observed that a classical computer could not simulate a quantum mechanical system without suffering from exponential slowdown. At the same time he hinted that perhaps by using a device whose behavior was inherently quantum in nature one could simulate such a system without this exponential slowdown. (Feynman)

Most modern theoretical quantum algorithms rely on something called quantum parallelism. Quantum parallelism arises from the ability of a quantum memory register to exist in a superposition of base states. A quantum memory register can exist in a superposition of states, each component of this superposition may be thought of as a single argument to a function. A function performed on the register in a superposition of states is thus performed on each of the components of the superposition, but this function is only applied one time. Since the number of possible states is $2^{n}$where $n$is the number of qubits in the quantum register, you can perform in one operation on a quantum computer what would take an exponential number of operations on a classical computer. This is fantastic, but the more superposed states that exist in you register, the smaller the probability that you will measure any particular one will become.

As an example suppose that you are using a quantum computer to calculate the function $\mathcal{F}(x) = 2*x \bmod 7$, for $x$integers between 0 and 7 inclusive. You could prepare a quantum register that was in a equally weighted superposition of the states 0-7. Then you could perform the $2*x \bmod 7$operation once, and the register would contain the equally weighted superposition of 1,2,4,6,1,3,5,0 states, these being the outputs of the function $2*x \bmod 7$for inputs 0 - 7. When measuring the quantum register you would have a $2/8$chance of measuring 1, and a $1/8$chance of measuring any of the other outputs. It would seem that this sort of parallelism is not useful, as the more we benefit from parallelism the less likely we are to measure a value of a function for a particular input. Some clever algorithms have been devised, most notably by Peter Shor and L. K. Grover which succeed in using quantum parallelism on a function where they are interested in some property of all the inputs, not just a particular one.

2.7 THE POWER OF QUANTUM COMPUTER

Given the possible power of quantum parallelism much work has been done to show formally with mathematical proofs how quantum computers differ from classical ones in their power to compute things. Here is a short list of some of the landmarks in the study of the power of quantum computers.

In 1980 Paul Benioff offered a classical Turing machine which used quantum mechanics in its workings, thus showing that theoretically a quantum computer was at least as powerful as a classical computer. (Benioff)

In 1982 Richard Feynman showed that a classical Turing Machine (and hence any classical computer) could not simulate a quantum mechanical system without suffering exponential slowdown. (Feynman)

David Deutsch and Richard Jozsa showed in a paper in 1992 that there was an algorithm that could be run in poly-log time on a quantum computer, but required linear time on a deterministic Turing machine. This may have been the first example of a quantum computer being shown to be exponentially faster than a deterministic Turing machine. Unfortunately for the quantum computer, the problem could also be solved in poly-log time in a probabilistic Turing machine, a Turing machine which is capable of making a random choice. (Deutsch, Jozsa)

Also in 1992 Andre Berthiaume proved that $P \subset QP$, where $P$is a complexity class as mentioned earlier and $QP$corresponds to problems which can be solved in worst case polynomial time by a quantum computer, so with regards to tractability a quantum computer is more powerful than any classical computer. (Berthiaume, Brassard)

SHOR’S ALGORITHM


4.1 INTRODUCTION

By the early nineties it was know that a quantum computer could be faster than any classical computer. Nonetheless these observations were largely driven by academic curiosity. There was not much motive for people to spend lots of money or time trying to build a quantum computer.

That changed in 1994 when Peter Shor, a scientist working for Bell Labs devised a polynomial time algorithm for factoring large numbers on a quantum computer. This discovery drew great attention to the field of quantum computing.

4.2 STEPS

Peter Shor showed how to design a quantum computer to calculate the factors of an integer in polynomial time, theoretically breaking RSA.

We want to factor N, that is, find A and B such that AB =N.

Trick: find distinct x and y such that

x 2 ºy 2 mod N.

Then

x 2 - y 2 = (x + y)(x - y) º0 mod N

so one must contain a factor, which we can find by e.g.

gcd(x - y,N).

Next, take y to be 1, so if x r º1 and r is even then

(x r/2 - 1)(x r/2 + 1) º0 modN.

Then r is the period of the function x a mod N in a.

Looking for pair x,r such that (x r/2 - 1)(x r/2 + 1) º0 mod N.

Greatly simplifying, algorithm builds a superposition of all integers x , then calculates xa mod N for all a in parallel.

Discover the periods using a (quantum) FFT on the resulting entanglement. The final state is (sort of) an entanglement of all valid x,r pairs.

Finally, measure the output register. QMP says it must choose one x,r pair, and we can factor.

With probability << 1/2, the output may be zero; if so, we run it again.

Not much like a regular computer program!

4.3 WHAT ELSE WE CAN DO?

Shor’s algorithm factors in polynomial time.

(We expect to get a nonzero result in a small number of runs.)It’s dramatically faster than any known classical algorithm.

Entanglement gives us exponential parallelism.

A few other quantum algorithms go faster than classical. Most are obscure but one is important:

Lov Grover’s algorithm searches an unordered database of N elements to finds an element satisfying a given condition in √N time. In other words,

it searches a linear list in square root time.

Not as dramatic as the exponential speedup in Shor’s algorithm, but remarkable and possibly even practical.

4.4 DECOHERENCE

Factoring a 200digit number using Shor requires 3500 perfectly well behaved qubits. (Current state of the art is four entangled qubits.) But that’s not the hard part.

The challenge is decoherence: the ‘leakage’ of quantum state into the environment. Actually, it is entanglement with the environment. (Believed to be the explanation for why the macroscopic world behaves classically).

QC must be run in a sealed box without any interaction with the outside world. Otherwise the qubits will be contaminated.(This is another reason debugging could be hard.)

The required isolation is extreme; today’s entangled atomic states in the lab last for about 10ns, and decoherence proceeds exponentially fast in the number of particles.

4.5 ERROR CORRECTION

Decoherence would be the death knell for QC, except that Shor and others discovered quantum error correction. Like classical error correction, but QEC can correct an arbitrary error in a qubit, even if we don’t know its state! (Much more astonishing than repairing a bit flip in a classical message.)

Many such codes exist, e.g. 7 qubits can fully repair damage to any one qubit in the message.

QEC could compensate for decoherence and other losses if they’re at a low enough rate. (Current theory ranges from 10 - 6 to 10 - 2.) Error correcting a t sstep computation involves overhead polynomial in log t.

Using Shor to factor 200 digits requires 3500 perfect qubits, 100,000 if error correction is involved.


Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)