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 查看全文>>