Correlations decide a shallow-circuit advantage

Zijian Gong, Zhaobin Lyu, Jingjing Hu, Dengfeng Li, Shuoming An

arXivarxiv/2610.04666Oct 3, 2026quant-phscore 0

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…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2610.04666
curl -X POST /api/v1/records/arxiv/2610.04666/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.04666/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'