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 als. (Dis)Proving the quantum supremacy conjecture requires approximate average case hardness; this remains an open problem for all quantum supremacy proposals.
Download