Quantum Information Science (QIS) Seminar
(CSI 991 - 006)
Monday, November 28, 2005, 4:30 - 6:00 PM
George Mason University, Fairfax Campus
Science Showcase, George Johnson Center, Room 237

 
Presenter: Debabrata Ghoshal, George Mason University

Title: Quantum Computing, Complexity and Some Recent Results

Abstract: Complexity theory has its history since Alan Turing, in 1936, developed his theoretical computational model. The field is still active and with the advent of quantum computing found new interesting results and insight about the nature of different computational classes and different communication protocols. In this talk I will first introduce some basic concepts and some classes of computational complexity. A recent exciting result of classical complexity will be the part of this discussion. Next I will go over the definition and different protocols of communication complexity.  I will try to explain one interesting recent quantum communication protocol along with the necessary background and ideas needed to interpret the result. The last part of the talk will focus on another very challenging new result that reveals the fact that some quantum computational complexity class is inherently same as the classical probabilistic computational complexity class provided that there is involved some post-selection computation.

About the Author: Debabrata Ghoshal has a background in physics and computer science (MS in computer science from Boston University). He spent a good number of years in industry as software professional. His interest led him to join the Quantum Computing group of GMU and he has been a very active member of the group since its inception. He is currently working in the area of quantum computation for his PhD from the School of Computational Sciences, GMU.