Daniel Grier

STOC Conference 2020 Conference Paper

Interactive shallow Clifford circuits: quantum advantage against NC¹ and beyond

• Daniel Grier
• Luke Schaeffer

FOCS Conference 2019 Conference Paper

A Quantum Query Complexity Trichotomy for Regular Languages

• 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 Θ(1), Θ̃(√ n), or Θ(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 show can have query complexity Θ(n c ) for all computable c [1/2, 1]. Our result implies an equivalent trichotomy for the approximate degree of regular languages, and a dichotomy-either Θ(1) or Θ(n)-for sensitivity, block sensitivity, certificate complexity, deterministic query complexity, and randomized query complexity. The heart of the classification theorem is an explicit quantum algorithm which decides membership in any star-free language in Õ(√n) time. This well-studied family of the regular languages admits many interesting characterizations, for instance, as those languages expressible as sentences in first-order logic over the natural numbers with the less-than relation. Therefore, not only do the star-free languages capture functions such as OR, they can also express functions such as "there exist a pair of 2's such that everything between them is a 0. " Thus, we view the algorithm for star-free languages as a nontrivial generalization of Grover's algorithm which extends the quantum quadratic speedup to a much wider range of string-processing algorithms than was previously known. We show a variety of applications-new quantum algorithms for dynamic constant-depth Boolean formulas, balanced parentheses nested constantly many levels deep, binary addition, a restricted word break problem, and path-discovery in narrow grids-all obtained as immediate consequences of our classification theorem.

MFCS Conference 2016 Conference Paper

On the Complexity of Probabilistic Trials for Hidden Satisfiability Problems

• Itai Arad
• Adam Bouland
• Daniel Grier
• Miklos Santha
• Aarthi Sundaram
• Shengyu Zhang 0002

What is the minimum amount of information and time needed to solve 2SAT? When the instance is known, it can be solved in polynomial time, but is this also possible without knowing the instance? Bei, Chen and Zhang (STOC'13) considered a model where the input is accessed by proposing possible assignments to a special oracle. This oracle, on encountering some constraint unsatisfied by the proposal, returns only the constraint index. It turns out that, in this model, even 1SAT cannot be solved in polynomial time unless P=NP. Hence, we consider a model in which the input is accessed by proposing probability distributions over assignments to the variables. The oracle then returns the index of the constraint that is most likely to be violated by this distribution. We show that the information obtained this way is sufficient to solve 1SAT in polynomial time, even when the clauses can be repeated. For 2SAT, as long as there are no repeated clauses, in polynomial time we can even learn an equivalent formula for the hidden instance and hence also solve it. Furthermore, we extend these results to the quantum regime. We show that in this setting 1QSAT can be solved in polynomial time up to constant precision, and 2QSAT can be learnt in polynomial time up to inverse polynomial precision.