  One-parameter interpolations between any two unitary matrices (e.g., quantum
gates) $U_1$ and $U_2$ along efficient paths contained in the unitary group are
constructed. Motivated by applications, we propose the continuous unitary path
$U(\theta)$ obtained from the QR-factorization \[
U(\theta)R(\theta)=(1-\theta)A+\theta B, \] where $U_1 R_1=A$ and $U_2 R_2=B$
are the QR-factorizations of $A$ and $B$, and $U(\theta)$ is a unitary for all
$\theta$ with $U(0)=U_1$ and $U(1)=U_2$. The QR-algorithm is modified to,
instead of $U(\theta)$, output a matrix whose columns are proportional to the
corresponding columns of $U(\theta)$ and whose entries are polynomial or
rational functions of $\theta$. By an extension of the Berlekamp-Welch
algorithm we show that rational functions can be efficiently and exactly
interpolated with respect to $\theta$. We then construct probability
distributions over unitaries that are arbitrarily close to the Haar measure.
  Demonstration of computational advantages of NISQ over classical computers is
an imperative near-term goal, especially with the exuberant experimental
frontier in academia and industry (e.g., IBM and Google). A candidate for
quantum computational supremacy is Random Circuit Sampling (RCS), which is the
task of sampling from the output distribution of a random circuit. The
aforementioned mathematical results provide a new way of scrambling quantum
circuits and are applied to prove that exact RCS is $\#P$-Hard on average,
which is a simpler alternative to Bouland et al's. (Dis)Proving the quantum
supremacy conjecture requires "approximate" average case hardness; this remains
an open problem for all quantum supremacy proposals.
