Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Luke Schaeffer:

TR19-089 | 21st June 2019
Adam Bene Watts, Robin Kothari, Luke Schaeffer, Avishay Tal

Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits

Recently, Bravyi, Gosset, and K├Ânig (Science, 2018) exhibited a search problem called the 2D Hidden Linear Function (2D HLF) problem that can be solved exactly by a constant-depth quantum circuit using bounded fan-in gates (or QNC^0 circuits), but cannot be solved by any constant-depth classical circuit using bounded fan-in AND, ... more >>>

TR19-061 | 16th April 2019
Scott Aaronson, Daniel Grier, Luke Schaeffer

A Quantum Query Complexity Trichotomy for Regular Languages

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 >>>

ISSN 1433-8092 | Imprint