Workshop on Computational, Descriptive and Proof Complexity, and Algorithms

Many computational problems that turn up in industry, operations research, network design, artificial intelligence, simulation of physical systems, logic, number theory, combinatorics, algebra, and computational biology lack a fast or feasible algorithmic solution. The best known algorithms for these problems are horrendously slow. One of the central open problems in computer science is the question of whether this slowness is inherent in these problems or that we simply lack good programming techniques. This question is known as the P versus NP question. The hardest computational problems of the above type are called NP-complete problems. It is widely believed that there does not exist a feasible algorithmic solution for these NP-complete problems.

Quantum computing devices are computing devices that take advantage of the laws of quantum mechanics, whereas classical computers only use classical mechanics. Quantum computers can outperform our current, classical, technology of computing, due to the possibility of massive exponential parallelism (the superposition principle) and interference.

Quantum computing gained a lot of momentum after the breakthrough result of Peter Shor who demonstrated that the factoring problem can be efficiently solved on a quantum computer, whereas no classical algorithm is known that solves this problem quickly. His results give some evidence that quantum computers can solve certain computational problems more efficiently than classical computers. Since most of modern cryptography is based ob our inability to efficiently factor large numbers, Shor's algorithm breaks all these cryptographic protocols.

We will introduce the mathematical framework of quantum mechanics and show how it can be used to define a quantum computer. We will then treat some of the known quantum algorithms including Shor's factorization algorithm, entanglement and the Einstein-Podolsky-Rozen paradox, quantum communication complexity, and quantum cryptography. If time permits we will mention some of the recent developments.