SCIENCE SPIN-OFFS

[dockzef]

Efficient unitary paths and quantum computational supremacy: A proof of average-case hardness of Random Circuit Sampling

Ramis Movassagh
(Submitted on 10 Oct 2018)

One-parameter interpolations between any two unitary matrices (e.g., quantum gates) U1 and U2 along efficient paths contained in the unitary group are constructed. Motivated by applications, we propose the continuous unitary path U(?) obtained from the QR-factorization
U(?)R(?)=(1-?)A+?B,
where U1R1=A and U2R2=B are the QR-factorizations of A and B, and U(?) is a unitary for all ? with U(0)=U1 and U(1)=U2. The QR-algorithm is modified to, instead of U(?), output a matrix whose columns are proportional to the corresponding columns of U(?) and whose entries are polynomial or rational functions of ?. By an extension of the Berlekamp-Welch algorithm we show that rational functions can be efficiently and exactly interpolated with respect to ?. 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.

https://arxiv.org/abs/1810.04681