Martin Roetteler (Microsoft Research) - Quantum Computing -- Power and Limitations

Date of Presentation: 
Wednesday, March 4, 2015
2015 Winter
Research Focus: 

Title: Quantum Computing -- Power and Limitations
Abstract: Many research groups around the world are working on the
challenge of building a quantum computer. The information processing
and communication capabilities of such a device would be dramatically
different from any classical computer. The differences range from speedups
for algorithmic problems to the prospect of unconditionally-secure
cryptography. Concepts of quantum information and computing have even
changed the way researchers think about physics and computers.
I will give an overview of the basic principles of quantum computing
and will address, both, the power and the limitations of this model of
computation: Regarding the power of quantum computing, I will
present recent quantum algorithms for so-called hidden subgroup problems
and hidden shift problems, both of which are designed to leverage feature
extraction properties of the Fourier transform. Regarding limitations,
I will present a lower bound for approaches to tackle the graph isomorphism
problem via reductions to the hidden subgroup problem.
Bio: Martin Roetteler received a Ph.D. in computer science from the University of Karlsruhe, Germany, in
2001. Subsequently, he held a post-doc position at the Institute for Quantum Computing at U Waterloo
(2003-2004) and was a Research Staff Member at NEC Laboratories America (2005-2013) and the leader of
NEC's Quantum IT group. In 2013, Martin joined Microsoft Research in Redmond as a Senior Researcher. He published more than 90 refereed journal and conference papers and is co-author of one book on quantum
information. Martin's research focuses on quantum algorithms and quantum error-correction.