All reports by Author Daniel Grier:

__
TR19-061
| 16th April 2019
__

Scott Aaronson, Daniel Grier, Luke Schaeffer#### A Quantum Query Complexity Trichotomy for Regular Languages

__
TR16-159
| 18th October 2016
__

Daniel Grier, Luke Schaeffer#### New Hardness Results for the Permanent Using Linear Optics

__
TR15-066
| 20th April 2015
__

Scott Aaronson, Daniel Grier, Luke Schaeffer#### The Classification of Reversible Bit Operations

__
TR15-021
| 5th February 2015
__

Stephen A. Fenner, Daniel Grier, Jochen Messner, Luke Schaeffer, Thomas Thierauf#### Game Values and Computational Complexity: An Analysis via Black-White Combinatorial Games

Scott Aaronson, Daniel Grier, Luke Schaeffer

We present a trichotomy theorem for the quantum query complexity of regular languages. Every regular language has quantum query complexity $\Theta(1)$, $\tilde{\Theta}(\sqrt n)$, or $\Theta(n)$. The extreme uniformity of regular languages prevents them from taking any other asymptotic complexity. This is in contrast to even the context-free languages, which we ... more >>>

Daniel Grier, Luke Schaeffer

In 2011, Aaronson gave a striking proof, based on quantum linear optics, showing that the problem of computing the permanent of a matrix is #P-hard. Aaronson's proof led naturally to hardness of approximation results for the permanent, and it was arguably simpler than Valiant's seminal proof of the same fact ... more >>>

Scott Aaronson, Daniel Grier, Luke Schaeffer

We present a complete classification of all possible sets of classical reversible gates acting on bits, in terms of which reversible transformations they generate, assuming swaps and ancilla bits are available for free. Our classification can be seen as the reversible-computing analogue of Post's lattice, a central result in mathematical ... more >>>

Stephen A. Fenner, Daniel Grier, Jochen Messner, Luke Schaeffer, Thomas Thierauf

A black-white combinatorial game is a two-person game in which the pieces are colored either black or white. The players alternate moving or taking elements of a specific color designated to them before the game begins. A player loses the game if there is no legal move available for his ... more >>>