15 citations · 21 across the 14 of their papers we have counts for
Showing 2020Show all
3 papers · 1 filter
quant-ph2020★ 15 cited
Symmetries, graph properties, and quantum speedups
Shalev Ben-David, Andrew M. Childs, András Gilyén +3
Aaronson and Ambainis (2009) and Chailloux (2018) showed that fully symmetric (partial) functions do not admit exponential quantum query speedups. This raises a natural question: h…
cs.CC2020
Communication memento: Memoryless communication complexity
Srinivasan Arunachalam, Supartha Podder
We study the communication complexity of computing functions in the memoryless communication model. Here, Alice is given $x\in \{0…
quant-ph2020★ 2 cited
How symmetric is too symmetric for large quantum speedups?
Shalev Ben-David, Supartha Podder
Suppose a Boolean function is symmetric under a group action acting on the bits of the input. For which does this mean does not have an exponential quantum spee…