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 quantum circuit to find discrete logarithms on ordinary binary elliptic curves in depth O(log^2 n)Martin Roetteler, R. Steinwandt, in Quant. Inform. & Comp., Rinton Press, July 1, 2014,
Quantum Algorithms to Solve the Hidden Shift Problem for Quadratics and for Functions of Large Gowers NormMartin Roetteler, in Proceedings SODA'10, ACM-SIAM Press, January 1, 2011,
Algebraic Signal Processing Theory: Cooley-Tukey Type Algorithms on the 2-D Hexagonal Spatial LatticeMarkus Puschel, Martin Roetteler, Springer, March 26, 2008,
On Approximately Symmetric Informationally Complete Positive Operator-Valued Measures and Related Systems of Quantum StatesAndreas Klappenecker, Martin Roetteler, Igor Shparlinski, Arne Winterhof, March 31, 2005,
Von N^2 nach log^2 N – Zur algebraischen Berechnungskomplexität allgemeiner Fouriertransformationen (in German)Bjorn Grohmann, Martin Roetteler, in Proceedings GI Jahrestagung 1999 (Paderborn), Springer Berlin Heidelberg, February 2, 1999,
- PQCrypto 2017, PQCrypto 2016, PQCrypto 2014
- ICITS 2016
- QIP 2015
- TQC 2011 (PC chair), TQC 2010
- AQIS 2012, AQIS 2011, AQIS 2010
- TQC steering committee (since 2011)
- DIMACS executive committee and council member (2007-2013)
- QIP 2017, Seattle, WA, USA, 2017. Member of the local organizing committee.
- Quantum Computer Science, Banff, 2016. Co-organizer
- Quantum Programming Languages and Circuits Workshop, IQC Waterloo, 2015. Co-organizer.
- 3rd Workshop on Quantum Cryptanalysis, Dagstuhl, Germany, 2015. Co-organizer.
- 2nd Workshop on Quantum Cryptanalysis, Dagstuhl, Germany, 2013. Co-organizer.
- 1st Workshop on Quantum Cryptanalysis, Dagstuhl, Germany, 2011. Co-organizer.
- 3rd NEC/MIT Workshop, Izu, Japan, 2009. Co-organizer.
- 2nd NEC/MIT Workshop, Princeton, 2007. Co-organizer.
- Rutgers/NEC seminar “Quantum Computation: Theory and Implementations”, 2006-2011. Co-organizer.
- CSSQI 2004, Waterloo, Canada, 2004. Co-organizer.
- QIP 2004, Waterloo, Canada, 2004. Member of the local organizing committee.
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
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)
2006: Jamie Batuwantudawe (IQC, University of Waterloo), Muzaffer Simsir (Princeton University)