Portrait of Martin Roetteler

Martin Roetteler

Principal Researcher


I am a Principal Researcher at Microsoft Research Redmond and member of Microsoft Quantum – Redmond (QuArC). 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, compilers that can break down higher-level algorithms into elementary gate sequences and that can perform resource estimation for a variety of physical machine descriptions. I am excited to be part of a team that develops Microsoft’s Quantum Development Kit and software libraries for the quantum programming language Q#.





Committee work

Conference/workshop organization


Tools to Optimize Resources in Quantum Engineering (TORQUE)

  • Funded by the Intelligence Advanced Research Projects Activity (IARPA), 2011-2013
  • Project partners: Raytheon/BBN Technologies, NEC Labs America, University of Waterloo, University of Melbourne, CQT Singapore.
  • My role: PI

Short summary: The goal of this project was to build a toolbox for end-to-end compilation of quantum algorithms that are expressed in a high-level quantum programming language down to the physical layer. Our government customer specified a set of target physical machine descriptions from which our tools automatically generated a set of primitive gates that could be used to implement fault-tolerant quantum computing protocols, such as the surface code or concatenated block codes. At the logical layer, we developed a domain-specific functional quantum programming language that allows the programmer to write code in a mathematical and almost entirely circuit-free way. Using several rewriting and circuit synthesis stages, this program is then transformed into a sequence of elementary gates for the target fault-tolerant protocol, where the primary target gate set was the set of Clifford+T operations.

The TORQUE team was truly interdisciplinary in that it consisted of computer scientists, physicists, and software engineers across 4 sub-teams and 5 institutions from academia and industry which were located in the US, Canada, and Australia. The team had over 25 members. My management style as the PI of this project was congruent with that of our primary BBN and our sub-team leads with whom I worked closely to meet the project milestones. We communicated constantly with the IARPA program management and applied agile management techniques to deal with challenging requirements and accommodate the government customer’s needs.

Sense and Sensitivity: towards domain-specific social networks

  • NEC Seeds Project, 2012
  • My role: co-PI

Short summary: In this exciting exploratory research project, which won NEC Labs’ internal Seeds competition in 2012, we considered a sensor scenario where users collect a combination of environmental and biometrical data using smartphones that are connected to sensors using bluetooth interfaces. We bootstrapped a test group of 25 people and collected data for a few weeks and showed a proof of concept that it is possible to extract latent features that are common to different participants using data mining techniques.

NEC Algorithms Project (NECAP)

  • Funded by the Army Research Office (ARO) and the National Security Agency (NSA), 2009-2012
  • Project partners: NEC Labs America
  • My role: PI

Short summary: A salient feature of quantum computers is that they can solve certain problems more efficiently than any classical machine, the ultimate goal being exponential separations in complexity. In this project we showed that a quantum computer can solve certain correlation tasks in a way that is much faster than any classical algorithm can. One of our main accomplishments was to show that for large classes of Boolean functions it is possible to identify an unknown shift of the function by computing a correlation with another function. Mathematically, a recurring theme in the project was to exploit properties of the quantum Fourier analysis of Boolean functions.

I was the sole PI of this project which was extended twice for a full duration of three years, during which our group wrote 13 project publications that were published at profile venues including SODA, FOCS, and ICALP.

QKD meets PON: protocols to secure the last mile (PROSECCO)

  • NEC Seeds Project, 2009
  • My role: co-PI

Short summary: Our goal was to show that highly efficient secure communication is possible without having to rely on computational assumptions. The key idea was to combine the advantaged offered by quantum key distribution (QKD) with those of passive optical networks (PON), a widely deployed technology, in order to achieve high secret key generation rates. We proposed an infrastructure for QKD-WDM-PON networks that is based on the “plug & play” method and synchronization between quantum and classical channels. Our work got published at CLEO and led to a patent filing.

Errors without terrors: defect tolerance and compilation for nano circuits

  • NEC Seeds Project, 2006-2007
  • My role: co-PI

Short summary: In this interdisciplinary project, which won the NEC internal Seeds competition in 2006 we considered nano-computers which are made of faulty processing elements (PEs). The basic computational element we considered was that of a programmable junction in a 2D crossbar. We assumed that a very large fraction of PEs will have defects and developed a compiler that can nevertheless map target Boolean functions to computational fabrics that consist of such flawed PEs. In a follow-up internship we studied fault-tolerance in modern processor architectures and obtained a result about data race detection using transactional memory. The work related to this project got published at ACM Journal of Emerging Technology and the SPAA conference.

IQC Quantum Algorithms Project

  • Funded by DARPA, ARO, and NSA, 2003-2004
  • Project partners: Institute for Quantum Computing, University of Waterloo
  • My role: Team member

Short summary: I was a member of the IQC Quantum Algorithms Project funded by DARPA, ARO, and NSA. PIs were Michele Mosca and Ashwin Nayak (both IQC). My task was to contribute new research results on quantum algorithms and to publish papers in journals and conference proceedings.

Quantum computation: novel algorithms and their many-body implementations (Q-ACTA)

  • Funded by the European Commission IST/FET program, 2000-2002
  • Project partners: University of Karlsruhe, ISI Torino, Royal Holloway London.
  • My role: Team member

Short summary: The goal of this project was to find new quantum algorithms. We focused on quantum Fourier transforms for finite groups, in particular special classes of solvable groups for which the Fourier transform has a concise description. Other aspects of the project were quantum error correction where among the main achievements were the discovery of a class of quantum codes that can be constructed representation-theoretically (Clifford codes) and which can be seen as a precursor to subsystem codes. Overall project coordinator of this project was Professor Thomas Beth (University of Karlsruhe). I was responsible for scientific and administrative coordination at U Karlsruhe. I helped to supervise one graduate student, compiled all project reports, and organized semi-annual project meetings with the project partners.

Summer internships supervised

2017: Thomas Häner (ETH Zurich)

2016: Thomas Häner (ETH Zurich)

2015: Matthew Amy (IQC, University of Waterloo)

2014: Alex Parent (IQC, University of Waterloo)

From 2007 until 2013, I organized the summer internship program of NEC’s Quantum IT group and hosted talented student researchers in quantum computing from the US and abroad. Following is a list of interns that I supervised or co-supervised, together with their affiliations at the time of the internship:

2013: Stacey Jeffery (IQC, University of Waterloo)

2012: Alex Parent (IQC, University of Waterloo), Qingye Jiang (Columbia University)

2011: Iasonas Petras (Columbia University), Tian Zhong (MIT)

2010: Loick Magnin (LRI Paris), Maris Ozols (IQC, University of Waterloo)

2009: Maris Ozols (IQC, University of Waterloo), Yi Zhao (University of Toronto)

2008: Bill Fefferman (University of Chicago), Rajat Mittal (Rutgers University), Thomas Vidick (ENS Paris)

2007: Pradeep Sarvepalli (Texas A&M University), Marcus Silva (IQC, University of Waterloo), Shantanu Gupta (University of Michigan)

2006: Jamie Batuwantudawe (IQC, University of Waterloo), Muzaffer Simsir (Princeton University)

Français du Canada English