What I might be doing
Well, people might wonder why I seem to have this fixation with quantum phenomena... Part of the reason is because it is what I think I might be doing when I get to grad school at USC. If you are interested (and I won't blame you if you are not), here is a paper I wrote on quantum computation. If you are Really interested, you can come here me give a talk about it on May 18. There are a couple of equations and circuits that are missing because their formats didn't transfer. But, this will give you an idea... Enjoy. :-)
If Moore's law is to continue, within the next few decades there will have to be some major computer architectural modifications. For the last half century, Moore's law stating that computers will double in speed ever two years has held true. However, transistors can only be made so small before they start running into difficult issues in their structure. One possible alternative is the quantum computer. A quantum computer would not be different merely because it was built out of electrons or ions as registers and circuits. While such minute parts could dramatically speed up interactions and reduce heat, there are multiple quantum phenomena that conflict with such classical engineering. However, starting primarily in 1984, Dr. Richard Feynman of California Institute of Technologyi began a discussion about how quantum mechanical computers could actually use quantum affects, suggesting that one possible use of this would be to simulate the complex quantum effects that make classical computers choke. However, as it turns out, there are even more exciting possibilities in this new technology.
All classical computers are built off of the Turing machine model. Alan Turing, in 1936ii, while attempting to answer a mathematical problem put forth by Hilbert, created a universal computation model before computers were even invented. This machine has a finite number of states and under certain conditions it can move from state to state. The states could be changed by ones and zeros that were read in by a tape and then read through a read-write head. With these elements and the instructions to know when to change states, any classical computer built on this model can do the same problem any other classical computer can accomplish, making the model universal.
In 1973, a man named Charles Bennett from IBM, created a model of the universal Turing machine (UTM) that was reversible. This was significant at the time because that meant that an ideal computer could calculate without the loss of any information, and thus, energy. This is actually used today for certain circuits in laptop cpu's in order to save energy. It was then realized in 1980iii, that Schroedinger's equation, the foundational wave equation that can represent all fundamental particles, was completely reversible, and Benioff showed that this meant any quantum system is reversible. Within 5 years, David Deutsch of Oxford Universityiv had developed a quantum Turing machine (QTM): one that was reversible and far more powerful than the original UTM. One fundamental change is that the storage tape is made from qubits. Qubits, instead of holding either 0 or 1, can actually be a superposition between 0 and 1. For example, if a qubit is the measure of the spin of an electron, then certain operations can be done to put that electron into a superstate. As long as the electron is not observed, it will remain in this superstate and be able to represent both 1 and 0 simultaneously. The other, and most important, change from the UTM, is that calculations can be done on all of the qubits simultaneously, creating a phenomena called quantum parallelism. Through this paper Deutsch argued that the physical universe is information rich. Computation and information is built into the foundational structure of our universe.
Before approaching quantum computing in more detail, it might be beneficial to have a more rigorous understanding of superpositions. This paper will use Dirac notation to represent quantum states. The spin of a fermion (any particle with a spin of ½: a proton, electron, etc.) can be represented as being in the state 0> or 1>, corresponding to a spin of -1/2 or +1/2. However, unless we have observed that particular fermion, we cannot say that it is in a particular state. Instead we have to say that our particle is in the general state of (A0> + B1>), where the probability of finding the particle in either state is dependent on the square of the coefficient A or B. This is often thought of as being the coordinates of a vector on a circle. 90 degrees is 1> and 0 degrees is 0>, and a superposition is any spot in between the two. Operators are applied to these kets (the x>'s) to change their state and manipulate the probabilities of where they could be found. 2 classical bits can represent four different numbers, either 0, 1, 2, or 3. However, 2 qubits can be a superposition of (A00>+B01>+C10>+D11>) if the two bits are entangled, and this way they can represent all four numbers simultaneously. By looking at the system, there is a random chance that any of the numbers will be found. This obviously scales very rapidly. A qubit register of 64 bits can represent 1.8 x 10^20 numbers simultaneously. If calculations can be done on the entire register without disturbing the superstate, then a massively parallel calculation could be performed. Multiple questions are then raised: how can a qubit be put into a superstate, how are they entangled, and how can a calculation be done on the system?
A qubit has numerous physical instantiations. It can, as has already been mentioned, fall under the realm of spintronics and use the spin of electrons. One promising way this is being done is through the use of quantum dots. A single electron can be trapped in a very thin substrate on a very pure silicon chip. This technology is being explored by UCSB along with several other institutes. The electron's spin can then be manipulated through superconductors on the chip. A qubit can also be the energy state of a single, trapped ion controlled by lasers. The NIST (National Institute of Standards and Technology) has been working on this method. Qubits can also be the spin state of the nuclei of a molecule that is manipulated by nuclear magnetic resonance (NMR). This is actually the same basic technology that medical MRI's are built from. The most progress has been made using this method because a great deal of the technology already exists. A very strong magnetic force is applied to a liquid to manipulate the spins on some of the molecules in the liquid. Then, through sending radio signals particular spins can be affected.
Let's approach the idea of a quantum superposition through the example of a trapped ion. A 0 for this qubit is when the valence electron for this ion is in the ground state. It moves to a 1 when it is pushed to an excited state. This excitation happens because an energy source is applied to the ion for a particular length of time. If it is applied for half the time, the ion's state can be placed into a superstate between ground and excited. This can be viewed mathematically through the Walsh-Hadamard gate, a fundamental one-qubit gate. If you apply a qubit 0> to this gate it will create a state 1/√2*(0>+1>), which in effect is a √not gate. If it is applied twice, it becomes 1> or a complete not gate.
Quantum entanglement, while difficult to understand, and perhaps even troubling to the theory of special relativity, is a well-proved phenomena. The EPR paradox, which suggested there were hidden variables, was disproved experimentally in 1982v, when Bell's inequalities were shown to be false, and thus quantum teleportation is a real phenomena. As long as a system of qubits can be setup and not disturbed, then the qubits are entangled and all of the qubits act as a system where calculations can be done in parallel. One way Qubits can be entangled is using a controlled-Not gate. A controlled-Not gate has the logic table:
00 00 Which sets up a matrix that looks like: 1 0 0 0
01 01 0 1 0 0
10 11 0 0 0 1
11 10 0 0 1 0
This is because the unity statement of bracket notation is <1> = 1, and we can make all other states to be equal to zero. So, if we analyze this logic table, <0> = 1, <0> = 0...<0> = 0...Down to the more interesting <2> state, which, when acted on by the controlled-Not gate, becomes <2> = 1, and the same for <3>, which turns into <3> = 1. The first input thus controls whether the gate acts like a not gate. But, more importantly, this gate sets up an entanglement between the two inputs. This gate, along with individual gates like the Walsh-Hadamard gate, are all that are necessary to do quantum calculations.
Inverse fourier transforms are used very frequently in various applications to create constructive and deconstructive interference. One of the fundamental aspects of quantum mechanics is that everything can be expressed as a wave, hence the Schroedinger equation. However, if things can be expressed as waves, then they can be interfered with, and constructive and deconstructive interference becomes a powerful tool. It can be used to amplify or destroy parts of the wave packet and thus pick out states to be more probable then other states. A Quantum Fourier Transform (QFT) can be implemented by considering the estimations made for the fast fourier transform. This way our QFT looks something like the following:
Now, examine the following circuit:
If the H stands for a Hadamard operator, and the R is a unitary operator such that Rd = 1 0
0 eiπ/2^d
where d is the distance between the lines, then this circuit could then be analyzed to be
Which, if looked at carefully, is seen to be the QFT.
We have now accrued a number of circuits in our repertoire. With various unitary operators such as the Hadamard operator to manipulate individual qubits into superpositions, the controlled-Not gate to entangle qubits, and the QFT to help manipulate the entire wave function, there are at least a few very powerful algorithms that can be built. A few things must be remembered though when dealing with quantum algorithms. In order for a quantum calculation to not decohere, the wave-function must not be disturbed. This means that the state cannot be passed off to another register, and it also means that there can be no input or output except for setting up the initial problem and receiving an answer. Therefore, a quantum algorithm is usually in the form of an oracle. The user sets up a question, and the computer responds with one particular answer. The few algorithms that have been developed so far have been set up in this form.
The first “killer application” was Shor's algorithm which was discovered in 1994vi. This algorithm makes it possible to calculate the factors of a number in exponential time. If this algorithm was implemented, then all RSA encryption could be broken in polynomial time. Since, outside of one-time pads, RSA encryption is one of the most secure methods of encryption, quantum computing suddenly became a very powerful tool. Without going into great mathematical detail, which is not possible in this paper, the periodic algorithm uses a quantum register that is big enough to hold the number that it is factoring. By the use of Hadamard operators, the circuit sets up a superstate that represents all the numbers from 1 to n. Also, using controlled-Not gates, it entangles all of the qubits. If the controllers for the not gates are allowed to decohere, they can give some number, x. The algorithm is used to find the period of the function such that x + r, and x + 2r, are also equal to the decohered not gates. This function is applied to the lines with the Hadamard operators, and then they are put into a QFT. For all the solutions that are based on r, or an integer multiple of r, the circuit will interfere constructively and every other solution will deconstructively interfere. By setting up the function to be: fn(s) = xs mod n s becomes a period function of n. Shor's algorithm will give us this period, and with a little manipulation, a common factor can be deduced from this period.
The second major algorithm that has been demonstrated is centered on unordered database searching. For example, if someone is looking for a particular phone number in a phone book, the only classical means of searching is to start at the beginning of the phone book and check every answer. The solution will be found on the order of O(n). However, in a quantum computer, this can be computed in a √n time. The main work is in constructing a unitary gate such that when the input, x, is equal to some number, w, then it will output a 1, otherwise it will output a 0. The control for this gate is then given to all the possible inputs, a qubit register spanning all the possible choices. Part of the circuit could look like this:
U is the special operator. 1> when applied to H becomes 1/√2*(0>-1>) and when U is true, the solution becomes -1 x> *1/√2*(0>-1>) because the 0> and 1> are switched, making it x> *1/√2*(1>-0>). When x ≠ w the solution is instead 1* x> *1/√2*(0>-1>). Just looking at the first part, If all x ≠ w, then the solution would just be x>. On the other hand, if x = w is the only case, then -w> is our only state. All of these cases can be summed up with (1-2w>
The other general category of algorithm that has great promise is the one originally suggested by Feynman in 1984. Today's supercomputers have trouble even representing small quantum systems. The exact phenomenon that make quantum computers so different from their classical counterparts, their entanglement and parallelism, also make them extremely difficult to model in a classical, serial model. However, reasoned Feynman, a quantum computer should be able to model a quantum system with ease. This seems clearly true, and yet, surprisingly little progress has been made. Perhaps actual computers must be made before we can develop a working set of algorithms.
Why has so little progress been made in any of these fields? If a quantum computer could break the most used, and most powerful encryption currently available, it seems every major government and spy organization would want a quantum computer delivered immediately. Actually, DARPA (Defense Advanced Research Projects Agency) has invested millions of dollars into various quantum computing projects, and many other research organizations are also investing heavily. But, there are some major challenges that must be overcome before a quantum computer comes to a store near you. The two biggest problems are scalability and error correction.
Quantum computers are analogue machines fundamentally, and because of this, the errors can grow significantly faster than on a digital machine. In a digital machine, a bit is either 1 or 0, and if there is an error, the error stops at that bit. However, in an analogue machine, the errors can creep into the entire algorithm and drag down the entire system. On top of this crucial issue, the quantum methodologies being pursued are greatly prone to errors. Most of the practical systems that have been created end up decohering in a matter of milliseconds. When the system must be brought to cryogenic temperatures and every stray photon can disrupt the superstate, the system is fairly unstable. The sources of error become almost innumerable. However, significant progress has been made on developing good error correction techniques. Most of them involve using from 5 to 9 qubits for every qubit that carries actual information. This then, leads to the second major problem of scalability.
The current, most promising methods of creating qubits are NMR and isolating ions. Quantum dots seem like they could be very promising since they rely on solid state devices, however, not a great deal has been accomplished yet in that field. NMR techniques use long molecules to create entangled spins, but they have only managed to do so with up to around 7-10 qubits. If there is any hope in this method of moving beyond around 100 qubits, then they will have to make some designer molecules that can be strings of thousands of atoms long. Isolating ions has also had limited success but decoherence starts to strike on the order of 1x10^-6 seconds. With each ion requiring it's own set of controlling lasers, it seems to require a little too much micromanaging to create a stable lengthy qubit register. In order to accomplish worthwhile calculations, there need to be qubit registers in the hundreds. Along with each of these qubits comes a party of at least 5 or more error correcting members. A working system, then, must be in the range of thousands. No current method seems to be promising that level of scalability anytime in the near future. However, research presses onward. Within the last few months, there have been news reports from places like Oxford and Los Alamos of large artificial atoms being used as qubits. If technology rates continue, the first usable quantum computers might be seen in a decade or two. Thus, they would arrive just in time to save Moore's law.
Bibliography
Brown, Julian, The Quest for the Quantum Computer, 2000, Simon and Schuster, New York
Gasiorowicz, Stephen, Quantum Physics, 3rd Edition, 2003, John Wiley and Sons, Inc.,
Hobeken, NJ
Johnson, George, A Shortcut Through Time, 1st Edition, 2003, Alfred A. Knoph, New York
Williams and Clearwater, Colin and Scott, Ultimate Zero and One, 1st Edition, 2000,
Copernicus, New York
http://beige.ucs.indiana.edu/M743/
http://www.cs.iastate.edu/~patterbj/cs/quantum/fp/index.htm
http://www-ee.stanford.edu/~osgood/Sophomore%20College/Quantum%20Computing.pdf
http://plato.stanford.edu/entries/turing-machine/
http://www.theory.caltech.edu/people/preskill/ph229/#lecture
iRichard Feynman, “Quantum Mechanical Computers”, IQEC-CLEO Meeting, 1984
ii Alan Turing, ``On Computable Numbers with an Application to the Entscheidungsproblem'', Proceedings of the London Mathematical Society, vol. 42, 1937, pp. 230-265, erratum in 43, 1937
iii Benioff, Journal of Statistical Physics, Vol. 22, 1980
iv Deutsch, Proceedings of the Royal Society of London, Vol. A400, 1985
v A. Aspect, J. Dalibard, G. Roger, ``Experimental Test of Bell's Inequalities Using Time-Varying Analyzers'', Physical Review Letters, Vol. 49, 1982
vi Peter Shor, ``Algorithms for Quantum Computation, Discrete Logarithms and Factoring'', Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994
posted by Secretwallaby @ 3:40 PM
1 comments
