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

Preprint · Ramis Movassagh

- Archive id: arxiv:1810.04681
- Published: 2018-10-10
- arXiv: https://arxiv.org/abs/1810.04681
- Citations: 13
- Source URL: https://arxiv.org/abs/1810.04681
- PDF: https://arxiv.org/pdf/1810.04681
- Provenance: arxiv

## 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(θ)$ 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(θ)$ is a unitary for all $θ$ with $U(0)=U\_1$ and $U(1)=U\_2$. 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.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

Topics: [Quantum Algorithms & Quantum Advantage](https://space-kitty.com/topics/quantum-algorithms-advantage)

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.