{"id":"arxiv/2610.04666","url":"https://arxiv.org/abs/2610.04666","tags":["quant-ph"],"score":0,"title":"Correlations decide a shallow-circuit advantage","domain":"quant-ph","source":"arxiv","authors":["Zijian Gong","Zhaobin Lyu","Jingjing Hu","Dengfeng Li","Shuoming An"],"reviews":0,"subject":"quant-ph","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-10-03","reactions":{}}