Daniel Grier

I am a postdoc at the Institute for Quantum Computing at the University of Waterloo.
The majority of my research is in quantum complexity theory. I am particularly interested in weak models of quantum computation such as Clifford circuits and low-depth circuits.

Previously, I was a graduate student in the Theory of Computation group at MIT, where I received my PhD in Computer Science. I was advised by Scott Aaronson. I received a B.S. in Computer Science and Mathematics at the University of South Carolina where I worked with Stephen Fenner on combinatorial game theory.

CV (last updated June 2020)

Previously, I was a graduate student in the Theory of Computation group at MIT, where I received my PhD in Computer Science. I was advised by Scott Aaronson. I received a B.S. in Computer Science and Mathematics at the University of South Carolina where I worked with Stephen Fenner on combinatorial game theory.

CV (last updated June 2020)

Publications

Depth-2 QAC Circuits Cannot Simulate Quantum Parity With Daniel Padé, Stephen Fenner, Thomas Thierauf. [arXiv] |

Interactive Shallow Clifford Circuits: Quantum Advantage Against NC^1 and Beyond With Luke Schaeffer. QIP 2020 / STOC 2020. [arXiv, slides, talk] |

A Quantum Query Complexity Trichotomy for Regular Languages With Scott Aaronson and Luke Schaeffer. QIP 2019 / FOCS 2019 [arXiv, slides, talk] |

New Hardness Results for the Permanent Using Linear Optics With Luke Schaeffer. CCC 2018. [arXiv, slides] |

The Classification of Stabilizer Operations over Qubits With Luke Schaeffer. QIP 2018. [arXiv] |

The Classification of Reversible Bit Operations With Scott Aaronson and Luke Schaeffer. ITCS 2017. [arXiv, slides] |

On the Complexity of Probabilistic Trials for Hidden Satisfiability Problems With Itai Arad, Adam Bouland, Miklos Santha, Aarthi Sundaram, and Shengyu Zhang. MFCS 2016. [arXiv] |

Game Values and Computational Complexity: An Analysis via Black-White Combinatorial Games With Stephen A. Fenner, Jochen Messner, Luke Schaeffer, and Thomas Thierauf. ISAAC 2015. [ECCC, slides] |

Deciding the Winner of an Arbitrary Finite Poset Game is PSPACE-complete. ICALP 2013. [arXiv, slides] |

On the Cyclic Van der Waerden Numbers. Geombinatorics 2012. [pdf] |