Introduction to quantum computing

Mario Szegedy, Dept. of Computer Science, Rutgers University

February 5, 4:30 PM, Rutgers Univ. CORE 431

Abstract.

If solutions to quantum mechanical equations are very hard to obtain, can we utilize the inherent hardness of these problems and their solutions provided by the nature to build computers that are far more powerful than their classical counterparts? This question was first raised by Richard Feynman, and the answer is still unclear. Recently, however the subject of quantum computing received a great momentum from breakthrough results of Peter Shor, who showed that at least in principle factoring large numbers (which is the mother of all code breaking) can be done in polynomial time with an imaginary quantum computer. We give an introduction to the computational model Shor used, and explain another result of Lov Grover on how to speed up exhaustive search with our imaginary quantum computer.



Back to Discrete Math/Theory of Computing seminar