XQUATH (Linear Cross-Entropy Quantum Threshold Assumption)

Let $U$ be a quantum circuit drawn from a distribution $\mathcal{D}$, and let

$$f_U(\lvert 0^n\rangle\langle 0^n\rvert):=\left\lvert\langle 0^n\rvert U\lvert 0^n\rangle\right\rvert^2.$$

A classical algorithm is polynomial-time if it runs in time polynomial in the circuit description and $n$. XQUATH (Linear Cross-Entropy Quantum Threshold Assumption). There is no polynomial-time classical algorithm that, given $U\sim\mathcal{D}$, produces a number $q(U,0^n)$ such that

$$\mathrm{XQ}:=\mathbb{E}_{U\sim\mathcal{D}}\left[\left(f_U(\lvert 0^n\rangle\langle 0^n\rvert)-2^{-n}\right)^2\right]-\mathbb{E}_{U\sim\mathcal{D}}\left[\left(f_U(\lvert 0^n\rangle\langle 0^n\rvert)-q(U,0^n)\right)^2\right]=\Omega\left(2^{-3n}\right).$$

The assumption underlies the complexity-theoretic justification for linear cross-entropy benchmarking in quantum-supremacy experiments. It was refuted for random Brickwork circuits of sublinear depth by a simple Pauli-path propagation algorithm achieving $\mathrm{XQ}=15^{-L}$, where $L$ is the circuit depth.