Quantum Computing: a huge breakthrough
By Spiros Tzelepis
People who are aware of computer issues are looking forward to the results of the research hold by the physics department of Media Lab under the guidance of Professor Neil Gersherfeld. I confess that I wrote to Prof. Gershenfeld asking for an interview mostly motivated by my personal interest to learn. Yael Maguire, one of the members of this team, shares his experience with all of us.
In the early 1980s, physicists Richard Feynman, David Deutsch and Paul Benioff noticed that classical computers required exponential memory and time to simulate a quantum system. You might have a couple of questions: What is a classical computer? And what is a quantum system? A classical computer is something, like a Pentium III, where you can reduce the computer to bits and gates. A bit is a Binary digIT that is either 1 or 0. If I want to write the number 7 as a 3-bit number, I would write111
To decode this, you write the number of bits on the left most column, subtract one and each column to the right subtract another one:1 1 1
Then you take the bit in the column, multiply it by 2 raised to the exponent of the column and then add all the entries. So, 7 is 1x2^2 + 1x2^1 + 1x2^0 = 4 + 2 + 1 = 7. You should work out for yourself some other numbers for fun. Gates are the little computational elements that make up a computer. One gate for example is the AND gate for 2 input bits:input output
A quantum system is a collection of REALLY small things like atoms or light particles that follow the rules of quantum mechanics. Just to remind you about exponentials, if I have a string of 80 atoms that I would like to simulate on a classical computer, I would need about 2^80 bits of memory to simulate this system. Now that is about the number of atoms in the WHOLE UNIVERSE, so you can see how hard this could be for a Pentium III or even a supercomputer. This original question of Feynman, Deutsch and Benioff remained a nice problem that nobody thought had any practical importance until Peter Shor in 1994 showed a quantum computer could solve a real problem (important for electronic commerce) exponentially faster than any computer that is based on classical rules. Certain problems that could not be solved before the universe ended could all the sudden be solved in years on these machines. It was still a dream because no quantum computers existed and nobody knew how to build them. People quickly were disappointed when people like Isaac Chuang and W. G. Unruh showed that these computers would be incredibly difficult to build. Then, a number of people showed that with some cleverness called error correction, there might be a chance to build them. In 1997, a couple of groups, one led by Neil Gershenfeld, showed that nuclear magnetic resonance (NMR) could be a quantum computer and now people (like me) are starting to build these machines. We're still a long way off to solving really hard problems, but it's at least a start.
Quantum computing is based on the idea of using quantum mechanics as a means of processing information. In a digital computer, bits are carried along wires that are processed by the transistors in a chip. A transistor is a little switch that makes gates. There are about 100 million transistors in a personal computer. Now, consider if you have made a circuit that operates on 2 bits of information. The possible states that can be represented are:00 = 0
So for 2 bits there are 4 combinations. In a Pentium III for example, it is a computer that works on 32-bits at a time, giving 4294967295 combinations. It is important to see that a 32-bit number can represent only 1 of those 4294967295 numbers at a time. In a quantum computer, things are quite different. One deals with quantum bits or qubits. Now qubits have an interesting property called superposition that allows 32-qubits to represent ALL 4294967295 combinations at once. So just about every person on earth would need 32-bits of information to represent the information that a single 32-bit quantum memory would provide You might ask how do you make a qubit? Well, lots of people are trying to answer that question. It's hard because quantum systems are very fragile. The systems people have tries to use so far are quantum dots (a tiny puddle of electrons), trapped ions (atoms made to hold still with lasers), and nuclear magnetic resonance (similar to what people get their brains scanned with).
Even though quantum computers seem very difficult to build, people have made amazing progress. The field already considers these results amazing. Nuclear Magnetic Resonance (NMR), the part of quantum computing I work in has had amazing progress. People have demonstrated a basic quantum algorithm called Grover's algorithm on a NMR quantum computer. This algorithm searches an unsorted list faster than a classical computer can. For example, if I have a list0 0 0 0 1 0 0 0
and ask your computer where the 1 is, the computer would take somewhere between 4 and 5 steps (you should think of how you would do that). If I ask a quantum computer the same answer is would take about 2 steps. Now that doesn't seem like much, but the fact that in principle it could do better than any normal computer is very important. If the database were 6,000,000,000 long, it would take about 3,000,000,000 steps on your computer and only about 61000 on a quantum computer.
People have been able to show a NMR quantum computer searching the 8 number long list, but it's very hard to get it to compute larger sizes. There will be a lot of work to develop quantum computers that can solve problems faster than a classical computer. A real working quantum computer will look nothing like what they look today. Right now if you wanted to buy a simple quantum computer, it would cost you about $500,000 and you (or I) would have a hard time getting it to act like a computer you or I is used to. People are working very hard to make quantum computers chips like a Pentium. But this is much harder - the pieces you need have to control and see very tiny things - thousands of times smaller than what Pentium's do. But, Pentiums are getting faster and faster and the pieces that make them up are getting smaller and smaller. Eventually the pieces of a Pentium will go so small that they'll be the size of atoms. This is predicted to happen somewhere between 15-20 years from now, in which Intel won't be able to make their processors go faster anymore by shrinking them. By then, the hope is that quantum computers will be ready to take over.
It's very hard to predict because the field is so young - about 5 years old. But, some changes that might happen involve the internet. Quantum computers are much better at computing security information than classical computers. They will really make it impossible to break into people's email and peek at their bank statements. Another application is searching. To search the web takes a long time right now which could be done much faster on quantum computers. Another example is the global positioning system (GPS), which we'll find very soon in cars and on people to find our where to go. GPS relies on extremely precise clocks that use quantum mechanics. Quantum computers will be able to improve these measurements so GPS should be able to get much better resolution. These will be enormous changes.
Right now, no person can say how much faster quantum computers are than classical computers. There are only specific programs that quantum computers can compute faster than classical computers. Running Windows or Quake are things that so far will not be any faster on quantum computers. Scientific research could vastly improve with quantum computers. Seth Lloyd showed that quantum computers can simulate quantum systems exponentially better (exponentially less memory and exponentially faster) than classical computers. Scientists right now do lots of quantum simulations on classical computers. They need huge supercomputers to do so, but quantum computers that are desktop in size could one day do much better.
I think that this field is only scratching at the surface of something giant. As long as there are no fundamental reasons why this can't work (nobody knows for sure), quantum computing will be a huge breakthrough for the world. I don't know if it will be THE breakthrough of the next century, because there are so many wonderful things in science these days, but it should definitely be important.
I would like to thank Professor Neil Gersherfeld and his colleague Yael Maguire for all their help and the time they spent to answer these questions.
Back to Technology
Reconstruction: July-August-September 2002
© Copyright 2002 Spiros Tzelepis
No part of this website is to be used or reproduced by any means without the written permission of the creator