50 citations · 140 across the 23 of their papers we have counts for
Showing 2019Show all
3 papers · 1 filter
quant-ph2019★ 7 cited
Towards Optimal Separations between Quantum and Randomized Query Complexities
Avishay Tal
The query model offers a concrete setting where quantum algorithms are provably superior to randomized algorithms. Beautiful results by Bernstein-Vazirani, Simon, Aaronson, and oth…
quant-ph2019★ 1 cited
Quantum versus Randomized Communication Complexity, with Efficient Players
Uma Girish, Ran Raz, Avishay Tal
We study a new type of separation between quantum and classical communication complexity which is obtained using quantum protocols where all parties are efficient, in the sense tha…
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…