Quantum Computation and Information

Quantum computation is a fascinating new area that touches upon the foundations of both quantum physics and computer science. Quantum computers can perform certain tasks, such as factoring, exponentially faster than classical computers. This talk will describe the principles underlying the fundamental quantum algorithms.The power of quantum computation lies in the exponentially many hidden degrees of freedom in the state of an n quantum bit system – whereas 2n – 1 complex numbers are necessary to specify the state, Holevo’s theorem states that n quantum bits cannot be used to communicate any more than n classical bits. Nevertheless, there are communication tasks in which these hidden degrees of freedom can be tapped into.Finally, the state of a quantum system is particularly fragile to noise and decoherence. However, there are beautiful techniques – quantum error-correcting codes – for protecting a given quantum state (with its exponentially many degrees of freedom) against noise and decoherence. These codes can be used to create fault-tolerant quantum circuits – which are immune to a constant rate of decoherence.