Quantum Architectures and Computation Group (QuArC)
One Microsoft Way
Redmond, WA 98052, USA
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.
- A. Bocharov, S. X. Cui, M. Roetteler, and K. M. Svore, Improved quantum ternary arithmetics, in Quantum Information and Computation, vol. 16, no. 9&10, pp. 862–884, Rinton Press, July 2016.
- A. Bocharov, M. Roetteler, and K. M. Svore, Factoring with qutrits: Shor's algorithm on ternary and metaplectic quantum architectures, no. MSR-TR-2016-21, 10 May 2016.
- A. D. Bookatz, M. Rötteler, and P. Wocjan, Improved bounded-strength decoupling schemes for local Hamiltonians, in IEEE Transactions on Information Theory, vol. 62, no. 5, pp. 2881–2894, IEEE – Institute of Electrical and Electronics Engineers, May 2016.
- Martin Roetteler, Quantum Error Correction, in Encyclopedia of Algorithms, pp. 1698–1703, Springer, April 2016.
- Matthew Amy, Martin Roetteler, and Krysta M. Svore, Verified compilation of space-efficient reversible circuits, no. MSR-TR-2016-22, 4 March 2016.
- M. Grassl, B. Langenberg, M. Rötteler, and R. Steinwandt, Applying Grover's algorithm to AES: quantum resource estimates, in Proceedings of the 7th International Conference on Post-Quantum Cryptography (PQCrypto'16), Fukuoka, Japan, Springer, February 2016.
- N. Wiebe and M Rötteler, Quantum arithmetic and numerical analysis using Repeat-Until-Success circuits, in Quantum Information and Computation, vol. 16, no. 1&2, pp. 134–178, January 2016.
- V. Kliuchnikov, A. Bocharov, M. Roetteler, and J. Yard, A framework for approximating qubit unitaries, no. MSR-TR-2015-80, 13 October 2015.
- Alex Parent, Martin Roetteler, and Krysta M. Svore, Reversible circuit compilation with space constraints, no. MSR-TR-2015-75, 2 October 2015.
- M. Grassl and M. Rötteler, Quantum MDS codes over small fields, in Proceedings of the 2015 IEEE International Symposium on Information Theory (ISIT'15), Hong Kong, IEEE – Institute of Electrical and Electronics Engineers, June 2015.