Quantum Hacking

by skwp

Many of the articles in 2600 deal with exploring today's computer, telephone, and electronic systems in new ways.

I wish to introduce one new system into this list - a quantum computer.  Although I will try to introduce the concept in a simple manner, quantum computing is by no means a simple subject.  It is recommended that the reader have at least some understanding of physics and chemistry.

quantum computing is an area that is being very actively researched today as one of the hottest topics in both computer science and physics.  Although scientists say that quantum computers won't be physically realized for several decades, the theoretical work that already exists makes it possible to learn about quantum computing through simulation.

Whereas current computers work with bits, i.e., movement of electricity (thousands of electrons) which we interpret to mean one or zero, a quantum computer may operate on only several quantum objects (such as atoms or electrons) and interpret their states (spin of electron or ground/excited state of atom) as a logical one or zero.

Now, without going into the reasons behind the theory, quantum mechanics states that objects can exist in indeterminate states.  For example, say we have an atom that has a fifty-fifty chance of decaying within the next half hour.  If we do not observe this atom after the half hour, quantum mechanics says it has neither decayed, nor not decayed.  Instead, it exists in neither state with equal probability.  While the concept may be strange, the theory is sound in that it explains effects observed in experiments.  For more information on why this is true, see Thomas Young's double-slit experiment in your local physics book.

The whole quantum theory has something to do with the behavior of small particles.  Basically, it is said that everything in nature has wave and particle characteristics, but small particles are small enough that we can observe their wave characteristics.  Thus, light can be said to be both an electromagnetic wave, and a stream of particles that we call photons.  Quantum theory also says that these particles exist as "probability waves" and only become real when we observe them.

The reasons for these theories are too complex to be discussed here, but it turns out that this property of objects to exist in indeterminate states can be used to create a new type of computing machine, a quantum computer, that can operate on quantum states.

A quantum computer operates on quantum bits, or "qubits," which are much similar to our bits, except that they can represent a zero, one, or a mix of a zero and one.  This mix - known as a superposition of states - collapses into a one or a zero with a certain probability for each outcome when observed.  The advantage is that while a three bit classical computer can hold the numbers from zero to seven, a quantum computer of the same size can hold the numbers zero through seven at the same time, in a "coherent superposition."

Classically, it is possible to increase computing power by adding more processors working in parallel, but to increase the power of a machine exponentially we need to add an exponential amount of processors.  This is not true in a quantum system.  By adding one "bit," the power is increased exponentially because this bit can now be part of the superposition.  Quantum computer can use this exponential power to solve problems that were before thought to be unsolvable.

Factoring is one such problem.  It is relied on heavily in modern cryptosystems because it is "hard" to factor large numbers into two prime factors.  There is no known efficient algorithm (meaning one that runs in polynomial time or less) to factor numbers.  However, in 1994, Peter W. Shor proposed an algorithm for quantum computers that would factor numbers in polynomial time, meaning that it would become as easy to factor numbers as it was to multiply them.  This means that any current encryption could be broken in a reasonable amount of time.

Thus, quantum computers will be machines that are not just "many times" faster than today's machines, but exponentially faster.  They will be able to break any code, factor large numbers, and find items in unsorted lists in an insanely short amount of time.  A good way to explore quantum computing, since such machines are not physically in existence as of yet, is to build a simulation.

I have created an open-source project for Linux to build a quantum computer simulator.  It is known as OpenQubit and is located at www.openqubit.org.  There is a ~200 person mailing list consisting of physicists, computer scientists, and anyone who cares to discuss quantum computing and related topics.

So far, we have created a working simulator that can run Shor's algorithm and factor numbers.  The only problem with simulation of such a system is its exponentially.  Because a classical computer does not operate in the same way as a quantum computer, it must use an exponential amount of memory to work.  Thus the largest number I can factor on my system with 32 MB of RAM is 63.

However, building this simulator gave me great insight into a very interesting technology that will probably become standard during our lifetime.  So get ready for the next computer revolution.

If you are interested in reading more about quantum computing, visit the web page mentioned above, or search for quantum computing (www.google.com seems particularly nice for this).

The author is the founder and project leader of the OpenQubit project.  He is a high school student who started learning about quantum mechanics as a hobby and was inspired to create a quantum computing simulator.  It is now in its third development series (0.3.x) and is code-named NewSpin.  For more information visit www.openqubit.org.  Don't be afraid to join the mailing list.