Posted by: jbayley | October 7, 2008

## Quantum Computing

My problem set this week in CS50 deals with cryptography and cracking encoded information, so I thought writing on the subject of quantum computers seemed relevant because I wish I had one instead of my binary computer to make the p set go much more quickly.

A quantum computer is a device that uses phenomena of quantum mechanics such as superposition and entanglement to perform operations and computations.  Unlike a normal computer, which uses binary bits to store data and perform operations, a quantum computer uses qubits which can hold a 0, a 1, or quantum superposition of the two states because quantum mechanics allows for particles to be in indeterminate states.  The main advantage of a quantum computer is that it can manipulate multiple qubits at a time, allow for the computer to operate in different states simultaneously.  This is because each additional qubit leads to double the number of states, so that a n-qubit computer can exist in 2n states simultaneously, while a classical computer which can only be in one of those 2n states at a given time.

The primary potential use for quantum computers is in encryption and decryption because they are much more efficient at factoring huge numbers than classical computers.  For example, consider a problem where the only way to solve it is to guess an check, with some number n of equally likely possibilities, all of which take an identical amount of time to generate and check.  The time it would take a quantum computer to solve the problem would be on the order of the square root of n, which can take a problem that could take a regular computer years to solve and reduce it to mere seconds.  If a decent quantum computer existed today, no information on the Internet would be safe.

That said, quantum computers seem to still be quite far from being practical as yet, although a Canadian company, D-Wave, created a 16-qubit computer in 2007 that solved sudoku puzzles and other pattern matching problems (here is a video).  Skeptics believe quantum computers are still a long way off from being useful; however, it seemed like it solved that puzzle significantly faster than I could which seems pretty helpful.

If you’d like to learn more about quantum computing or the mystifying and highly confusing world of quantum mechanics, I recommend wikipedia or a physics concentrator.