Average-case approximation hardness of random-circuit output probabilities

Problem

Does there exist a fixed family of \(n\)-qubit circuit layouts with \(m=\operatorname{poly}(n)\) one- and two-qubit gates for which the following task is \(\#\mathrm{P}\)-hard? Choose every gate independently from Haar measure, obtaining \(C\). Given \(C\) and \(\epsilon,\delta\in(0,1)\), estimate the all-zero output probability with

\begin{equation} p_0(C)=|\langle0^n|C|0^n\rangle|^2,\qquad \Pr_C[|\widetilde p(C)-p_0(C)|\leq\epsilon 2^{-n}]\geq1-\delta. \tag{1} \end{equation}

The guarantee in Eq. (1) must hold for arbitrary \(\epsilon,\delta\), with running time measured in \(n,1/\epsilon,1/\delta\).

Source

Conjecture 6 of Bouland, Fefferman, Nirkhe, and Vazirani (2018), in its formal version in Appendix A.4, using Definition 20 of an average-case approximate solution [BFNV19]. This is an additive-error probability-estimation conjecture; the parameters \(\epsilon,\delta\) retain the original meaning.

Progress

2018: Taylor truncation gives exact \(\#\mathrm{P}\)-hardness on an \(8/9\) fraction of perturbed, generally nonunitary instances (Theorem 1); it does not establish the desired approximation guarantee for Haar gates [BFNV19].
2019–2023: Movassagh’s Cayley path preserves unitarity and enables rational interpolation, proving exact \(\#\mathrm{P}\)-hardness on a \(3/4+1/\operatorname{poly}(n)\) fraction of Haar-random circuits (arXiv Theorem 1) [Mov23].
2021: Bouland et al. and, independently, Kondo–Mori–Movassagh obtain additive-error tolerance \(2^{-O(m\log m)}\) with constant failure probability, using \(\mathrm{BPP}^{\mathrm{NP}}\) reductions [BFLL22][KMM22].
2022: Krovi improves the tolerance to \(2^{-O(m)}\) for a constant fraction of Haar-random circuits, via \(\mathrm{BPP}\) reductions; the hardness class is \(\mathrm{coC}_{=}\mathrm{P}\), rather than \(\#\mathrm{P}\) [Kro22].
2025: Bouland et al.’s dilution method gives \(\#\mathrm{P}\)-hardness at error \(2^{-n-O(n^\gamma)}\) for suitable depth-\(\Omega(\log n)\) RCS ensembles, for every fixed \(\gamma>0\) (Corollary 2, \(\mathrm{BPP}^{\mathrm{NP}}\) reduction) [BDFH25].

Comment

The original approximation conjecture remains open. The 2025 result still has an \(O(n^\gamma)\) loss in the exponent, rather than the \(O(\log n)\) loss corresponding to error \(2^{-n}/\operatorname{poly}(n)\) [BDFH25]. Exact hardness and smaller additive-error hardness do not settle this gap.

References

[BFNV19]: A. Bouland, B. Fefferman, C. Nirkhe, and U. Vazirani, "On the complexity and verification of quantum random circuit sampling," Nature Physics 15, 159–163 (2019).(2018 preprint titled "Quantum Supremacy and the Complexity of Random Circuit Sampling").DOI arXiv
[Mov23]: R. Movassagh, "The hardness of random quantum circuits," Nature Physics 19, 1719–1724 (2023).(preprint titled "Quantum supremacy and random circuits").DOI arXiv
[BFLL22]: A. Bouland, B. Fefferman, Z. Landau, and Y. Liu, "Noise and the frontier of quantum supremacy," in FOCS 2021, 1308–1317 (2022).DOI arXiv
[KMM22]: Y. Kondo, R. Mori, and R. Movassagh, "Quantum supremacy and hardness of estimating output probabilities of quantum circuits," in FOCS 2021, 1296–1307 (2022).DOI arXiv
[Kro22]: H. Krovi, "Average-case hardness of estimating probabilities of random quantum circuits with a linear scaling in the error exponent," arXiv preprint (2022).DOI arXiv
[BDFH25]: A. Bouland, I. Datta, B. Fefferman, and F. Hernandez, "Exponential improvements to the average-case hardness of BosonSampling," in FOCS 2025, 912–933 (2025).DOI arXiv

Average-case approximation hardness of random-circuit output probabilities

Problem

Source

Progress

Comment

References

Cite this problem

BibTeX

Plain text

Problem

Source

Progress

Comment

References

Related problems