^{SENIOR RESEARCHER}

Quantum Architectures and Computation Group (QuArC)

Microsoft Research

One Microsoft Way

Redmond, WA 98052, USA

E-mail: martinro@microsoft.com

Phone: (425) 706-3473

I am a Senior Researcher at Microsoft Research Redmond and member of the Quantum Architectures and Computation (QuArC) group. Prior to joining MSR, I was a Senior Research Staff Member at NEC Laboratories America (2005-2013) and the leader of NEC's Quantum IT group. I was a post-doctoral fellow at the Institute for Quantum Computing, Waterloo, Canada (2003-2004). I received my Ph.D. degree from the University of Karlsruhe, Germany (2001). My research is centered around quantum algorithms, quantum error-correction, quantum circuits, and digital signal processing.

I am passionate about finding new examples of problems for which a quantum computer *dramatically* outperforms any classical computer. In particular, I am interested in problems where an exponential speedup compared to the best known classical algorithm can be achieved by using a quantum computer. Not many such problems are currently known, arguably the most well-known cases are Shor's algorithms for factoring and dlog and the simulation of a wide range of quantum mechanical systems on a quantum computer. A problem that I like in particular is the so-called hidden shift problem in which one has to identify an unknown offset in the argument of a function. I showed that for certain Boolean functions that are used in cryptography, such hidden shift problems can be solved efficiently, a result which was subsequently generalized to broader classes of functions.

Starting in 2011, I changed my research area almost completely and started to work on quantum programming languages, quantum circuit synthesis, and more generally, a compiler system that can break down higher-level algorithms into elementary gate sequences and that can perform resource estimation for a variety of physical machine descriptions.

- Alex Bocharov, Martin Roetteler, and Krysta M. Svore, Efficient Synthesis of Probabilistic Quantum Circuits with Fallback, September 2014
- M. Rötteler and R. Steinwandt, A note on quantum related-key attacks, in
*Information Processing Letters*, vol. 115, pp. 40–44, 26 August 2014 - M. Rötteler and R. Steinwandt, A quantum circuit to find discrete logarithms on ordinary binary elliptic curves in depth O(log^2 n), in
*Quant. Inform. & Comp.*, vol. 14, no. 9&10, pp. 888-900, Rinton Press, July 2014 - Nathan Wiebe and Martin Roetteler, Quantum arithmetic and numerical analysis using Repeat-Until-Success circuits, no. MSR-TR-2014-103, 19 June 2014
- N. de Beaudrap and M. Rötteler, Quantum linear network coding as one-way quantum computation, in
*Proceedings TQC'14, to appear*, LIPIcs Leibniz International Proceedings in Informatics, May 2014 - Alex Bocharov, Martin Roetteler, and Krysta M. Svore, Efficient Synthesis of Universal Repeat-Until-Success Circuits, 23 April 2014
- G. Chiribella, G. M. D'Ariano, and M. Rötteler, Identification of a reversible quantum gate: assessing the resources, in
*New Journal of Physics*, vol. 15, pp. 103019, IOP, October 2013