## Quantum Computing & Information

In the latter part of the twentieth century, and the first years of twenty first, the growth in the American economy has been driven to no small degree by Moore's Law, the exponential decrease with time of the size of the switching elements that are the basis for the physical implementation of digital computers. Moore's Law has made digital computers ubiquitous, from our iPods to our automobiles. No less important than this digital revolution was the work of Turing and other mathematicians who developed the theoretical underpinnings of programmable digital computers in the 1930s. Unfortunately, with the size of the smallest circuit element approaching 100 atoms, we are reaching the limit of Moore's Law for classical computation. Classical computing power will then increase only by increasing size and not density. Correspondingly, the speed of computing will be limited by the speed of light across the dimension of the computer. Quantum computing promises to be able to solve some problems far faster than classical computers of the same size.

Quantum computing is interdisciplinary and requires intricate and inseparable interplay of physics, mathematics, and computer science. While the intuitive idea of a quantum computer dates back to Richard Feynman, the recipient of Nobel Prize in Physics in 1965, the first shocking result was Shor's factoring algorithm discovered in 1994. Peter Shor, currently a professor at MIT, showed how a quantum algorithm could exponentially speed-up classical computation and factor large numbers into primes much faster than any known classical algorithm. Thus, if it is possible to build quantum computers, they will be significantly faster than any classical computer for certain problems. For example, in cryptography, breaking supposedly unbreakable codes would then be possible. Other recent results in this field indicate that information can be teleported, and true random numbers could be generated.

The basic unit of information in the quantum computer is a qubit, a storage element capable of holding not only a bit of information, but also a quantum connection to the originating bits called 'coherence in phase.' The technology for the construction of a small number of coupled qubits has recently been demonstrated. However, while the experimentalists are engaged in tackling tremendous technological difficulties and we await the physical realization of large scale quantum computers, we are dealing with equally, if not more challenging, theoretic problems focusing on fundamental questions of computing, information, and complexity. In 1997, Freedman and Kitaev proposed a topological model of a quantum computer that performs computations by encoding information in the configurations of braids. These computers have a built-in defense against decoherence and offer the promise of error rates many orders of magnitude lower than any other quantum computation scheme to date.

In 2002, it was proved that a topological quantum computer can perform any computation that a localized-qubit quantum computer can do. The field of topological quantum computing is full of theoretical challenges, including the formulation and classification of relative quantum phases on the mathematical side and the search for topological phases of matter on the physical side. Analysis of quantum computing may also help us better understand the quantum world, and the mathematical logic best used to describe quantum computation and information transfer.

Quantum computing activities at GW are organized by *Quantum Computation, Complexity, and Information Group* funded by the University Research Enhancement Award.