I am an Assistant Professor in the Computer Science and Engineering and Mathematics departments at the University of California, San Diego. My research is in quantum complexity theory. I am particularly interested in near-term quantum computing paradigms and proving that they exhibit some kind of quantum advantage over their classical counterparts.

Previously, I was a postdoc at the Institute for Quantum Computing at the University of Waterloo. I completed my PhD at MIT in Computer Science under the supervision of Scott Aaronson. I received a B.S. in Computer Science and Mathematics at the University of South Carolina.

I'm currently looking for students! If you're interested in working with me, apply to UCSD and mention my name in your application. Current UCSD students should feel free to email me directly.

Teaching

Selected Research

  • The Complexity of Bipartite Gaussian Boson Sampling (talk) BosonSampling is a popular proposal for a task that a quantum computer could easily solve that no classical device could efficiently simulate. In this work, we give a modified version of this proposal (BipartiteGBS) and prove that it can lead to classical intractability in regimes which are more suitable for near-term experiments than traditional BosonSampling.
  • Interactive Shallow Clifford Circuits: Quantum Advantage Against NC^1 and Beyond (talk) Most proofs that quantum computers outperform classical computers are predicated on a number of conjectures. However, when comparing low-depth quantum circuits to low-depth classical circuits, a different story emerges—unconditional separations exist. In this line of work, we prove one of the largest-known separations of this type based on an interactive protocol with a particularly simple type of shallow quantum circuit.
  • Fast Simulation of Planar Clifford Circuits Low-depth classical circuits provably cannot simulate simple low-depth quantum circuits. What happens when we remove the depth restriction for these tasks? In this work, we show that extremely efficient classical algorithms exist. These classical simulation algorithms are tightly connected to solving systems of linear equations defined over planar graphs, and in fact, our work improves some of the best-known algorithms for those problems.

Contact

email: dgrier@ucsd.edu
office: CSE 4218