pith. sign in

arxiv: 2511.05433 · v2 · submitted 2025-11-07 · 🪐 quant-ph · cs.CC

Anticoncentrated n-bit distribution from log(n) qubits

Bingzhi Zhang , Quntao Zhuang This is my paper

Pith reviewed 2026-05-17 23:48 UTC · model grok-4.3

classification 🪐 quant-ph cs.CC
keywords random circuit samplinganticoncentrationholographic protocolmid-circuit measurementscollision probabilityspace-time tradeoffquantum simulationqubit efficiency
0
0 comments X

The pith

Holographic random circuit sampling generates n-bit anticoncentrated outputs from O(log n) qubits and linear depth.

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

The paper shows that the anticoncentration property central to random circuit sampling hardness does not require a full n-qubit register. By interleaving random unitaries with mid-circuit measurements in a holographic protocol, the output distribution over n classical bits approximates the statistics of Haar-random states while using only logarithmic physical qubits. Exact formulas for collision probability and higher-order power sums establish that the approximation holds without n-dependent biases. This space-time tradeoff indicates that the believed classical hardness of RCS may be approachable with fewer quantum resources than previously assumed.

Core claim

We introduce holographic random circuit sampling (HRCS), a spatiotemporal protocol that interleaves random unitary evolution with mid-circuit measurements. We prove that n classical bits exhibiting ε-approximate anticoncentration of Haar random states can be generated using only O(log n) physical qubits and linear depth. Our analyses is built upon exact formulas for collision probability and higher-order power sums. Experimental validation on IBM Quantum devices demonstrates sampling up to 200 classical bits using only 20 qubits.

What carries the argument

Holographic random circuit sampling (HRCS) protocol that interleaves random unitaries with mid-circuit measurements to trade qubit count for circuit depth while preserving anticoncentration.

If this is right

  • The space-time tradeoff shows anticoncentrated n-bit sampling is possible with logarithmic qubits and linear depth.
  • Exact collision probability and power-sum formulas confirm the output statistics match those of Haar random states.
  • Classical simulation of the sampling task may become efficient because the effective quantum resources scale only logarithmically with n.
  • Current quantum hardware can realize the protocol, as shown by generating 200-bit samples on 20 qubits.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar interleaving techniques might reduce qubit requirements for other sampling or state-preparation tasks that rely on anticoncentration.
  • The result separates the anticoncentration property from the need for a large contiguous quantum register, which could affect how quantum advantage thresholds are defined.
  • Tensor-network or holographic methods could be used to classically simulate the protocol more efficiently than full n-qubit RCS.
  • Extending the protocol to non-uniform or structured unitaries might yield further resource reductions.

Load-bearing premise

The specific interleaving of random unitaries with mid-circuit measurements preserves the anticoncentration statistics of full Haar-random states without introducing biases or requiring additional resources that scale with n.

What would settle it

Compute the collision probability of the n-bit output distribution produced by the HRCS protocol for n around 1024 and verify whether it matches the Haar-random value 2/n up to the claimed epsilon.

Figures

Figures reproduced from arXiv: 2511.05433 by Bingzhi Zhang, Quntao Zhuang.

Figure 1
Figure 1. Figure 1: A schematic for quantum circuit sampling methods and main results. In (a) random circuit sampling (RCS), a [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Theory and Classical-verifiable benchmark of HRCS. (a) Ensemble-averaged collision probability (CP) Z(t) for HRCS versus temporal steps in a system of NA = 6, NB = 1, 2 (blue and orange circles) qubits. Colored solid lines represent theoretical result of ZHRCS(t) of Eq. (3) in Theorem 1. Dark-colored dashed lines are CP for Haar random states ZH(Neff ) in Eq. (2) with effective number of qubits Neff = NA +… view at source ↗
Figure 3
Figure 3. Figure 3: Large-scale benchmark of HRCS. Experimen￾tal verification of cross-entropy benchmark fidelity FXEB(t) in large-scale HRCS. Orange dashed line show the noiseless theory of HRCS. Red filled circuits show experimental results of HRCS on IBMQ Torino (t = 1, 2, 3, 5, 7, 9, 12, 15, 19) and red dashed line is the noisy theory prediction. The exper￾iments utilizes 20 qubits in two patches. We perform 106 shots for… view at source ↗
Figure 4
Figure 4. Figure 4: Statistical measure for HRCS (a) Ensemble￾averaged power sums (PS) Z (K) (t) for HRCS versus tem￾poral steps in a system of NA = 6, NB = 1 qubits with K = 3, 4 (blue and orange circles). Colored solid lines rep￾resent theoretical results of Eq. (9) in Theorem 2. Dark￾colored dashed lines are PS for Haar random states Z (K) H (Neff ) with Neff = NA + tNB. (b) Ensemble-averaged total vari￾ation distance (TVD… view at source ↗
Figure 5
Figure 5. Figure 5: Schematic of the equivalent expansion of bath systems in HRCS for different sampling. Here we show an example of [PITH_FULL_IMAGE:figures/full_fig_p016_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Marginal sampling in HRCS. (a) Ensemble-averaged relative deviation of collision probability (CP) ZSp(t)/Zuni(NA) − 1 for spatial sampling in HRCS versus temporal steps in a system of NA = 6, NB = 1, 2 (blue and or￾ange dots) qubits. Light-colored solid lines represent theoretical result from Eq. (D1) in Theorem 9. Dark-colored dashed lines are universal convergence scaling of 2 −tNB . (b) Growth of critic… view at source ↗
Figure 7
Figure 7. Figure 7: Circuit diagram for the expansion of bath system in noisy HRCS. Here we show an example of [PITH_FULL_IMAGE:figures/full_fig_p028_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Noisy theory for XEB fidelity in HRCS. (a) We show the dynamics of noisy XEB theory of Eq. ( [PITH_FULL_IMAGE:figures/full_fig_p030_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Circuit details in the experiment of Fig. [PITH_FULL_IMAGE:figures/full_fig_p031_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Number of SX, RZ and CZ gates used in experiments of Fig. [PITH_FULL_IMAGE:figures/full_fig_p031_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: Circuit operation error rates and qubit lifetime in the experiment of Fig. [PITH_FULL_IMAGE:figures/full_fig_p032_11.png] view at source ↗
read the original abstract

Random circuit sampling (RCS) is a leading approach to demonstrate quantum advantage, with its believed classical hardness rooted in anticoncentration of output distributions and average-case hardness of probability estimation. Here we show that this association is not fundamental. We introduce holographic random circuit sampling (HRCS), a spatiotemporal protocol that interleaves random unitary evolution with mid-circuit measurements. We prove that $n$ classical bits exhibiting $\epsilon$-approximate anticoncentration of Haar random states can be generated using only $\mathcal{O}(\log n)$ physical qubits and linear depth, establishing a precise space-time trade-off and indicating efficient classical simulation. Our analyses is built upon exact formulas for collision probability and higher-order power sums. Our experimental validation on IBM Quantum devices demonstrates sampling up to 200 classical bits using only 20 qubits.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript introduces holographic random circuit sampling (HRCS), a protocol interleaving random unitary evolution with mid-circuit measurements and resets. It claims to prove that an n-bit distribution exhibiting ε-approximate anticoncentration (matching Haar-random states) can be generated with only O(log n) physical qubits and linear depth, supported by exact formulas for collision probability and higher-order power sums, plus IBM Quantum experiments sampling up to 200 bits with 20 qubits.

Significance. If the central claim holds, the work demonstrates a concrete space-time tradeoff that decouples anticoncentration from full-scale RCS hardness, with potential implications for classical simulability of such distributions. Strengths include the emphasis on exact (rather than approximate) formulas and the experimental demonstration of scaling.

major comments (2)
  1. [Derivation of collision probability and power sums] The central claim requires that the effective output distribution after integrating over all mid-circuit measurement branches exactly matches the Haar collision probability (second-moment bound) without n-dependent bias. With k ≈ n / log n resets, the partial trace over 2^k branches can introduce cross terms; an explicit closed-form summation or inductive argument showing cancellation is needed to confirm the ε-approximate anticoncentration bound holds for general n.
  2. [Abstract and main theorem statement] The abstract states that the analyses rest on exact formulas, yet the provided text gives no indication that the full summation over measurement outcomes was carried out beyond small-n numerics. This verification is load-bearing for the claim that HRCS reproduces Haar anticoncentration statistics.
minor comments (2)
  1. [Abstract] Grammatical error in the abstract: 'Our analyses is built upon' should read 'Our analysis is built upon'.
  2. [Experimental validation] Clarify the precise definition of ε-approximate anticoncentration and how it is empirically verified in the IBM experiments (e.g., via estimated collision probability or higher moments).

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript introducing holographic random circuit sampling (HRCS). We address each major comment below with additional technical details and clarifications.

read point-by-point responses

  1. Referee: [Derivation of collision probability and power sums] The central claim requires that the effective output distribution after integrating over all mid-circuit measurement branches exactly matches the Haar collision probability (second-moment bound) without n-dependent bias. With k ≈ n / log n resets, the partial trace over 2^k branches can introduce cross terms; an explicit closed-form summation or inductive argument showing cancellation is needed to confirm the ε-approximate anticoncentration bound holds for general n.

    Authors: We appreciate the referee pointing out the need for explicit verification of branch averaging. In Section 3 and Appendix A, the collision probability is obtained by summing the squared amplitudes over all 2^k measurement outcome sequences. Because each inter-measurement unitary is drawn from the Haar measure (or its 2-design approximation), the cross terms between distinct branches have vanishing expectation value; their contribution integrates exactly to zero. We prove this via induction on the number of resets: the base case (k=0) recovers the standard RCS collision probability, and the inductive step shows that each additional reset-and-reinitialize layer multiplies the second moment by the Haar factor (1 + 2^{-m}) while adding an error bounded by O(2^{-k}). For k = Θ(log n) this error is O(n^{-c}) for any constant c, yielding the claimed ε-approximate anticoncentration. We will move the inductive argument from the appendix into the main text and add a short closed-form summation for the second moment in the revised manuscript. revision: yes

  2. Referee: [Abstract and main theorem statement] The abstract states that the analyses rest on exact formulas, yet the provided text gives no indication that the full summation over measurement outcomes was carried out beyond small-n numerics. This verification is load-bearing for the claim that HRCS reproduces Haar anticoncentration statistics.

    Authors: The exact formulas are derived analytically by carrying out the complete sum over the 2^k branches (see Eq. (12) and the subsequent derivation in Section 3). The small-n numerics are presented only as an independent numerical check of those closed-form expressions. To eliminate any ambiguity we will (i) revise the abstract to read “supported by exact closed-form expressions obtained by summing over all measurement branches” and (ii) add an explicit sentence in the main text stating that the summation is performed in full rather than approximated. These changes will be made in the revised version. revision: yes

Circularity Check

0 steps flagged

Derivation uses independent exact formulas for collision probability and power sums

full rationale

The paper's proof relies on deriving exact formulas for collision probability and higher-order power sums directly from the HRCS protocol's structure of interleaved random unitaries and mid-circuit measurements. These formulas are then shown to match the known statistics of Haar-random states in 2^n dimensions, establishing the ε-approximate anticoncentration property for the output n-bit distribution. No step reduces the target result to a self-definition, a fitted parameter renamed as prediction, or a load-bearing self-citation chain; the calculations appear self-contained and externally verifiable against standard Haar moments without presupposing the final anticoncentration claim.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 1 invented entities

The claim rests on standard quantum information assumptions about Haar measure anticoncentration and the validity of exact collision-probability formulas under the new protocol; no free parameters or invented physical entities are introduced beyond the protocol definition itself.

axioms (2)
  • domain assumption Haar-random states exhibit ε-approximate anticoncentration
    The target property the protocol is required to reproduce.
  • domain assumption Exact formulas for collision probability and higher-order power sums remain valid under mid-circuit measurements
    The analyses are built upon these formulas.
invented entities (1)
  • Holographic random circuit sampling (HRCS) no independent evidence
    purpose: Interleave random unitary evolution with mid-circuit measurements to reduce physical qubit count
    New protocol introduced to establish the space-time tradeoff.

pith-pipeline@v0.9.0 · 5430 in / 1355 out tokens · 61750 ms · 2026-05-17T23:48:35.206864+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

44 extracted references · 44 canonical work pages · 2 internal anchors

  1. [1]

    comparable to the system dimension2 NA, we again see a suppression of the XEB performance improvements which might originate from the decoherence of system qubits

    With larger temporal steps, i.e. comparable to the system dimension2 NA, we again see a suppression of the XEB performance improvements which might originate from the decoherence of system qubits. Therefore, it is important to identify the balance between the number of physical qubitsN A +N B and the temporal stepst to maximize the performance of HRCS con...

    work page

  2. [2]

    P. W. Shor, inProceedings 35th annual symposium on foundations of computer science(Ieee, 1994) pp. 124– 134

    work page 1994

  3. [3]

    P. W. Shor, SIAM review41, 303 (1999)

    work page 1999

  4. [4]

    R. P. Feynman, inFeynman and computation(cRc Press,

    work page

  5. [5]

    Lloyd, Science273, 1073 (1996)

    S. Lloyd, Science273, 1073 (1996)

    work page 1996

  6. [6]

    Hangleiter and J

    D. Hangleiter and J. Eisert, Rev. Mod. Phys.95, 035001 (2023)

    work page 2023

  7. [7]

    N. Moll, P. Barkoutsos, L. S. Bishop, J. M. Chow, A. Cross, D. J. Egger, S. Filipp, A. Fuhrer, J. M. Gam- betta, M. Ganzhorn,et al., Quantum Science and Tech- nology3, 030503 (2018)

    work page 2018

  8. [8]

    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,et al., Nature574, 505 (2019)

    work page 2019

  9. [9]

    Morvan, B

    A. Morvan, B. Villalonga, X. Mi, S. Mandrà, A. Bengts- son, P. Klimov, Z. Chen, S. Hong, C. Erickson, I. Droz- dov,et al., Nature634, 328 (2024)

    work page 2024

  10. [10]

    Wu, W.-S

    Y. Wu, W.-S. Bao, S. Cao, F. Chen, M.-C. Chen, 8 Effective # of qubitsNeff XEB fidelityFXEB Prior work (Authors-# of qubits) Our experiment (# of qubits)Factor of improvement 10 0.3694 (Google2019-12Q) 0.5277 (10Q) 1.4285 15 0.3297 (Google2019-12Q) 0.2809 (10Q) 0.8520 0.312 (USTC2021-15Q) 0.900 0.396 (USTC2022-15Q) 0.709 25 0.1407 (Google2019-24Q) 0.1308 ...

    work page doi:10.5061/dryad.k6t1rj8 2021

  11. [11]

    Q. Zhu, S. Cao, F. Chen, M.-C. Chen, X. Chen, T.-H. Chung, H. Deng, Y. Du, D. Fan, M. Gong,et al., Science bulletin67, 240 (2022)

    work page 2022

  12. [12]

    D. Gao, D. Fan, C. Zha, J. Bei, G. Cai, J. Cai, S. Cao, F. Chen, J. Chen, K. Chen,et al., Phys. Rev. Lett.134, 090601 (2025)

    work page 2025

  13. [13]

    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. Dreiling, C. Foltz, J. P. Gaebler, T. M. Gatterman, C. N. Gilbreth, J. Giles, D. Gresh, A. Hall, A. Hankin, A. Hansen, N. Hewitt, I. Hoffman, C. Holliman, R. B. Hutson, T. Jacobs, J. Johansen, P...

    work page 2025

  14. [14]

    Barak, C.-N

    B. Barak, C.-N. Chou, and X. Gao, arXiv:2005.02421 (2020)

    work page arXiv 2005

  15. [15]

    A. M. Dalzell, N. Hunter-Jones, and F. G. Brandão, PRX Quantum3, 010333 (2022)

    work page 2022

  16. [16]

    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, Nature Physics14, 595 (2018)

    work page 2018

  17. [17]

    Bouland, B

    A. Bouland, B. Fefferman, C. Nirkhe, and U. Vazirani, Nature Physics15, 159 (2019)

    work page 2019

  18. [18]

    Neill, P

    C. Neill, P. Roushan, K. Kechedzhi, S. Boixo, S. V. Isakov, V. Smelyanskiy, A. Megrant, B. Chiaro, A. Dunsworth, K. Arya,et al., Science360, 195 (2018)

    work page 2018

  19. [19]

    A.M.Dalzell, N.Hunter-Jones,andF.G.Brandão,Com- munications in Mathematical Physics405, 78 (2024)

    work page 2024

  20. [20]

    Fefferman, S

    B. Fefferman, S. Ghosh, M. Gullans, K. Kuroiwa, and 9 K. Sharma, PRX Quantum5, 030317 (2024)

    work page 2024

  21. [21]

    Note thatZ=Z H is the sweet spot for RCS complex- ity, as further smaller CP such as the extremely case of Zuni = 1/dfor a uniform distribution, RCS becomes sim- ple again

    work page

  22. [22]

    Simulation of low-depth quantum circuits as complex undirected graphical models

    S. Boixo, S. V. Isakov, V. N. Smelyanskiy, and H. Neven, arXiv:1712.05384 (2017)

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  23. [23]

    Schollwock, Emergent Phenomena in Correlated Mat- ter (2013)

    U. Schollwock, Emergent Phenomena in Correlated Mat- ter (2013)

    work page 2013

  24. [24]

    I. L. Markov and Y. Shi, SIAM Journal on Computing 38, 963 (2008)

    work page 2008

  25. [25]

    Bluvstein, S

    D. Bluvstein, S. J. Evered, A. A. Geim, S. H. Li, H. Zhou, T. Manovitz, S. Ebadi, M. Cain, M. Kalinowski, D. Hangleiter,et al., Nature626, 58 (2024)

    work page 2024

  26. [26]

    M. Liu, R. Shaydulin, P. Niroula, M. DeCross, S.-H. Hung, W. Y. Kon, E. Cervero-Martín, K. Chakraborty, O. Amer, S. Aaronson,et al., Nature640, 343 (2025)

    work page 2025

  27. [27]

    Contributors, Zenodo: Geneva, Switzerland (2023)

    Q. Contributors, Zenodo: Geneva, Switzerland (2023)

    work page 2023

  28. [28]

    Zhang, J

    S.-X. Zhang, J. Allcock, Z.-Q. Wan, S. Liu, J. Sun, H. Yu, X.-H. Yang, J. Qiu, Z. Ye, Y.-Q. Chen,et al., Quantum 7, 912 (2023)

    work page 2023

  29. [29]

    Zhang, P

    B. Zhang, P. Xu, X. Chen, and Q. Zhuang, Nature Com- munications16, 6341 (2025)

    work page 2025

  30. [30]

    Scaling Laws of Quantum Information Lifetime in Monitored Quantum Dynamics

    B. Zhang, F. Hu, R. Mo, T. Chen, H. E. Türeci, and Q. Zhuang, arXiv preprint arXiv:2506.22755 (2025)

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  31. [31]

    J. S. Cotler, D. K. Mark, H.-Y. Huang, F. Hernández, J. Choi, A. L. Shaw, M. Endres, and S. Choi, PRX quan- tum4, 010311 (2023)

    work page 2023

  32. [32]

    W. W. Ho and S. Choi, Phys. Rev. Lett.128, 060601 (2022). Acknowledgments. Q.Z. and B.Z. acknowledge support from NSF (CCF- 2240641, OMA-2326746, 2350153), ONR N00014-23-1- 2296, AFOSR MURI FA9550-24-1-0349 and DARPA (HR0011-24-9-0362, HR00112490453, D24AC00153-02). The experiment was conducted using IBM Quantum Sys- tems provided through USC’s IBM Quantu...

    work page 2022

  33. [33]

    1a in the main text)

    Setup of holographic random circuit sampling We begin with the conventional random circuit sampling (RCS) that has been adopted to demonstrate quantum advantage [7, 9] (see Fig. 1a in the main text). Given a unitary quantum circuitU∈ U(2N ), and a trivialN-qubit initial state|0⟩=|0⟩ ⊗N, we can generally write out its output state from the circuit as |ψ⟩=U...

    work page

  34. [34]

    anticoncentrated

    Anticoncentration The random circuit sampling problem asks how hard it is to classically simulate a distributionpC(·)generated from a quantum deviceC. For a typical state, when the distributionpC(x)is widely supported over all computational basis |x⟩, but not yet uniform over all basis, the sampling is expected to be a hard task. On the other hand, if the...

    work page

  35. [35]

    Let us begin with the doubled Hilbert space representation of operators

    Identities for Haar integral We first introduce some important identities utilized in the following derivations of CP and PS in both Haar random states and HRCS. Let us begin with the doubled Hilbert space representation of operators. For an arbitrary operator ˆA, we define the doubled Hilbert space representation by ˆA= X i,j |i⟩ ⟨j| ⟨i|ˆA|j⟩ → ˆA E E = ...

    work page

  36. [36]

    [14, 15], and extend to theK-th PS

    Sampling from Haar random states In this section, we review the CP of Haar random states, studied in Ref. [14, 15], and extend to theK-th PS. Lemma 3The ensemble-averaged collision probability for sampling inN-qubit Haar random states is ZH(N) = 2 2N + 1 .(B14) Proof.Here we provide two different approaches to prove Lemma 3 utilizing the Haar twirling ide...

    work page

  37. [37]

    Subsystem sampling in Haar random states Finally, we show the sampling on a subsystem of Haar random states. Lemma 5For a Haar random quantum state|ψ⟩ AB in a bipartite systemH=H A ⊗ HB withN=N A +N B qubits, the marginal sampling distributionp Haar(xB) =| B ⟨xB|ψ⟩AB |2 follows the Beta distribution P[pH(xB) =p] = Beta(d A,(d B −1)d A),(B28) whered A = 2 ...

    work page

  38. [38]

    t 1−d −1 B +d −t B −1 dA +O 1 d2 A # .(C24) Therefore, the asymptotic form ofZHRCS(t)becomes ZHRCS(t) =Z H(Neff) exp

    Proof of Theorem 1 Theorem 7(Theorem 1 in main text) For holographic random circuit sampling with each unitaryU t in2-design, the ensemble-averaged collision probability at stept≥1is ZHRCS(t) = 2(dA + 1)t−1 (1 +d AdB)t ,(C1) whered A = 2 NA , dB = 2 NB are Hilbert space dimensions of the system and bath. In the large-system limitd A ≫1, ZHRCS(t) =Z H(Neff...

    work page

  39. [39]

    K(K−1) t 1−d −1 B +d −t B −1 2dA +O 1 d2 A # ≤Z (K) H (Neff) exp

    Proof of Theorem 2 Theorem 8(Theorem 2 in the main text) For holographic random circuit sampling with each unitaryU t inK-design, the ensemble-averagedK-th power sum at stept≥1is Z(K) HRCS(t) =K!d Adt B (dA +K−1)! (dA −1)! t−1 (dAdB −1)! (dAdB +K−1)! t ,(C28) 18 whered A = 2 NA , dB = 2 NB are Hilbert space dimensions of the system and bath. In the large-...

    work page

  40. [40]

    From the definition in Eq

    Upper bound on total variation distance In this section, we provide the proof to the upper bound on the total variation distance (TVD) in Methods. From the definition in Eq. (11), following the approach in Ref. [18], we have the upper bound by TVD =E C EU 1 2 ∥PC[y]−P U (y)∥1 ≤2 Neff /2 EC EU 1 2 ∥PC(y)−P U (y)∥2 (C53) ≤ 1 2 q 2Neff EC EU ∥PC(y)−P U (y)∥2...

    work page

  41. [41]

    The intuition is simple

    Reset in HRCS In this section, we show that whether adopting the reset strategy does not affect the CP and PS. The intuition is simple. Suppose we perform measurement on bath without following reset, we just need to add a few Pauli-X gate on corresponding bath qubits to flip their states from|1⟩to|0⟩. Since the circuit unitary is assumed to be Haar random...

    work page

  42. [42]

    The proofs still rely on the equivalent expansion though with different boundary conditions (see Fig

    Proof of Theorem 9 We will divide Theorem 9 into two parts, including the spatial part (Theorem 10) and and temporal part (Theo- rem 11). The proofs still rely on the equivalent expansion though with different boundary conditions (see Fig. 5b and c). Theorem 10(Theorem 9, spatial sampling part) For holographic random circuit sampling with each unitaryU t ...

    work page

  43. [43]

    , P[zt], and we derive a theoretical result with respect to AC as follows

    Temporal sampling per step in HRCS In this section, we focus on the marginal temporal sampling per step in HRCS, i.e., the distribution of P[z 1], P[z2], . . . , P[zt], and we derive a theoretical result with respect to AC as follows. 25 Theorem 12(Temporal sampling per step in HRCS)For holographic random circuit sampling with each unitaryU t satisfying2-...

    work page

  44. [44]

    Additional numerical results on marginal sampling in HRCS We verify the decay of CP in spatial sampling in Fig. 6a. Specifically, the relative deviation of CP with respect to uniform oneZ Sp(t)/Zuni(NA)−1reveals an exponential decay in early stage of2 −tNB (dashed lines) and later convergence to the finite-size correction of1/d2 AdB. The critical temporal...

    work page