|MadSci Network: Physics|
Quantum computers are an exciting development in computer science. The Centre for Quantum Computation at Oxford is a great site with an introduction and tutorials on the subject. There are also brief introductions here and in a paper from 1999 on the subject. Here I'll mention some basic ideas about quantum computing.
In a classical digital computer, all information is represented using bits. A bit (short for binary digit) is either 0 or 1, but cannot be both at the same time. A qubit (short for quantum binary digit) can be 0, 1, or a supposition of 0 and 1. This supposition assigns a complex number to 0 and to 1, so for instance the qubit might have 0.3 + 0.4i value for 0 and 0.4 sqrt(3) – 0.3 sqrt(3) i for 1. To record the value of this qubit, we would write: (0.3,0.4)|0> + (0.4sqrt(3),0.3sqrt(3))|1>.
So a single qubit has a lot more information that a regular bit. Instead of just holding a 0 or 1, a qubit records 2 complex numbers. Now suppose that we have two regular bits. They can be either in state 00, 01, 10, or 11. A quantum computer sees a supposition of these states, so a_1|00> + a_2|01> + a_3|10> + a_4|11>, where a_1, a_2, a_3, and a_4 are complex numbers. This means that 2 qubits hold 2^2 or 4 complex numbers. If I have L qubits, then they hold 2^L complex numbers. When L = 10, 2^L = 1024, so the amount of information goes up very fast as the number of qubits grows.
There are restrictions on the type of moves that quantum computers can make compared to digital computers. Still, the ability to manupulate 2^L different values at once makes certain algorithms very fast. One problem in particular that quantum computers excel at is the ability to factor large numbers. This is a key ingredient in breaking several cryptographic schemes, and so there is much interest in building an actual quantum computer. Computers with several bits have been built, but making larger ones is a difficult engineering task. The original digital computers could only hold a few bits as well, and there is hope that quantum computers will be an important technology in the coming century.
Try the links in the MadSci Library for more information on Physics.
[an error occurred while processing this directive]