Sample-efficient benchmarking of shallow all-to-all random quantum circuits
Pith reviewed 2026-05-25 05:53 UTC · model grok-4.3
The pith
Nonlinear cross-entropy separates noisy quantum computers from classical spoofers in shallow all-to-all random circuits.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The nonlinear cross-entropy provides a sample-efficient benchmark for shallow-depth all-to-all random quantum circuits whose score cleanly separates noisy quantum computers from state-of-the-art classical spoofers, even in the presence of depolarizing noise. A binary classifier based on heavy output generation features logarithmic sample complexity at short depth. Analytic expressions for all-to-all Brownian circuit ensembles derived using replica tricks support these results, and numerical simulations corroborate them for discrete Haar-random unitary circuits.
What carries the argument
Nonlinear cross-entropy, obtained from replica-trick calculations on Brownian circuit ensembles, which quantifies output separation under depolarizing noise and enables the heavy-output binary classifier.
If this is right
- Shallow-depth regimes become verifiable even though linear cross-entropy is spoofable.
- The heavy-output classifier decides quantum versus classical origin with only logarithmically many samples at short depth.
- Depolarizing noise leaves a usable gap between quantum and classical score distributions.
- Benchmarking can now reach circuit depths where sampling remains plausibly classically intractable.
Where Pith is reading between the lines
- The same separation might appear in circuits with sparser connectivity if the noise model stays local.
- Logarithmic sample complexity suggests the method could remain practical as qubit number grows.
- Combining the classifier with existing error-mitigation techniques could extend its reach to higher noise rates.
- Direct tests on current hardware would supply the next concrete check beyond the paper's numerics.
Load-bearing premise
The analytic expressions derived using replica tricks for all-to-all Brownian circuit ensembles accurately model and predict the separation under depolarizing noise for discrete Haar-random unitary circuits as well.
What would settle it
A numerical simulation or hardware experiment in which the nonlinear cross-entropy score achieved by a noisy quantum circuit falls inside the distribution reachable by state-of-the-art classical spoofers would falsify the claimed separation.
Figures
read the original abstract
Random circuit sampling (RCS) remains one of the most competitive frameworks for demonstrating quantum advantage in near-term noisy intermediate-scale quantum (NISQ) hardware. Unfortunately, absent error-correction, existing benchmarks to characterize these experiments, like linear cross-entropy, have been classically spoofed due to noise. Because of this, there are interesting regimes, like shallow-depth random quantum circuits, where sampling is plausibly classically intractable, but no existing benchmark can distinguish between a noisy quantum computer and an adversarial classical spoofer. In this paper, we demonstrate that the nonlinear cross-entropy provides a sample-efficient benchmark for shallow-depth all-to-all random quantum circuits whose score cleanly separates noisy quantum computers from state-of-the-art classical spoofers, even in the presence of depolarizing noise. Further, we develop a binary classifier based on the notion of heavy output generation that features logarithmic sample complexity at short depth. Our evidence comes from exact analytic expressions for all-to-all Brownian circuit ensembles derived using replica tricks, and numerical simulations that corroborate these results for discrete Haar-random unitary circuits.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript claims that the nonlinear cross-entropy provides a sample-efficient benchmark for shallow-depth all-to-all random quantum circuits whose score cleanly separates noisy quantum computers from state-of-the-art classical spoofers under depolarizing noise; it further introduces a heavy-output-generation binary classifier with logarithmic sample complexity at short depth. Evidence is drawn from exact analytic expressions obtained via replica tricks on all-to-all Brownian circuit ensembles together with numerical simulations that corroborate the results for discrete Haar-random unitary circuits.
Significance. If the claimed separation holds and the analytics transfer reliably, the work would supply a practical tool for characterizing NISQ random-circuit-sampling experiments in the shallow-depth regime where linear cross-entropy benchmarks are known to be classically spoofable, thereby strengthening experimental claims of quantum advantage.
major comments (2)
- [Abstract] Abstract: the central claim that replica-trick analytic expressions derived for continuous all-to-all Brownian ensembles accurately predict both the nonlinear cross-entropy score and the heavy-output classifier performance for discrete Haar-random unitaries under depolarizing noise is load-bearing, yet the manuscript provides no explicit error bounds, convergence analysis, or section detailing the modeling step that justifies the transfer from the continuous to the discrete finite-depth setting.
- [Numerical simulations (referenced in Abstract)] The numerical simulations are stated to corroborate the analytic results for discrete circuits, but without a dedicated section or table reporting quantitative agreement (e.g., deviation in the nonlinear cross-entropy value or classifier accuracy as a function of depth and system size), it is impossible to assess whether the numerics close the modeling gap or merely illustrate qualitative trends.
Simulated Author's Rebuttal
We thank the referee for the careful review and constructive feedback. The two major comments identify gaps in the justification for transferring analytic results from the continuous Brownian ensemble to discrete Haar-random circuits and in the quantitative presentation of numerical corroboration. We address each point below and will incorporate revisions to strengthen the manuscript.
read point-by-point responses
-
Referee: [Abstract] Abstract: the central claim that replica-trick analytic expressions derived for continuous all-to-all Brownian ensembles accurately predict both the nonlinear cross-entropy score and the heavy-output classifier performance for discrete Haar-random unitaries under depolarizing noise is load-bearing, yet the manuscript provides no explicit error bounds, convergence analysis, or section detailing the modeling step that justifies the transfer from the continuous to the discrete finite-depth setting.
Authors: We agree that the manuscript would benefit from an explicit discussion of the modeling assumptions underlying the transfer. The Brownian ensemble is used because it permits exact replica-trick calculations while reproducing the leading-order statistics of Haar-random gates at short depth; the numerics are intended to confirm that the resulting expressions remain predictive for discrete circuits. In the revision we will add a dedicated subsection (likely in Section II) that (i) recalls the replica-trick derivation, (ii) states the regime of validity (small depth relative to system size, large number of gates per layer), and (iii) supplies numerical error bounds obtained by comparing the analytic formulas to exact small-system simulations. Convergence plots versus depth and qubit number will be included. revision: yes
-
Referee: [Numerical simulations (referenced in Abstract)] The numerical simulations are stated to corroborate the analytic results for discrete circuits, but without a dedicated section or table reporting quantitative agreement (e.g., deviation in the nonlinear cross-entropy value or classifier accuracy as a function of depth and system size), it is impossible to assess whether the numerics close the modeling gap or merely illustrate qualitative trends.
Authors: We concur that quantitative metrics are needed. The current figures show visual agreement but do not tabulate deviations. In the revised manuscript we will add an appendix (or new subsection) containing a table that reports, for depths d = 1…10 and qubit numbers n = 4…12, the mean absolute deviation and relative error between the analytic Brownian predictions and the Monte-Carlo estimates for both the nonlinear cross-entropy and the heavy-output classifier accuracy. Statistical uncertainties from finite sampling will also be listed, allowing readers to judge the size of the modeling gap directly. revision: yes
Circularity Check
No significant circularity detected
full rationale
The paper derives exact analytic expressions for all-to-all Brownian circuit ensembles via replica tricks and uses numerical simulations to corroborate applicability to discrete Haar-random unitaries under depolarizing noise. No load-bearing step reduces by construction to a fitted input, self-definition, or self-citation chain; the replica-trick derivation and separate numerical check constitute independent content against external benchmarks.
Axiom & Free-Parameter Ledger
Reference graph
Works this paper leans on
- [1]
-
[2]
F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S...
work page 2019
-
[3]
Q. Zhu, S. Cao, F. Chen, M.-C. Chen, X. Chen, T.-H. Chung, H. Deng, Y. Du, D. Fan, M. Gong, C. Guo, C. Guo, S. Guo, L. Han, L. Hong, H.- L. Huang, Y.-H. Huo, L. Li, N. Li, S. Li, Y. Li, F. Liang, C. Lin, J. Lin, H. Qian, D. Qiao, H. Rong, H. Su, L. Sun, L. Wang, S. Wang, D. Wu, Y. Wu, Y. Xu, K. Yan, W. Yang, Y. Yang, Y. Ye, J. Yin, C. Ying, J. Yu, C. Zha,...
-
[4]
A. Morvan, B. Villalonga, X. Mi, S. Mandr` a, A. Bengtsson, P. V. Klimov, Z. Chen, S. Hong, C. Erickson, I. K. Drozdov, J. Chau, G. Laun, R. Movassagh, A. Asfaw, L. T. A. N. Brand˜ ao, R. Peralta, D. Abanin, R. Acharya, R. Allen, T. I. Andersen, K. Anderson, M. Ansmann, F. Arute, K. Arya, J. Atalaya, J. C. Bardin, A. Bilmes, G. Bortoli, A. Bourassa, J. Bo...
-
[5]
Complexity-Theoretic Foundations of Quantum Supremacy Experiments
S. Aaronson and L. Chen, arXiv preprint arXiv:1612.05903 (2016)
work page internal anchor Pith review Pith/arXiv arXiv 2016
-
[6]
A. Bouland, B. Fefferman, C. Nirkhe, and U. Vazi- rani, Nature Physics15, 159–163 (2018)
work page 2018
-
[7]
Movassagh, Quantum supremacy and random circuits (2020), arXiv:1909.06210 [quant-ph]
R. Movassagh, Quantum supremacy and random circuits (2020), arXiv:1909.06210 [quant-ph]
-
[8]
A. Bouland, B. Fefferman, Z. Landau, and Y. Liu, in2021 IEEE 62nd Annual Symposium on Founda- tions of Computer Science (FOCS)(IEEE, 2022)
work page 2022
-
[9]
A. Bouland, I. Datta, B. Fefferman, and F. Hernandez, Exponential improvements to the average-case hardness of bosonsampling (2025), arXiv:2411.04566 [quant-ph]
-
[10]
S. Aaronson and S. Gunn, On the classical hard- ness of spoofing linear cross-entropy benchmarking (2020), arXiv:1910.12085 [quant-ph]
-
[11]
B. Barak, C.-N. Chou, and X. Gao, in12th In- novations in Theoretical Computer Science Confer- ence (ITCS 2021), Leibniz International Proceed- ings in Informatics (LIPIcs), Vol. 185, edited by J. R. Lee (Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik, Dagstuhl, Germany, 2021) pp. 30:1– 30:20
work page 2021
-
[12]
X. Gao, M. Kalinowski, C.-N. Chou, M. D. Lukin, B. Barak, and S. Choi, PRX Quantum5, 010334 (2024)
work page 2024
-
[13]
J. C. Napp, R. L. La Placa, A. M. Dalzell, F. G. S. L. Brand˜ ao, and A. W. Harrow, Phys. Rev. X 12, 021021 (2022)
work page 2022
- [14]
-
[15]
A. Bene Watts, D. Gosset, Y. Liu, and M. Soleiman- ifar, PRX Quantum6, 010356 (2025)
work page 2025
-
[16]
A. M. Dalzell, N. Hunter-Jones, and F. G. S. L. Brand˜ ao, PRX Quantum3, 10.1103/prxquan- tum.3.010333 (2022)
-
[17]
A. Deshpande, P. Niroula, O. Shtanko, A. V. Gor- shkov, B. Fefferman, and M. J. Gullans, PRX Quan- tum3, 10.1103/prxquantum.3.040329 (2022)
-
[18]
D. Aharonov, X. Gao, Z. Landau, Y. Liu, and U. Vazirani, inProceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC ’23 (ACM, 2023)
work page 2023
-
[19]
N. Lashkari, D. Stanford, M. Hastings, T. Osborne, and P. Hayden, Journal of High Energy Physics 2013, 22 (2013)
work page 2013
-
[20]
G. S. Bentsen, S. Sahu, and B. Swingle, Phys. Rev. B104, 094304 (2021)
work page 2021
-
[21]
S.-K. Jian, G. Bentsen, and B. Swingle, Journal of High Energy Physics2023, 190 (2023). [22]βJis the depth of the Brownian circuit and is a good proxy for the depth of analogous discrete all-to-all circuits
work page 2023
- [22]
-
[23]
Y. Bao, S. Choi, and E. Altman, Phys. Rev. B101, 104301 (2020)
work page 2020
-
[24]
S. Choi, Y. Bao, X.-L. Qi, and E. Altman, Phys. Rev. Lett.125, 030505 (2020)
work page 2020
-
[25]
Y. Li, X. Chen, and M. P. Fisher, Physical Review B100, 134306 (2019)
work page 2019
- [26]
-
[27]
S. Sahu, S.-K. Jian, G. Bentsen, and B. Swingle, Phys. Rev. B106, 224305 (2022)
work page 2022
-
[28]
M. Heinrich, M. Kliesch, and I. Roth, arXiv preprint arXiv:2212.06181 (2022)
-
[29]
F. G. Brand˜ ao, W. Chemissany, N. Hunter-Jones, R. Kueng, and J. Preskill, PRX Quantum2, 030316 (2021)
work page 2021
- [30]
-
[31]
S. F. Edwards and P. W. Anderson, Journal of Physics F: Metal Physics5, 965 (1975)
work page 1975
-
[32]
D. Sherrington and S. Kirkpatrick, Phys. Rev. Lett. 35, 1792 (1975)
work page 1975
-
[33]
P. W. A. D. J. Thouless and R. G. Palmer, The Philosophical Magazine: A Journal of Theoretical Experimental and Applied Physics35, 593 (1977), https://doi.org/10.1080/14786437708235992
-
[34]
J. R. L. de Almeida and D. J. Thouless, Journal of Physics A: Mathematical and General11, 983 (1978)
work page 1978
- [35]
- [36]
-
[37]
M. Mezard, G. Parisi, and M. Virasoro,Spin Glass Theory and Beyond(WORLD SCIENTIFIC, 1986) https://www.worldscientific.com/doi/pdf/10.1142/0271
-
[38]
A. P. Young,Spin Glasses and Ran- dom Fields(WORLD SCIENTIFIC, 1997) https://www.worldscientific.com/doi/pdf/10.1142/3517
-
[39]
A. J. Bray and M. A. Moore, Journal of Physics C: Solid State Physics13, L655 (1980)
work page 1980
- [40]
- [41]
-
[42]
N. Read, S. Sachdev, and J. Ye, Phys. Rev. B52, 384 (1995)
work page 1995
-
[43]
T. K. Kope´ c, Phys. Rev. B52, 9590 (1995)
work page 1995
- [44]
-
[45]
A. Georges, O. Parcollet, and S. Sachdev, Phys. Rev. B63, 134406 (2001). 17
work page 2001
- [46]
-
[47]
A. L. Fitzpatrick, S. Kachru, J. Kaplan, and S. Raghu, Phys. Rev. B89, 165114 (2014)
work page 2014
- [48]
- [49]
-
[50]
R. A. Davison, W. Fu, A. Georges, Y. Gu, K. Jensen, and S. Sachdev, Phys. Rev. B95, 155131 (2017)
work page 2017
-
[51]
Y. Gu, A. Kitaev, S. Sachdev, and G. Tarnopolsky, Journal of High Energy Physics2020, 157 (2020)
work page 2020
-
[52]
D. Chowdhury, A. Georges, O. Parcollet, and S. Sachdev, Rev. Mod. Phys.94, 035004 (2022)
work page 2022
-
[53]
E. Br´ ezin, C. Itzykson, G. Parisi, and J. B. Zu- ber, Communications in Mathematical Physics59, 35 (1978)
work page 1978
-
[54]
E. Witten, The 1/n expansion in atomic and parti- cle physics, inRecent Developments in Gauge The- ories, edited by G. Hooft, C. Itzykson, A. Jaffe, H. Lehmann, P. K. Mitter, I. M. Singer, and R. Stora (Springer US, Boston, MA, 1980) pp. 403– 419
work page 1980
-
[55]
Coleman, 1/n, inAspects of Symmetry: Selected Erice Lectures(Cambridge University Press, 1985) p
S. Coleman, 1/n, inAspects of Symmetry: Selected Erice Lectures(Cambridge University Press, 1985) p. 351–402
work page 1985
-
[56]
G. ’t Hooft, inThe Large N Expansion In Quantum Field Theory And Statistical Physics: From Spin Systems to 2-Dimensional Gravity(World Scientific,
- [57]
-
[58]
Kitaev, inKITP strings seminar and Entangle- ment, Vol
A. Kitaev, inKITP strings seminar and Entangle- ment, Vol. 12 (2015)
work page 2015
- [59]
- [60]
- [61]
-
[62]
M. Berkooz, P. Narayan, M. Rozali, and J. Sim´ on, Journal of High Energy Physics2017, 138 (2017)
work page 2017
-
[63]
W. Fu, D. Gaiotto, J. Maldacena, and S. Sachdev, Phys. Rev. D95, 026009 (2017)
work page 2017
- [64]
-
[65]
S. A. Hartnoll, A. Lucas, and S. Sachdev,Holo- graphic quantum matter(MIT press, 2018)
work page 2018
- [66]
-
[67]
P. Saad, S. H. Shenker, and D. Stanford, A semiclassical ramp in syk and in gravity (2019), arXiv:1806.06840 [hep-th]
work page internal anchor Pith review Pith/arXiv arXiv 2019
-
[68]
Rosenhaus, Journal of Physics A: Mathematical and Theoretical52, 323001 (2019)
V. Rosenhaus, Journal of Physics A: Mathematical and Theoretical52, 323001 (2019)
work page 2019
-
[69]
M. Berkooz, V. Narovlansky, and H. Raj, Journal of High Energy Physics2021, 113 (2021)
work page 2021
-
[70]
Choi, Linear algebra and its applications10, 285 (1975)
M.-D. Choi, Linear algebra and its applications10, 285 (1975)
work page 1975
-
[71]
Jamio lkowski, Reports on mathematical physics 3, 275 (1972)
A. Jamio lkowski, Reports on mathematical physics 3, 275 (1972)
work page 1972
-
[72]
G. Bentsen, B. Fefferman, S. Ghosh, M. J. Gul- lans, and Y. Liu, arXiv preprint arXiv:2411.04169 (2024)
-
[73]
E. Pednault, J. A. Gunnels, G. Nannicini, L. Horesh, and R. Wisnieff, arXiv preprint arXiv:1910.09534 (2019)
-
[74]
G. Q. AI and Collaborators, Nature638, 920 (2025)
work page 2025
-
[75]
Y. Kim, A. Eddins, S. Anand, K. X. Wei, E. Van Den Berg, S. Rosenblatt, H. Nayfeh, Y. Wu, M. Za- letel, K. Temme,et al., Nature618, 500 (2023)
work page 2023
-
[76]
AbuGhanem, The Journal of Supercomputing 81, 687 (2025)
M. AbuGhanem, The Journal of Supercomputing 81, 687 (2025)
work page 2025
-
[77]
D. Bluvstein, S. J. Evered, A. A. Geim, S. H. Li, H. Zhou, T. Manovitz, S. Ebadi, M. Cain, M. Kali- nowski, D. Hangleiter,et al., Nature626, 58 (2024)
work page 2024
-
[78]
H. J. Manetsch, G. Nomura, E. Bataille, X. Lv, K. H. Leung, and M. Endres, Nature647, 60 (2025)
work page 2025
-
[79]
P. Sales Rodriguez, J. M. Robinson, P. N. Jepsen, Z. He, C. Duckering, C. Zhao, K.-H. Wu, J. Campo, K. Bagnall, M. Kwon,et al., Nature645, 620 (2025)
work page 2025
- [80]
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.