153 citations · 237 across the 10 of their papers we have counts for
Showing 2002Show all
3 papers · 1 filter
quant-ph2002
Quantum Certificate Complexity
Scott Aaronson
Given a Boolean function f, we study two natural generalizations of the certificate complexity C(f): the randomized certificate complexity RC(f) and the quantum certificate complex…
quant-ph2002★ 5 cited
Quantum Lower Bound for Recursive Fourier Sampling
Scott Aaronson
One of the earliest quantum algorithms was discovered by Bernstein and Vazirani, for a problem called Recursive Fourier Sampling. This paper shows that the Bernstein-Vazirani algor…
quant-ph2002★ 1 cited
Quantum Computing and Dynamical Quantum Models
Scott Aaronson
A dynamical quantum model assigns an eigenstate to a specified observable even when no measurement is made, and gives a stochastic evolution rule for that eigenstate. Such a model…