Quantum Computing

Quantum computing is an exciting new area between theoretical computer science and quantum physics. The quantum computation has the potential to demonstrate that for some problems quantum computation is more efficient than classical computation.

A goal of quantum computing is to determine for which problems quantum computers are faster than classical computers. It is a central open problem, whether a quantum computer can solve all problems in the complexity class NP in polynomial time.

Until today, there are only two basic quantum algorithms known. The first one is Shor’s polynomial time quantum algorithm for the factorization of integers, and the second one is Grover’s search algorithm. Since then, we have seen some generalizations and applications of these two basic quantum techniques. The Shor algorithm has been generalized to a quantum algorithms for the hidden subgroup problems. Grover’s search algorithm can be used for quantum amplitude amplification and quantum random walk search.
The application of these quantum tools is a fast growing area in quantum computing. Quantum algorithms have been presented for several problems in computer science, graph theory and algebra.