37 citations · 39 across the 6 of their papers we have counts for
Showing 2019Show all
2 papers · 1 filter
quant-ph2019
Interactive shallow Clifford circuits: quantum advantage against NC and beyond
Daniel Grier, Luke Schaeffer
Recent work of Bravyi et al. and follow-up work by Bene Watts et al. demonstrates a quantum advantage for shallow circuits: constant-depth quantum circuits can perform a task which…
quant-ph2019★ 37 cited
Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits
Adam Bene Watts, Robin Kothari, Luke Schaeffer +1
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…