153 citations · 237 across the 10 of their papers we have counts for
Showing 2003Show all
3 papers · 1 filter
quant-ph2003
Multilinear Formulas and Skepticism of Quantum Computing
Scott Aaronson
Several researchers, including Leonid Levin, Gerard 't Hooft, and Stephen Wolfram, have argued that quantum mechanics will break down before the factoring of large numbers becomes…
quant-ph2003
Lower Bounds for Local Search by Quantum Arguments
Scott Aaronson
The problem of finding a local minimum of a black-box function is central for understanding local search as well as quantum adiabatic algorithms. For functions on the Boolean hyper…
quant-ph2003
Quantum Search of Spatial Regions
Scott Aaronson, Andris Ambainis
Can Grover's algorithm speed up search of a physical region - for example a 2-D grid of size sqrt(n) by sqrt(n)? The problem is that sqrt(n) time seems to be needed for each query,…