Introduction to quantum computing

Let’s start with the Wikipedia definition:

A quantum computer is any device for computation that makes direct use of distinctively quantum mechanical phenomena, such as superposition and entanglement, to perform operations on data. In a classical (or conventional) computer, information is stored as bits; in a quantum computer, it is stored as qubits (quantum bits). The basic principle of quantum computation is that the quantum properties can be used to represent and structure data, and that quantum mechanisms can be devised and built to perform operations with this data.

What is a superposition? What is entanglement? Can quantum computers compute NP problems in P? It’s hard get started in this strange field.

Scott AaronsonFirst the basics: Quantum Computing for High School Students by Scott Aaronson is an easy to read introduction to quantum computing in general.

You’ve heard quantum computers can break RSA? Theoretically you’re right. Using Shors Algorithm they can. I won’t explain this here, because Scott Aaronson again has written a beautiful and readable explanation.

Those two links should give you a good start. If not, just read on through Scotts blog.

What you should know about quantum computers: They are not a magic weapon to make computers faster. They can’t compute all NP problems in polynomial time. They are no silver bullet. Quantum computers can solve specific problems due to the quantum phenomenons. Some problems (like breaking RSA) can be reduced to these specific problems.

Currently scientists can build small quantum computers consisting of 7 qubits and have successfully factorized 15 into 5 and 3 in 2001. It’s an engineering problem to scale up the qubits to factorize bigger numbers.

My prediction: It’ll take some time, but eventually (probably decades) we will build quantum computers and scale them up to thousands of qubits. They won’t replace traditional CPUs though, but will work as a coprocessor like Cell.

The scary sidenote for a good discussion (recommended to combine with some drinks): What will happen with the world, once we break RSA? Public key encryption won’t work anymore. No online banking, no e-commerce, no cheap and secure communication anymore. Economy breaks down and world war III wipes out all humans?

Published in: on September 20, 2007 at 12:10 pm  Comments (2)