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 admitting students! If you're interested in working with me, apply to UCSD and mention my name in your application.
Teaching (previous years)
Students
Selected Research
  • QAC0 Contains TC0 (with Many Copies of the Input) A celebrated result in classical circuit complexity is that constant-depth circuits with unbounded AND gates (known as AC0 circuits) cannot compute the parity function. A longstanding question in quantum circuit complexity is whether or not this same separation exists in the quantum world. In this work, we give some evidence why this result may have evaded us—namely, quantum circuits with unbounded AND gates (known as QAC0 circuits) are surprisingly powerful. If given access to multiple copies of the input, such circuits cannot only compute parity, but also every symmetric Boolean function.
  • Sample-optimal classical shadows for pure states In general, to learn the output of a quantum experiment you might have to run it exponentially-many times. Fortunately, only certain features of your quantum state are important for many applications, and a popular quantum learning algorithm called classical shadows has emerged as a way to dramatically reduce the number of experiments. In this work, we show how to reduce this cost even more when you can assume the unknown quantum state is pure—a natural setting for a large range of quantum algorithms.
  • Interactive Shallow Clifford Circuits: Quantum Advantage Against NC1 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.
Contact
email: dgrier@ucsd.edu
office: CSE 4218 / AP&M 7141
CV (last updated: 3/26) Mastodon