Randomness extractors provide a generic way of converting sources of randomness that are
merely unpredictable into almost uniformly random bits. While in general, deterministic randomness
extraction is impossible, it is possible if the source has some structural constraints.
While much of the literature on deterministic extraction has focused on sources with strong indepen-
dence properties, a natural class where deterministic extraction is possible is sources that can sampled
by a polynomial size circuit, Levin [SIAM J Comp’86]. Trevisan and Vadhan [FOCS’00] explicitly con-
structed deterministic randomness extractors for this class of sources, assuming very strong circuit
lower bounds.
We suggest that there is perhaps an even more reasonable model of natural sources of randomness than
Levin’s: sources sampled by polynomial size quantum circuits. Under a suitable circuit lower bound,
we show that Trevisan and Vadhan’s extractor indeed works for this class.
Along the way, we substantially improve their analysis in the classical case, showing that a circuit lower
bound against NP-circuits suffice in the classical case (as opposed to a lower bounds on ?5-circuits, as
shown by Trevisan and Vadhan). Moreover, we show that under this assumption, it is possible to handle
sources sampled by postselecting circuits (a variant of nondeterministic circuits). We show that this
model is sufficient to capture randomness extraction in the presence of efficiently computable leakage.