652 citations · 1.1k across the 27 of their papers we have counts for
4 papers · 1 filter
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…
On the Hardness of Detecting Macroscopic Superpositions
Scott Aaronson, Yosi Atia, Leonard Susskind
When is decoherence "effectively irreversible"? Here we examine this central question of quantum foundations using the tools of quantum computational complexity. We prove that, if…
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…
New Approaches for Quantum Copy-Protection
Scott Aaronson, Jiahui Liu, Qipeng Liu +2
Quantum copy protection uses the unclonability of quantum states to construct quantum software that provably cannot be pirated. Copy protection would be immensely useful, but unfor…