Yaoyun Shi

We initiate the study of quantifying the quantumness of

a quantum circuit by the number of gates that do not preserve

the computational basis, as a means to understand the nature

of quantum algorithmic speedups.

Intuitively, a reduction in the quantumness requires

an increase in the amount of classical computation, ...
more >>>

Aran Nayebi, Scott Aaronson, Aleksandrs Belovs, Luca Trevisan

Given a random permutation $f: [N] \to [N]$ as a black box and $y \in [N]$, we want to output $x = f^{-1}(y)$. Supplementary to our input, we are given classical advice in the form of a pre-computed data structure; this advice can depend on the permutation but \emph{not} on ... more >>>