652 citations · 956 across the 19 of their papers we have counts for
Showing 2011Show all
2 papers · 1 filter
quant-ph2011
Advice Coins for Classical and Quantum Computation
Scott Aaronson, Andrew Drucker
We study the power of classical and quantum algorithms equipped with nonuniform advice, in the form of a coin whose bias encodes useful information. This question takes on particul…
quant-ph2011
Impossibility of Succinct Quantum Proofs for Collision-Freeness
Scott Aaronson
We show that any quantum algorithm to decide whether a function f:[n]->[n] is a permutation or far from a permutation must make Omega(n^{1/3}/w) queries to f, even if the algorithm…