Quantum Information Processing

In recent years, quantum information science has emerged as a major research area at the intersection of physics, information theory, and computer science. It originated from the realization that information is not a purely abstract concept but depends on the physics of the systems in which it is represented.

Many computational problems that turn up in industry, operations research, network design, artificial intelligence, simulation of physical systems, logic, number theory, algebra, and computational biology lack a fast or feasible algorithmic solution. The best available algorithms for these problems are often extraordinarily slow. One of the central open problems in computer science is the question of whether this slowness is inherent in these problems or whether we simply lack good programming techniques.  This is known as the question which problems lie in the complexity class P (solution time polynomial in input size), which lie in NP (solution time non-polynomial in input size) and the question whether these classes are distinct at all. Quantum Information Science and in particular quantum computing gained a lot of momentum after the breakthrough result of Shor who demonstrated that the factoring problem, which is thought to be outside P on a classical computer, can be solved efficiently on a quantum computer. Shor's result presents some evidence that quantum computers can solve certain computational problems more efficiently than classical computers. Further progress has been achieved in finding applications that are either provably impossible or considerably less efficient on classical devices. Examples include the possibility of unconditionally secure key distribution (which is now being offered commercially), algorithms that provide efficient solutions for problems that are believed to be hard on any classical device, and more efficient solutions to communication problems.

These results indicate the potential power and implications of quantum information processing devices. For example, most of modern cryptography is based on the fact that no fast algorithms for the factorization problem are known.  However with a working quantum computer all of modern cryptography, including electronic banking and Internet security, will be broken.

The main focus of quantum information processing has been twofold. On one side there has been a lot of effort in the physical implementation of quantum information devices and qubits.  On the other, there has been a considerable effort in finding new algorithms and applications of quantum information processing. This workshop focuses on the second area: finding novel quantum information protocols and applications. We will invite people from computer science, theoretical physics, and mathematics. As a by product, we believe that a better understanding of the algorithmical issues of quantum information processing will help the implementation side as well.