Pith. sign in

REVIEW 3 major objections 4 minor 78 references

Generalized Cross-Entropy Benchmarking for Random Circuits with Ergodicity

T0 review · 3 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Random circuit ensembles satisfy an ergodicity condition—bitstring averages concentrate around ensemble averages—and the deviation from it estimates a chip's fidelity, generalizing linear cross-entropy benchmarking.

desk verdict Solid ergodicity theorem and clean global-depolarizing benchmark; the advertised weak-noise recovery of linear XEB rests on an invalid Lévy step and an unmatched weak-correlation assumption. read the letter →

arxiv 2502.09015 v1 pith:FGKPTOUE submitted 2025-02-13 quant-ph

Bin Cheng , Fei Meng , Zhi-Jiong Zhang , Man-Hong Yung This is my paper · ORCID
classification quant-ph MSC 81P6881P4560B20 PACS 03.67.-a03.67.Lx
keywords ergodicityrandomcircuitsamplingcross-entropybenchmarkingunitaryt-designfidelitydepolarizingnoiseconcentrationofmeasurequantumcertification
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper establishes an ergodicity property of random circuit sampling: for a circuit drawn from an ensemble that forms a unitary $2t$-design, the average of any degree-$t$ polynomial with non-negative coefficients over the output bitstrings of a single circuit is close—with probability at least $1-1/\alpha^2$—to the same polynomial averaged over the circuit ensemble, up to a gap of order $\sigma_f/\sqrt{N}$ with $N=2^n$. The paper then turns the size of this gap into a benchmarking signal, defining the deviation of ergodicity and showing that it estimates circuit fidelity under global depolarizing noise and under weakly correlated noise. For the quadratic scheme function $f(p)=N^2p^2$ it recovers linear cross-entropy benchmarking as a special case, and for $f(p)=p\ln p$ it gives a logarithmic variant. The practical point is that the benchmark needs only $T=O(\mathrm{poly}(\log N))$ samples, far fewer than the Hilbert space dimension, making it usable in the supremacy regime.

What carries the argument

The engine is the unitary $2t$-design—a finite set of unitaries that matches the Haar measure through the $2t$-th moment—together with Lemma 1's covariance identity, which shows that the output probabilities at two distinct bitstrings are negatively correlated over the unitary ensemble. This negative covariance is what lets Chebyshev's inequality produce the $1/\alpha^2$ concentration bound, and it is also the reason the argument needs a $2t$-design rather than a $t$-design. For the benchmarking scheme, the operative object is the deviation of ergodicity $DE_f$, estimated from $T$ experimental samples via $\widehat{C}_f=\frac{1}{NT}\sum_i f(P_U(x_i))/P_U(x_i)$, which is unbiased and needs only $T=O(\mathrm{poly}(\log N))$ samples. A second mechanism, Levy's lemma, is invoked to concentrate the noise correlation $C_f(P_U,\chi_U)$ in the weakly correlated noise analysis.

What would settle it

Take a concrete weakly correlated noise model, such as single-qubit depolarizing noise applied after a few gates, and for small $N$ (e.g., $N=8$ or $16$) compute $C_f(P_U,\chi_U)$ exactly for many Haar-random unitaries $U$. If the empirical probability that $|C_f-\mathbb{E}[C_f]|\ge 1/\sqrt{N}$ decays far more slowly than the claimed bound $2\exp[-C(2N+1)N]$, or does not decay at all, then Proposition 2.1's concentration step fails and the fidelity formula $F=1-\widehat{DE}_f$ is unsupported.

Watch

Extended reading notes

Core claim

The paper's central claim is Theorem 1: a unitary $2t$-design is ergodic relative to any polynomial $f(p)=\sum_{i=1}^{t}a_ip^i+b$ with $a_i\ge 0$, meaning that for every $\alpha>0$, the probability that the bitstring average $\frac{1}{N}\sum_x f(P_U(x))$ differs from the ensemble average $\mathbb{E}_U[f(P_U)]$ by at least $\alpha\sigma_f/\sqrt{N}$ is at most $1/\alpha^2$. The proof runs through Chebyshev's inequality and the negative-covariance identity $\mathrm{Cov}(P_U^{q_1}(x),P_U^{q_2}(y))<0$ for distinct bitstrings $x,y$, which makes the variance of the bitstring average smaller than $\sigma_f^2/N$. The paper defines the deviation of ergodicity $DE_f=|\mathbb{E}_U[f(P_U)]-C_f(P_U,Q_U)|$ with $C_f$ the correlation between ideal and experimental output distributions, proves the deviation estimates fidelity for global depolarizing noise, and gives a sufficient condition under which it does so for weakly correlated noise, recovering the linear cross-entropy benchmark for $f(p)=N^2p^2$.

Load-bearing premise

The load-bearing premise is that the correlation between ideal output probabilities and the noise part stays close to its average for every circuit; if it does not, the deviation of ergodicity is not a reliable measure of fidelity under weakly correlated noise, and the paper's argument for that concentration is incomplete.

Editorial extensions

If this is right

  • For a noiseless device the estimator $\widehat{DE}_f$ is $O(\sigma_f/\sqrt{N})$ with high probability, so a statistically significant large deviation directly signals noise.
  • Under global depolarizing noise with fidelity $F$, the deviation satisfies $\widehat{DE}_f=(1-F)(i-1)!(i-1)\pm O(1/\sqrt{T})$ for the polynomial $f(p)=N^ip^i$, giving an explicit way to extract $F$ from samples.
  • Choosing $f(p)=N^2p^2$ reproduces the linear cross-entropy benchmarking estimator $F_{\mathrm{XEB}}=F\pm O(1/\sqrt{T})$ under the paper's weak-correlation condition, so the new framework contains the standard XEB protocol as one instance.
  • The ergodicity result for $f(p)=p\ln p$ provides a logarithmic cross-entropy variant with the same sample-count scaling.
  • Because the estimate requires only $T=O(\mathrm{poly}(\log N))$ samples, the scheme remains practical when the number of qubits is large enough that most bitstrings are never observed twice.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The benchmark's sensitivity is not fixed by the theorem: replacing a single polynomial degree by several degrees $i=2,3,4$ gives independent estimates of the same fidelity, and discrepancies among them would flag correlated noise that the weakly correlated model cannot handle; this is a natural extension the paper does not develop.
  • The positive-coefficient condition in Theorem 1 suggests a sharp boundary for ergodicity: testing functions with mixed signs, such as $f(p)=p-p^2$, could reveal whether the concentration relies specifically on monotone post-processing and might lead to benchmark functions tailored to particular noise channels.
  • Since the deviation of ergodicity is computed from ideal probabilities of sampled bitstrings, it is exposed to the same classical spoofing threats as linear cross-entropy benchmarking; a classical sampler that mimics the ideal distribution's statistics could keep $\widehat{DE}_f$ small without high fidelity, so the scheme's certification power depends on the hardness of such spoofing.
  • The paper's Levy-lemma route to concentrating $C_f(P_U,\chi_U)$ appears to give a trivial bound; if a different argument can close that gap, the weakly correlated noise result would become a theorem, and if not, the scheme's validity in practical regimes rests on empirical noise assumptions.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper introduces a notion of ergodicity for random circuit ensembles: for functions f of the output probabilities, the average of f over output bitstrings of a typical circuit is close to the ensemble average. Theorem 1 proves this for positive-coefficient polynomials of degree t when the circuit ensemble is a unitary 2t-design, via explicit Haar-integral computations showing negative covariances between distinct bitstrings. Theorem 2 extends the result to f(p)=p ln p for Haar-random unitaries. The authors then define a benchmarking quantity, the deviation of ergodicity (DE_f), and analyze it for global depolarizing noise and for a weak-correlation noise model. For the quadratic choice f(p)=N^2 p^2, they claim to recover linear cross-entropy benchmarking (XEB), i.e., that DE_f estimates the circuit fidelity F. They also analyze Google's Sycamore data for several polynomial scheme functions.

Significance. The ergodicity theorems (Theorem 1 and Theorem 2) are a genuine mathematical contribution: they establish a clean concentration baseline for random circuit output statistics, with proofs based on explicit Haar integrals and negative covariance bounds. The global depolarizing noise analysis (Section III.B.a) is a correct and useful sanity check, showing that DE_f is a linear function of fidelity in that model. However, the paper's headline applied claim, the recovery of linear XEB for weakly correlated noise (Proposition 2.1), is not proven and, as stated, is false. Since the abstract and introduction advertise this recovery as a central result, the paper's main benchmarking claim fails. The experimental section inherits this problem because its interpretation of the Sycamore data relies on the weak-noise relation that is not established.

major comments (3)
  1. [Section III.B.b, Eq. (36)] The weak-correlation assumption (32) is stated only for f(p)=N^2 p^2, i.e., E[χ_U f(P_U)] ≈ E[χ_U] E[f(P_U)]. However, Eq. (36) applies the same factorization to the linear function N^2 P_U, requiring E[χ_U P_U] ≈ E[χ_U] E[P_U]. The quadratic assumption does not imply the linear one, so the computation of E[C_f(P_U,χ_U)] = 1 + O(1/(N√N)) is unsupported by the stated hypothesis.
  2. [Section III.B.b, Eq. (39)] The proof states that C_f(P_U,χ_U) is Lipschitz with constant η ≥ N√2 and then invokes Lévy's lemma (Lemma 2, Appendix F). Lévy's lemma requires an upper bound on the Lipschitz constant; a lower bound is useless for concentration. Moreover, inserting η = N√2 and ε = 1/√N into Lemma 2 gives the trivial bound 2 exp[-C(2N+1)/(2N^3)] ≈ 2, not the claimed 2 exp[-C(2N+1)N]. The concentration claim is therefore not derived.
  3. [Section III.B.b, Eqs. (37)-(40)] Even if the mean were correctly computed, the fluctuation of C_f(P_U,χ_U) around its mean need not be O(1/√N). Consider noise where χ_U is a random computational basis state |π(U)⟩⟨π(U)|, with π(U) uniformly random and independent of U. This satisfies E[χ_U(x0)] = 1/N and also satisfies Eq. (32) exactly, because E[χ_U(x0) f(P_U(x0))] = (1/N) E[f(P_U(x0))] = E[χ_U(x0)] E[f(P_U(x0))]. Yet C_f(P_U,χ_U) = N P_U(π(U)), whose variance over U is (N-1)/(N+1) ≈ 1. Thus C_f fluctuates by order 1, not O(1/√N), and Eq. (40) fails. Consequently Proposition 2.1 is false as stated, and the claimed recovery of linear XEB, Eq. (45), does not hold under the stated assumptions.
minor comments (4)
  1. [Fig. 2 caption] The word "ergdicity" should be "ergodicity".
  2. [Section III.D] The sentence "our analysis in Section III B dose not contradict" contains a typo: "dose" should be "does".
  3. [Section I] There are several OCR-style spacing artifacts in the text, such as "o ffer" and "su fficient"; these should be cleaned up.
  4. [Appendix A, Eq. (A9)] The statement that the correction term o(p) can be expressed as O(1) independent of N is imprecise; the limit should be justified more carefully, though this does not affect the main results.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation: the ergodicity theorem and depolarizing-noise fidelity estimate are self-contained, and the quadratic XEB recovery is an acknowledged special case rather than a hidden circular prediction.

full rationale

The paper's main derivation chain is self-contained. Theorem 1 is proved from Haar moment integrals (Lemma 1) plus Chebyshev's inequality, and the relaxation to unitary 2t-designs is exactly the defining moment-matching property of a design, not a circular import. The global depolarizing noise fidelity estimate follows algebraically from Theorem 1 and Eq. (19), with no fitted parameter renamed as a prediction. The quadratic case is definitionally related to XEB: Eq. (44) states that for f(p)=N^2p^2 the estimator eC_f equals F_XEB+1, and the paper explicitly says it 'recovers Google's result'; this is an acknowledged special case and reframing, not a claim that a new quantity is predicted from scratch. The weak-noise Proposition 2.1 has a genuine mathematical gap: the stated Lipschitz bound is a lower bound, and Eq. (36) applies the weak-correlation assumption to a linear function while Eq. (32) states it for f=N^2p^2; however, this is a correctness or proof-validity concern, not circularity, because the conclusion F=1-DE is not equivalent to the assumptions by construction and no parameter is fitted to the target fidelity. There are no load-bearing self-citations or imported uniqueness theorems; the only author self-citation is background. Therefore the circularity score is 0.

Assumptions & free parameters 0 free parameters · 7 assumptions · 0 invented entities

The central claim rests mainly on the weak correlation assumption (Eq 32) and the unproven concentration of C_f(P_U,χ_U); the ergodicity theorems themselves use standard Haar integration and unitary design definitions.

assumptions (7)
  • standard math Unitary t-designs match Haar moments up to order t (Definition 1).
    Used in Theorem 1 to replace Haar expectations with design expectations for polynomials of degree t and covariances of degree 2t.
  • standard math The Haar integral formula for moments of output probabilities, Γ(N)ΠΓ(q_i+1)/Γ(Σq_i+N), from Ref [71].
    Used in Lemma 1 / Proposition 2.2 to establish negative covariance.
  • domain assumption Porter-Thomas (exponential) approximation for the distribution of output probabilities, valid up to e^{-Ω(N)} corrections.
    Used to compute E_U[f(P_U)] and σ_f in Eq (19) and Appendix B.
  • domain assumption Weak correlation assumption Eq (32): E_U[χ_U f(P_U)] = E_U[χ_U] E_U[f(P_U)] + O(1/(N√N)), and E_U[χ_U] = 1/N.
    Central premise of Proposition 2.1; characterizes noise for which DE estimates fidelity.
  • ad hoc to paper Concentration of C_f(P_U,χ_U) around its mean via Levy's lemma (claimed in Prop 2.1 proof).
    The asserted Lipschitz bound (η >= N√2) and the resulting probability bound are inconsistent; this concentration is not actually established.
  • domain assumption Local unital noise is scrambled into global depolarizing noise by deep random circuits (Ref [57]).
    Used in Section III B c to justify the depolarizing model for real hardware.
  • standard math Replica trick ln p = lim_{i→0} (p^i - 1)/i.
    Used in Appendix E to prove ergodicity for p ln p.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Generalized Cross-Entropy Benchmarking for Random Circuits with Ergodicity." pith.science (2026). https://pith.science/paper/FGKPTOUE

@misc{pith2026250209015,
  author       = {Pith},
  title        = {Pith review of: Generalized Cross-Entropy Benchmarking for Random Circuits with Ergodicity},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FGKPTOUE}},
  note         = {Machine review of arXiv:2502.09015}
}
abstract

Cross-entropy benchmarking is a central technique used to certify a quantum chip in recent experiments. To better understand its mathematical foundation and develop new benchmarking schemes, we introduce the concept of ergodicity to random circuit sampling and find that the Haar random quantum circuit satisfies an ergodicity condition -- the average of certain types of post-processing function over the output bit strings is close to the average over the unitary ensemble. For noiseless random circuits, we prove that the ergodicity holds for polynomials of degree $t$ with positive coefficients and when the random circuits form a unitary $2t$-design. For strong enough noise, the ergodicity condition is violated. This suggests that ergodicity is a property that can be exploited to certify a quantum chip. We formulate the deviation of ergodicity as a measure for quantum chip benchmarking and show that it can be used to estimate the circuit fidelity for global depolarizing noise and weakly correlated noise. For a quadratic post-processing function, our framework recovers Google's result on estimating the circuit fidelity via linear cross-entropy benchmarking (XEB), and we give a sufficient condition on the noise model characterizing when such estimation is valid. Our results establish an interesting connection between ergodicity and noise in random circuits and provide new insights into designing quantum benchmarking schemes.

Figures

Figures reproduced from arXiv: 2502.09015 by the authors.

Figure 1
Figure 1. FIG. 1. Basic procedure of our quantum chip benchmarking scheme. [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. FIG. 2. Numerical evidence of the ergdicity condition relative to [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. FIG. 3. The scaling of [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: FIG. 4 [PITH_FULL_IMAGE:figures/full_fig_p007_4.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

78 extracted references · 57 canonical work pages

  1. [1]

    Eisert, D

    J. Eisert, D. Hangleiter, N. Walk, I. Roth, D. Markham, R. Parekh, U. Chabaud, and E. Kashefi, Quantum certification and benchmarking, Nature Reviews Physics 2, 382 (2020)

    work page 2020

  2. [2]

    Therefore, typically (with high probability) we have C f (PU,χ U) = EU[C f (PU,χ U)]± O 1√ N ! = 1 + O 1√ N ! , (40) for any U

    Define δ = C f (PU,χ U)− EU[C f (PU,χ U)] (38) and by Levy’s lemma (see Appendix F), we have Pr " δ≥ 1√ N # ≤ 2 exp[−C(2N + 1)N], (39) where C is some constant. Therefore, typically (with high probability) we have C f (PU,χ U) = EU[C f (PU,χ U)]± O 1√ N ! = 1 + O 1√ N ! , (40) for any U. This implies that, typically, we have eC f (PU, QU) = (1 + F)± O 1√ ...

    work page

  3. [3]

    Kliesch and I

    M. Kliesch and I. Roth, Theory of quantum system certification, PRX quantum 2, 010201 (2021)

    work page 2021

  4. [4]

    Resch and U

    S. Resch and U. R. Karpuzcu, Benchmarking quantum comput- ers and the impact of quantum noise, ACM Computing Surveys (CSUR) 54, 1 (2021)

    work page 2021

  5. [5]

    Wang, Y .-H

    Y . Wang, Y .-H. Lu, J. Gao, Y .-J. Chang, R.-J. Ren, Z.-Q. Jiao, Z.-Y . Zhang, and X.-M. Jin, Topologically protected polariza- tion quantum entanglement on a photonic chip, Chip 1, 100003 (2022)

    work page 2022

  6. [6]

    Preskill, Quantum Computing in the NISQ era and beyond, Quantum 2, 79 (2018), arXiv:1801.00862

    J. Preskill, Quantum Computing in the NISQ era and beyond, Quantum 2, 79 (2018), arXiv:1801.00862

    arXiv 2018

  7. [7]

    Preskill, Quantum computing and the entanglement frontier, arXiv:1203.5813 (2012)

    J. Preskill, Quantum computing and the entanglement frontier, arXiv:1203.5813 (2012)

    arXiv 2012

  8. [8]

    A. W. Harrow and A. Montanaro, Quantum computational supremacy, Nature 549, 203 (2017)

    2017

Show all 78 references
  1. [9]

    Yung, Quantum supremacy: some fundamental concepts, Natl

    M.-H. Yung, Quantum supremacy: some fundamental concepts, Natl. Sci. Rev. 6, 22 (2019)

    2019

  2. [10]

    Aaronson and A

    S. Aaronson and A. Arkhipov, The Computational Complexity of Linear Optics, Theory Comput. 9, 143 (2013)

    2013

  3. [11]

    A. P. Lund, A. Laing, S. Rahimi-Keshari, T. Rudolph, J. L. O’Brien, and T. C. Ralph, Boson sampling from a Gaussian state, Physical Review Letters 113, 1 (2014), arXiv:1305.4346

    2014 arXiv

  4. [12]

    C. S. Hamilton, R. Kruse, L. Sansoni, S. Barkhofen, C. Silber- horn, and I. Jex, Gaussian Boson Sampling, Physical Review Letters 119, 1 (2017), arXiv:1612.01199

    2017 arXiv

  5. [13]

    D. J. Brod, E. F. Galv ˜ao, A. Crespi, R. Osellame, N. Spagnolo, and F. Sciarrino, Photonic implementation of boson sampling: a review, Advanced Photonics1, 034001 (2019)

    2019

  6. [14]

    Gao, X.-W

    J. Gao, X.-W. Wang, W.-H. Zhou, Z.-Q. Jiao, R.-J. Ren, Y .- X. Fu, L.-F. Qiao, X.-Y . Xu, C.-N. Zhang, X.-L. Pang, et al., Quantum advantage with membosonsampling, Chip 1, 100007 (2022)

    2022

  7. [15]

    M. J. Bremner, R. Jozsa, and D. J. Shepherd, Classical simula- tion of commuting quantum computations implies collapse of the polynomial hierarchy, Proc. R. Soc. A 467, 459 (2011)

    2011

  8. [16]

    M. J. Bremner, A. Montanaro, and D. J. Shepherd, Average- case complexity versus approximate simulation of commuting quantum computations, Phys. Rev. Lett. 117, 080501 (2016)

    2016

  9. [17]

    Boixo, S

    S. Boixo, S. V . Isakov, V . N. Smelyanskiy, R. Babbush, N. Ding, Z. Jiang, M. J. Bremner, J. M. Martinis, and H. Neven, Char- acterizing quantum supremacy in near-term devices, Nat. Phys. 14, 595 (2018), arXiv:1608.00263

    2018 arXiv

  10. [18]

    Arute, K

    F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. Brandao, D. A. Buell, B. Burkett, Y . Chen, Z. Chen, B. Chiaro, R. Collins, W. Court- ney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gid- ney, M. Giustina, R. Gra ff, K. Guerin,...

    2019 arXiv

  11. [19]

    Wu, W.-S

    Y . Wu, W.-S. Bao, 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...

    2021

  12. [20]

    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. ...

    2021

  13. [21]

    DeCross, R

    M. DeCross, R. Haghshenas, M. Liu, E. Rinaldi, J. Gray, Y . Alexeev, C. H. Baldwin, J. P. Bartolotta, M. Bohn, E. Chertkov, J. Cline, J. Colina, D. DelVento, J. M. Dreil- ing, C. Foltz, J. P. Gaebler, T. M. Gatterman, C. N. Gilbreth, J. Giles, D. Gresh, A. Hall, A. Hankin, A. ...

    2024 arXiv

  14. [22]

    Aaronson and L

    S. Aaronson and L. Chen, Complexity-theoretic founda- tions of quantum supremacy experiments, in Leibniz Inter- national Proceedings in Informatics, LIPIcs , V ol. 79 (2017) arXiv:1612.05903

    2017 arXiv

  15. [23]

    R. L. Mann and M. J. Bremner, On the Complexity of Ran- dom Quantum Computations and the Jones Polynomial (2017), arXiv: 1711.00686

    2017 arXiv

  16. [24]

    Hangleiter, J

    D. Hangleiter, J. Bermejo-Vega, M. Schwarz, and J. Eisert, Anticoncentration theorems for schemes showing a quantum speedup (2018), arXiv: 1706.03786

    2018 arXiv

  17. [25]

    Harrow and S

    A. Harrow and S. Mehraban, Approximate unitary t-designs 10 by short random quantum circuits using nearest-neighbor and long-range gates (2018), arXiv:1809.06957

    2018 arXiv

  18. [26]

    Bouland, B

    A. Bouland, B. Fe fferman, C. Nirkhe, and U. Vazirani, On the complexity and verification of quantum random circuit sam- pling, Nat. Phys. 15, 159 (2019), arXiv:1803.04402

    2019 arXiv

  19. [27]

    Movassagh, Cayley path and quantum computational supremacy: A proof of average-case #P-hardness of Random Circuit Sampling with quantified robustness (2019), arXiv: 1909.06210

    R. Movassagh, Cayley path and quantum computational supremacy: A proof of average-case #P-hardness of Random Circuit Sampling with quantified robustness (2019), arXiv: 1909.06210

    2019 arXiv

  20. [28]

    A. M. Dalzell, N. Hunter-Jones, and F. G. S. L. Brand ˜ao, Random quantum circuits anti-concentrate in log depth, arXiv:2011.12277 [cond-mat, physics:quant-ph] (2020), arXiv: 2011.12277

    2020 arXiv

  21. [29]

    Morimae, Y

    T. Morimae, Y . Takeuchi, and S. Tani, Sampling of globally depolarized random quantum circuit, arXiv:1911.02220 [quant- ph] (2019), arXiv: 1911.02220

    2019 arXiv

  22. [30]

    Rinott, T

    Y . Rinott, T. Shoham, and G. Kalai, Statistical As- pects of the Quantum Supremacy Demonstration (2020), arXiv:2008.05177

    2020 arXiv

  23. [31]

    Jozsa, Fidelity for mixed quantum states, Journal of Modern Optics 41, 2315 (1994), https://doi.org/10.1080/09500349414552171

    R. Jozsa, Fidelity for mixed quantum states, Journal of Modern Optics 41, 2315 (1994), https://doi.org/10.1080/09500349414552171

    1994 doi

  24. [32]

    Knill, D

    E. Knill, D. Leibfried, R. Reichle, J. Britton, R. B. Blakestad, J. D. Jost, C. Langer, R. Ozeri, S. Seidelin, and D. J. Wineland, Randomized benchmarking of quantum gates, Physical Review A - Atomic, Molecular, and Optical Physics 77, 10.1103/Phys- RevA.77.012307 (2008), arXi...

    2008 arXiv

  25. [33]

    J. J. Wallman and S. T. Flammia, Randomized benchmarking with confidence, New Journal of Physics 16, 103032 (2014)

    2014

  26. [34]

    Magesan, J

    E. Magesan, J. M. Gambetta, and J. Emerson, Scalable and ro- bust randomized benchmarking of quantum processes, Physical review letters 106, 180504 (2011)

    2011

  27. [35]

    Helsen, I

    J. Helsen, I. Roth, E. Onorati, A. H. Werner, and J. Eisert, Gen- eral framework for randomized benchmarking, PRX Quantum 3, 020357 (2022)

    2022

  28. [36]

    J. F. Poyatos, J. I. Cirac, and P. Zoller, Complete characteriza- tion of a quantum process: The two-bit quantum gate, Physical Review Letters 78, 390 (1997), arXiv:9611013 [quant-ph]

    1997

  29. [37]

    Torlai, C

    G. Torlai, C. J. Wood, A. Acharya, G. Carleo, J. Carrasquilla, and L. Aolita, Quantum process tomography with unsupervised learning and tensor networks, Nature Communications14, 2858 (2023)

    2023

  30. [38]

    G. A. White, F. A. Pollock, L. C. Hollenberg, K. Modi, and C. D. Hill, Non-markovian quantum process tomography, PRX Quantum 3, 020344 (2022)

    2022

  31. [39]

    Mohseni, A

    M. Mohseni, A. T. Rezakhani, and D. A. Lidar, Quantum- process tomography: Resource analysis of di fferent strategies, Physical Review A—Atomic, Molecular, and Optical Physics 77, 032322 (2008)

    2008

  32. [40]

    S. T. Flammia and Y .-K. Liu, Direct fidelity estimation from few pauli measurements, Physical review letters 106, 230501 (2011)

    2011

  33. [41]

    D. M. Reich, G. Gualdi, and C. P. Koch, Optimal strategies for estimating the average fidelity of quantum gates, Physical Re- view Letters 111, 200401 (2013)

    2013

  34. [42]

    Gluza, M

    M. Gluza, M. Kliesch, J. Eisert, and L. Aolita, Fidelity wit- nesses for fermionic quantum simulations, Physical review let- ters 120, 190501 (2018)

    2018

  35. [43]

    Aolita, C

    L. Aolita, C. Gogolin, M. Kliesch, and J. Eisert, Reliable quantum certification for photonic quantum technologies, arXiv preprint arXiv:1407.4817 (2014)

    2014 arXiv

  36. [44]

    Jurcevic, B

    P. Jurcevic, B. P. Lanyon, P. Hauke, C. Hempel, P. Zoller, R. Blatt, and C. F. Roos, Quasiparticle engineering and entan- glement propagation in a quantum many-body system, Nature 511, 202 (2014)

    2014

  37. [45]

    K. M. Audenaert and M. B. Plenio, When are correlations quan- tum?—verification and quantification of entanglement by sim- ple measurements, New Journal of Physics 8, 266 (2006)

    2006

  38. [46]

    Courme, P

    B. Courme, P. Cameron, D. Faccio, S. Gigan, and H. Defienne, Manipulation and certification of high-dimensional entangle- ment through a scattering medium, PRX Quantum 4, 010308 (2023)

    2023

  39. [47]

    Trotzky, Y .-A

    S. Trotzky, Y .-A. Chen, A. Flesch, I. P. McCulloch, U. Schollw ¨ock, J. Eisert, and I. Bloch, Probing the relaxation towards equilibrium in an isolated strongly correlated one- dimensional bose gas, Nature physics 8, 325 (2012)

    2012

  40. [48]

    Trotzky, L

    S. Trotzky, L. Pollet, F. Gerbier, U. Schnorrberger, I. Bloch, N. Prokof’Ev, B. Svistunov, and M. Troyer, Suppression of the critical temperature for superfluidity near the mott transition, Nature Physics 6, 998 (2010)

    2010

  41. [49]

    C. Oh, L. Jiang, and B. Fefferman, Spoofing cross-entropy mea- sure in boson sampling, Physical Review Letters 131, 010401 (2023)

    2023

  42. [50]

    X. Gao, M. Kalinowski, C.-N. Chou, M. D. Lukin, B. Barak, and S. Choi, Limitations of linear cross-entropy as a measure for quantum advantage, PRX Quantum 5, 010334 (2024)

    2024

  43. [51]

    Suzuki and A

    K. Suzuki and A. Kawachi, Experimental analysis of a classical algorithm spoofing linear cross-entropy benchmarking, IEICE Technical Report; IEICE Tech. Rep.121, 46 (2021)

    2021

  44. [52]

    Peters, The ergodicity problem in economics, Nature Physics 15, 1216 (2019)

    O. Peters, The ergodicity problem in economics, Nature Physics 15, 1216 (2019)

    2019

  45. [53]

    G. D. Birkho ff, Proof of the ergodic theorem, Proceedings of the National Academy of Sciences 17, 656 (1931)

    1931

  46. [54]

    J. v. Neumann, Proof of the quasi-ergodic hypothesis, Proceed- ings of the National Academy of Sciences 18, 70 (1932)

    1932

  47. [55]

    C. C. Moore, Ergodic theorem, ergodic theory, and statistical mechanics, Proceedings of the National Academy of Sciences 112, 1907 (2015)

    2015

  48. [56]

    J. W. Gibbs, Elementary principles in statistical mechanics: de- veloped with especial reference to the rational foundations of thermodynamics (C. Scribner’s sons, 1902)

    1902

  49. [57]

    Y . Liu, M. Otten, R. Bassirianjahromi, L. Jiang, and B. Fe ffer- man, Benchmarking near-term quantum computers via random circuit sampling, arXiv:2105.05232 (2021), arXiv:2105.05232

    2021 arXiv

  50. [58]

    A. M. Dalzell, N. Hunter-Jones, and F. G. S. L. Brand ˜ao, Random quantum circuits transform local noise into global white noise, arXiv:2111.14907 [quant-ph] (2021), arXiv: 2111.14907

    2021 arXiv

  51. [59]

    Deshpande, B

    A. Deshpande, B. Fe fferman, A. V . Gorshkov, M. J. Gullans, P. Niroula, and O. Shtanko, Tight bounds on the convergence of noisy random circuits to uniform, arXiv:2112.00716 [cond-mat, physics:quant-ph] (2021), arXiv: 2112.00716

    2021 arXiv

  52. [60]

    X. Gao, M. Kalinowski, C.-N. Chou, M. D. Lukin, B. Barak, and S. Choi, Limitations of Linear Cross-Entropy as a Mea- sure for Quantum Advantage, PRX Quantum5, 010334 (2024), arXiv: 2112.01657

    2024 arXiv

  53. [61]

    Dankert, R

    C. Dankert, R. Cleve, J. Emerson, and E. Livine, Exact and approximate unitary 2-designs and their application to fidelity estimation, Phys. Rev. A 80, 012304 (2009)

    2009

  54. [62]

    Gross, K

    D. Gross, K. Audenaert, and J. Eisert, Evenly distributed uni- taries: on the structure of unitary designs, Journal of Mathemat- ical Physics 48, 052104 (2007), arXiv:quant-ph/0611002

    2007 arXiv

  55. [63]

    Aaronson and S

    S. Aaronson and S. Gunn, On the Classical Hardness of Spoofing Linear Cross-Entropy Benchmarking (2019), arXiv: 1910.12085

    2019 arXiv

  56. [64]

    M. P. M ¨uller, D. Gross, and J. Eisert, Concentration of measure for quantum states with a fixed expectation value, Communica- tions in Mathematical Physics 303, 785 (2011). 11

    2011

  57. [65]

    J. R. McClean, S. Boixo, V . N. Smelyanskiy, R. Babbush, and H. Neven, Barren plateaus in quantum neural network training landscapes, Nature communications 9, 4812 (2018)

    2018

  58. [66]

    Ledoux, The concentration of measure phenomenon, nachdr

    M. Ledoux, The concentration of measure phenomenon, nachdr. ed., Mathematical surveys and monographs No. 89 (American Mathematical Society, Providence, RI, 2005)

    2005

  59. [67]

    V . D. Milman and G. Schechtman, Asymptotic theory of finite dimensional normed spaces: Isoperimetric inequalities in rie- mannian manifolds , V ol. 1200 (Springer Science & Business Media, 1986)

    1986

  60. [68]

    Ledoux, The concentration of measure phenomenon , 89 (American Mathematical Soc., 2001)

    M. Ledoux, The concentration of measure phenomenon , 89 (American Mathematical Soc., 2001)

    2001

  61. [69]

    Collins and P

    B. Collins and P. ´Sniady, Integration with Respect to the Haar Measure on Unitary, Orthogonal and Symplectic Group, Com- mun. Math. Phys. 264, 773 (2006)

    2006

  62. [70]

    Ozols, How to generate a random unitary matrix, unpub- lished essay on http://home

    M. Ozols, How to generate a random unitary matrix, unpub- lished essay on http://home. lu. lv/sd20008 (2009)

    2009

  63. [71]

    R. W. Bailey, Distributional identities of beta and chi-squared variates: A geometrical interpretation, The American Statisti- cian 46, 117 (1992)

    1992

  64. [72]

    Puchała and J

    Z. Puchała and J. A. Miszczak, Symbolic integration with re- spect to the haar measure on the unitary group, arXiv preprint arXiv:1109.4244 (2011)

    2011 arXiv

  65. [73]

    Hayden, D

    P. Hayden, D. W. Leung, and A. Winter, Aspects of generic entanglement, Communications in mathematical physics 265, 95 (2006)

    2006

  66. [74]

    Z. Hu, Z. Wang, B. Wu, et al., Generalized wigner–von neu- mann entropy and its typicality, Physical Review E 99, 052117 (2019)

    2019

  67. [75]

    O. C. Dahlsten, C. Lupo, S. Mancini, and A. Serafini, Entangle- ment typicality, Journal of Physics A: Mathematical and Theo- retical 47, 363001 (2014). Appendix A: Output probabilities of Haar-distributed unitaries Let p = PU(x0) be the output probability of x0, where U is sa...

    2014

  68. [76]

    To begin with, it is well established that a Haar random unitary can be decomposed into the components U = CR [69]

    Beta distribution We will assume in the following that the quantum circuit U is Haar random. To begin with, it is well established that a Haar random unitary can be decomposed into the components U = CR [69]. Here, C is sampled from the Ginibre ensemble with C jk := a jk +ib j...

  69. [77]

    First, suppose we have k independent standard normal random variablesc1,··· , ck, i.e., ci∼ N(0, 1)

    (A2) We would like to show that PU( j), as a random variable over all choices of U, obeys the Beta distribution. First, suppose we have k independent standard normal random variablesc1,··· , ck, i.e., ci∼ N(0, 1). It is well-known that the sum of squares ofci, obeys the chi-sq...

  70. [78]

    Porter-Thomas properties Porter-Thomas distribution of probability PU( j) for having outcome| j⟩ is given by Pr(p) = Ne−N p. (A5) Consider the expression of Beta distribution under the limit of N→∞ : lim N→∞ (N− 1)(1− p)N−2 = lim N→∞ (N− 1)e(N−2) ln(1−p) (A6) = lim N→∞ NeN ln(...

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.