2 citations · 2 across the 1 of their papers we have counts for
3 papers
quant-ph2020
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…