{
  "abstract": "Quantum computers are claimed to produce samples ordinary classical computers cannot reproduce. The sharpest such claim known pits constant-depth quantum circuits, given one entangled state per run, against shallow classical circuits of few-input gates and limited randomness. No efficient test was known that certifies such a claim from classical samples alone. Here we show that what such a test must read is decided by the classical class's pattern of single-bit and pair correlations, not by a distance. The test rests on one inequality: any machine producing the samples sits no further from the target than the fraction it mislabels plus the deviation of its string half, the bits beyond the label, from uniform. A collapse theorem, machine-checked in the Lean~4 proof assistant, confines that second term, one setting of the sampler's random input bits at a time. Four natural checks provably fail; a fifth, reading those same correlations, catches a far-from-target construction they cannot reach, and is exact on the class of few-input gates. The label test is proven and sample-optimal in its own tolerance up to a logarithmic factor; the fifth check is sound, not only effective, on the bounded pinned-residue class, pairwise-uniform samplers whose residue, the string's weight modulo the prime, is pinned by few seeds and whose seed sharing is bounded. What binds an experiment is the $43$-qubit entangled resource state at fidelity near $0.99$, not the readout. What remains are two named open problems; a positive answer to the first would extend the guarantee to the full class.",
  "abstract_shown": true,
  "affiliations": [],
  "article_type": null,
  "arxiv": "2610.04666",
  "author_total": 5,
  "authors": [
    {
      "name": "Zijian Gong"
    },
    {
      "name": "Zhaobin Lyu"
    },
    {
      "name": "Jingjing Hu"
    },
    {
      "name": "Dengfeng Li"
    },
    {
      "name": "Shuoming An"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/0y3yvz46qssqs.bib",
  "cited_by": 0,
  "doi": "10.48550/arxiv.2610.04666",
  "fulltext_url": null,
  "id": "0y3yvz46qssqs",
  "issns": [],
  "landing_url": "https://arxiv.org/abs/2610.04666",
  "language": null,
  "licence": "CC-BY-4.0",
  "licence_label": "CC BY 4.0",
  "licence_source": "article",
  "licence_url": "http://creativecommons.org/licenses/by/4.0/",
  "metadata_licence": "CC0-1.0",
  "native_subjects": [
    [
      "arxiv",
      "quant-ph"
    ],
    [
      "openalex",
      "1702|Quantum Computing Algorithms and Architecture"
    ]
  ],
  "openalex": "W7220746029",
  "pdf_url": "https://arxiv.org/pdf/2610.04666",
  "pmcid": null,
  "pmid": null,
  "published": "2026-10-03",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/0y3yvz46qssqs.ris",
  "sources": [
    {
      "first_seen": "2026-10-30T12:27:01Z",
      "native_id": "2610.04666",
      "source": "arxiv",
      "url": "https://arxiv.org/abs/2610.04666"
    }
  ],
  "subjects": [
    {
      "field": "physics",
      "origin": "arxiv:quant-ph",
      "subfield": "quantum"
    }
  ],
  "title": "Correlations decide a shallow-circuit advantage",
  "title_text": "Correlations decide a shallow-circuit advantage",
  "type": "preprint",
  "updated_at": "2026-10-30T12:27:01Z",
  "url": "https://research.draconitic.com/paper/0y3yvz46qssqs",
  "venue": "arXiv",
  "versions": []
}