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

Abstract

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(θ)R(θ)=(1-θ)A+θ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.

17 pages, 3 figures

References in corpus (3)

• Black holes as mirrors: quantum information in random subsystems
• Quantum Computational Supremacy
• Approximate unitary $t$-designs by short random quantum circuits using nearest-neighbor and long-range gates

Cited by in corpus (8)

• A flexible high-performance simulator for verifying and benchmarking quantum circuits implemented on real hardware
• Efficient classical simulation of random shallow 2D quantum circuits
• Efficient classical simulation of noisy random quantum circuits in one dimension
• Random quantum circuits anti-concentrate in log depth
• NISQ Computers: A Path to Quantum Supremacy
• Quantum supremacy and random circuits
• A game of quantum advantage: linking verification and simulation
• Sampling and the complexity of nature