Polynomial-time sampling from peaked shallow quantum circuits with arbitrary connectivity

Yuxuan Zhang

Manuscript, version 1, 22 October 2026 (PDF, 9 pages) · LaTeX source, proof, checkers and review records (ZIP)

Can the point-probability methods for peaked shallow circuits be converted into a polynomial-time sampler without assuming a heavy output string is supplied?

Result

Fix depth \(d\) and peak exponent \(k\). For an n-qubit circuit with arbitrary connectivity, bounded-degree algebraic gate descriptions of bit length \(b\), and maximum output probability at least \(n^{-k}\), the algorithm samples within total-variation error \(\varepsilon\) in \(\operatorname{poly}_{d,k}(n,b)\) worst-case time whenever \(n^{-k}\leq\varepsilon\leq1/4\). The heavy string is not given to the algorithm.

What the argument adds

The cluster and rooted-expansion methods substantially overlap the existing point-probability analysis. The added steps are a global L1 error regrouping and a positive moment envelope with polynomial normalization. Together they support rejection sampling with a deterministic runtime cap and fully charged finite-bit arithmetic.

Coudron, Gullans, Nelson, Rajakumar and Tan, point-probability evaluation. Bravyi, Gosset and Liu, previous peaked-circuit sampling bounds.

Scope and checks

Depth and peak exponent are fixed, accuracy is inverse polynomial, and the polynomial exponents can be very large. The statement is an asymptotic complexity result rather than a practical runtime claim or a simulation theorem for arbitrary shallow circuits.

Fresh independent review checked the global error sum, unique proposal representation, invalid-proposal rejection and the precision of acceptance probabilities. Exact finite-circuit and parity-law controls were replayed separately; the asymptotic result comes from the proof.

The proof and primary-source comparisons were reviewed independently within the AI-assisted research workflow. No specific unresolved proof gap or covering result was found in the checked sources through 22 October 2026. This is internal review, not external peer review, formal certification or an exhaustive priority guarantee.

This paper is part of the 22 October 2026 ten-paper release. Its PDF and source package are posted here; the release does not add an archival DOI or claim a catalog’s acceptance.

Human and AI contributions. The work was developed in an author-directed research workflow. AI systems assisted mathematical derivation, primary-source comparison, computational checks and scientific writing. The broader research log describes the author’s direction and the research harness.