About Me

I'm a postdoc at the Institute for Quantum Computing (IQC) at the University of Waterloo. Before that, I did my PhD at MIT (under Scott Aaronson), and a BMath and MMath (under Jeffrey Shallit) at the University of Waterloo.

Research

My focus is on quantum complexity theory with recurring themes of

• Clifford circuits,
• low-depth circuits (classical and quantum), and
• classical simulation of quantum circuits.

My background is in discrete math: I've worked on combinatorial game theory, combinatorics on words (the subject of my Master's), and cellular automata.

Quantum Papers

• Classical algorithms for Forrelation
  with Sergey Bravyi, David Gosset, and Daniel Grier.
  [arxiv]
  
  
• Interactive quantum advantage with noisy, shallow Clifford circuits
  with Nathan Ju and Daniel Grier. Appeared in QIP 2021.
  [arxiv]
  
  
• Fast simulation of planar Clifford circuits
  with David Gosset, Daniel Grier, and Alex Kerzner. Appeared in QIP 2021.
  [arxiv]
  
  
• Interactive shallow Clifford circuits: quantum advantage against NC¹ and beyond
  with Daniel Grier. Appeared in QIP 2020, presented in STOC 2020.
  [arxiv]
  
  
• Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits
  with Adam Bene Watts, Robin Kothari, and Avishay Tal. Presented in QIP 2019, appeared in STOC 2019.
  [arxiv]
  
  
• A quantum query complexity trichotomy for regular languages.
  with Scott Aaronson and Daniel Grier. Appeared in QIP 2019 and FOCS 2019.
  [arxiv]
  
  
• Trading T-gates for dirty qubits in state preparation and unitary synthesis
  with Guang Hao Low and Vadym Kliuchnikov. Appeared in QIP 2020.
  [arxiv]
  
  
• New hardness results for the permanent using linear optics
  with Daniel Grier. Appeared in CCC 2018.
  [arxiv]
  
  
• The classification of stabilizer operations over qubits
  with Daniel Grier. Presented in QIP 2018.
  [arxiv]
  
  
• The classification of reversible bit operations
  with Scott Aaronson and Daniel Grier. Appeared in ITCS 2017.
  [arxiv]
  
  
• A physically universal quantum cellular automaton.
  Appeared in AUTOMATA 2015.
  [Springer]
  
  
• A physically universal cellular automaton.
  Best student paper in ITCS 2015.
  [ECCC]
  
  

Teaching

I served as a teaching assistant for the following courses.

• Design and Analysis of Algorithms (MIT, Fall 2018)
• Geometric Computation (MIT, Spring 2018)
• Advanced Algorithms (MIT, Fall 2017)
• Introduction to the Theory of Computation (Waterloo)
• Algorithms (Waterloo)

Contact

email: lrschaeffer at gmail dot com