Sampling weakly depolarized constant-depth random circuits

Unsolved ID op_3a7c93378a832c01 Last edited 16 September 2026

Edit

Field: Quantum Algorithm
Topics: Random circuit sampling
Computational complexity and computability
Quantum supremacy

Problem

Can weak final-layer depolarizing noise make constant-depth two-dimensional Haar-random circuits classically samplable to inverse-polynomial total-variation error?

Let \(n=L^2\) qubits occupy an even-sided square grid. Apply a fixed-depth nearest-neighbor brickwork circuit \(U\) of independent Haar-random two-qubit gates to \(|0^n\rangle\), followed on every qubit by

\begin{equation} \mathcal D_\gamma(X)=(1-\gamma)X+\gamma\operatorname{Tr}(X)I/2. \tag{1} \end{equation}

Let \(P_{U,\gamma}\) be the computational-basis output distribution. For fixed \(a>0\), set \(\varepsilon=n^{-a}\) and \(\gamma=K\log(n/\varepsilon)/n\). Is there a constant \(d_0\) such that, for every fixed depth \(d>d_0\), some constant \(K>0\) permits a polynomial-time classical sampler with output distribution \(Q_U\) satisfying

\begin{equation} \mathbb E_U\|Q_U-P_{U,\gamma}\|_{\mathrm{TV}}\leq\varepsilon, \qquad \|P-Q\|_{\mathrm{TV}}=\frac12\sum_x|P(x)-Q(x)|? \tag{2} \end{equation}

Equation (2) is the target for the noise channel in Eq. (1).

Source

This precise formulation is editor wording based on the unresolved direction and limitations documented in the cited primary literature [Liu26][Go26]; it is not presented as a verbatim conjecture of those authors.

Progress

Liu, McGinley, Schuster, and Gosset prove this sampling guarantee conditional on their Scrooge hypothesis. Theorem 1 states the threshold

\begin{equation} \gamma=\Omega\!\left(\frac{\log(n/\varepsilon)}n\right). \tag{3} \end{equation}

Its end-matter proof establishes the stronger final-layer-only noise formulation used here; intermediate depolarizing noise can then be absorbed into randomly modified gates. [Liu26]

The displayed definitions, constraints, and target bounds are recorded in Eqs. (3).
The hypothesis concerns conditional ensembles produced by measuring a region, not the global circuit becoming Haar random. The paper supplies statistical-mechanical and Clifford-circuit numerical evidence, but does not prove the required Haar-circuit hypothesis. [Liu26]
The July 2026 noisy-RCS hardness result does not settle this question: its hardness assumption concerns ideal probability estimation at \(2^{-n}/\operatorname{poly}(n)\) precision and is expressly inapplicable to generic sublogarithmic-depth parallel architectures. Constant depth is precisely such a different regime. [Go26]
The 12 August 2026 paper retains the Scrooge hypothesis as a conjecture. No unconditional proof of this vanishing-noise sampling guarantee was located. [Liu26][Go26]

Comment

This asks for an unconditional algorithmic consequence of a published conjecture, not for the full Scrooge hypothesis itself. In the replacement interpretation of depolarizing noise, the target uses only \(n\gamma=O(\log n)\) expected final-layer replacements, making it a sharp test of the noise fragility of shallow-circuit sampling.

References

[Liu26]: Y. Liu, M. McGinley, T. Schuster, and D. Gosset, "Conditional dependence and Scrooge ensembles in shallow random quantum circuits," arXiv preprint (2026), version 1, 12 August 2026.arXiv
[Go26]: B. Go, C. Oh, and H. Jeong, "Hardness and Complexity Transition of Noisy Random Circuit Sampling," arXiv preprint (2026), version 1, 23 July 2026.arXiv

Sampling weakly depolarized constant-depth random circuits

Problem

Source

Progress

Comment

References

Cite this problem

BibTeX

Plain text

Problem

Source

Progress

Comment

References

Related problems