2 citations · 4 across the 3 of their papers we have counts for
7 papers · 1 filter
On Query-to-Communication Lifting for Adversary Bounds
Anurag Anshu, Shalev Ben-David, Srijita Kundu
We investigate query-to-communication lifting theorems for models related to the quantum adversary bounds. Our results are as follows: 1. We show that the classical adversary bound…
Degree vs. Approximate Degree and Quantum Implications of Huang's Sensitivity Theorem
Scott Aaronson, Shalev Ben-David, Robin Kothari +2
Based on the recent breakthrough of Huang (2019), we show that for any total Boolean function , : The degree of…
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…
Quantum Implications of Huang's Sensitivity Theorem
Scott Aaronson, Shalev Ben-David, Robin Kothari +1
Based on the recent breakthrough of Huang (2019), we show that for any total Boolean function , the deterministic query complexity, , is at most quartic in the quantum que…
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…
Quantum distinguishing complexity, zero-error algorithms, and statistical zero knowledge
Shalev Ben-David, Robin Kothari
We define a new query measure we call quantum distinguishing complexity, denoted QD(f) for a Boolean function f. Unlike a quantum query algorithm, which must output a state close t…