Efficient classical simulation of random shallow 2D quantum circuits

1.1 How hard is it for classical computers to simulate quantum circuits?

• Conventional tensor-contraction reasoning treats random 2D circuits of depth d ≥3 as nearly worst-case hard because cost is governed by the smallest cut through their space-time volume.Depth-1 and depth-2 circuits have simple exact simulations [TD02], while stabilizer circuits [Got98] and sufficiently unentangled one-dimensional systems [Vid03] [Vid04] are efficient exceptions.Source: §1.1 · pp. 3–5
• For certain constant-depth architectures, typical random circuit instances with small allowed error can be simulated in time O(L1L2), although arbitrary instances remain classically intractable under standard complexity assumptions.The result exploits gate randomness and approximation rather than near-exact simulation.Source: §1.1 · p. 3
• The efficient regime is motivated by reducing shallow 2D random circuits to effective 1D dynamics with random local unitaries and weak measurements that suppress entanglement.This reduced entanglement makes efficient classical simulation possible in sufficiently shallow settings.Source: §1.1 · p. 4
• The paper provides numerical and analytical evidence that efficient simulation extends beyond the proven architecture to sufficiently shallow random circuits more generally.The evidence concerns low constant depth and supports the broader conjecture that sufficiently shallow random circuits are efficiently simulable.Source: §1.1 · pp. 3–4
• Complexity-theoretic arguments support worst-case or near-exact hardness through post-selected universality and worst-to-average-case reductions, but the proposed algorithms avoid these barriers by allowing small error.The hardness results rely on conjectures such as an infinite polynomial hierarchy and often anti-concentration; near-exact output-probability computation is #P-hard for some architectures.Source: §1.1 · p. 4
• Random-circuit hardness is also motivated by near-maximal entanglement, the absence of algorithms exploiting random inputs, and the lack of obvious structure admitting simple simulation.Known exceptions include noisy random circuits and heuristic tensor-network approximations whose overall simulation error may be unclear.Source: §1.1 · pp. 4–5
• The paper proposes two simulation algorithms: a 2D-to-1D tensor-network method and a method that exactly simulates small subregions before stitching them together.Both algorithms’ performance is related to entropic quantities, and the first is implemented numerically.Source: §1.1 · p. 5
• It identifies computational phase transitions even for noiseless quantum-circuit simulation, driven by local qudit dimension q and circuit depth d.The proposed picture is that enough entanglement-destroying random measurements overcome entanglement-preserving effects, with an analogy to percolation in cluster-state MBQC.Source: §1.1 · pp. 5–6

1.2.1 Provable complexity separations

• These separations hold for certain non-uniform extended brickwork architectures, improving on prior exact tensor-network simulation time 2^Θ(nc′), but do not establish simulability for natural architectures.The hardness statements rely on standard assumptions involving polynomial-hierarchy collapse and randomized computation of #P-hard functions.Source: §1.2 · p. 6, §1.2.1 · p. 7
• O(n)-time algorithms approximately sample and estimate output probabilities for all but 2^-nc of instances, despite hardness of exact sampling and near-exact probability computation.The sampling error is at most 2^-nc in total variation distance; probability estimates have additive error 2^-n/2nc.Source: §1.2.1 · p. 7
• The results rule out improving worst-to-average-case hardness for output probabilities to error 2^-n/2nc, so hardness proofs for random circuit sampling must depend on circuit depth.This excludes applying that strategy to worst-case-hard shallow ensembles that admit approximate average-case simulation.Source: §1.2.1 · p. 8

1.2.2 Conjectures for uniform architectures

• Conjecture 1 posits uniform architectures that remain worst-case intractable while algorithms simulate typical instances in poly(n,1/ε,1/δ) time with variational and probability errors ε and ε/q^n.Conjecture 1’ proposes the stronger runtime n^1+o(1) · exp scaling, supported by numerical simulations and toy models.Source: §1.2.2 · pp. 8–9
• The conjectured efficient regime is expected to undergo computational phase transitions as depth or local qudit dimension increases, reaching 2^O(L) runtime beyond thresholds.Evidence includes a rigorous 2D-to-1D reduction, numerical tests on depth-3 brickwork circuits [BFK09], statistical-mechanical mappings, and a toy model.Source: §1.2.2 · pp. 8–9

1.3.1 Reduction to “unitary-and-measurement” dynamics.

• SEBD reduces an L × L′ constant-depth circuit to effective 1D dynamics iterated for L′ or L timesteps, and rigorously relates simulation error to entanglement spectra.The algorithm gives conditions for efficient sampling and probability estimation and is self-certifying through confidence intervals for simulation error and simulable-instance fractions.Source: §1.3.1 · pp. 9–10

1.3.2 Proof idea for rigorous complexity separation with non-uniform architectures.

• A non-uniform architecture makes weak-measurement strength grow rapidly with system size, allowing constant-bond-dimension MPS compression with very low error and efficient simulation.This mechanism relies on measurement-induced destruction of pre-existing entanglement and underpins the rigorous complexity separation.Source: §1.3.2 · p. 11

1.3.3 Numerical evidence for conjectures.

• SEBD numerically simulates typical depth-3 brickwork instances on 409 × 409 grids with variational-distance error below 0.01 in roughly one minute per sample.The simulations provide evidence that efficiency persists asymptotically, while tensor-network contraction is argued to be intractable at comparable scales.Source: §1.3.3 · pp. 11–12
• Numerics show area-law von Neumann and sub-unit-index Rényi entropies, superpolynomial Schmidt-spectrum decay, and strong support for Conjectures 1 and 1′.The stronger Rényi area law implies efficient MPS representation, while the spectrum matches the toy model’s predicted scaling.Source: §1.3.3 · p. 12

1.3.4 Analytical evidence for conjectures from statistical mechanics.

• Statistical-mechanical mappings predict an area-to-volume-law transition near qc ≈6 for brickwork quasi-entropy ˜S2 and support analogous q- and depth-driven computational transitions.For q = 2 or q = 3, ˜S2 obeys an area law; sufficiently large q produces a volume-law phase, although this does not rigorously prove SEBD’s transition.Source: §1.3.4 · p. 14
• Patching uses exponentially decaying quasi-conditional mutual information to simulate shallow random circuits efficiently with high probability, improving prior quasi-polynomial runtime to polynomial.In the ordered large-q limit, expected classical-output CMI approaches (1 − γ)/ln2 ≈ 0.61, providing evidence against Patching efficiency.Source: §1.3.4 · p. 14

• Increasing noise may push the associated statistical-mechanical model toward a disordered, algorithmically efficient phase, enabling simulation at larger depths and qudit dimensions.This suggests a three-dimensional phase diagram governed by circuit depth, qudit dimension, and noise strength.Source: §1.4 · p. 15
• Whether random 2D circuits of arbitrary depth can be approximately simulated remains open, particularly for Google’s supremacy experiment.Under Conjecture 2, the proposed algorithms cease to be efficient beyond some constant depth, but this may reflect the method rather than an inherent barrier.Source: §1.4 · p. 15
• The algorithms’ efficiency for nonrandom shallow 2D evolutions, including short-time evolution under a fixed local 2D Hamiltonian, is unknown.Although the algorithms are defined for all 2D circuits, their efficiency beyond random circuits remains to be established.Source: §1.4 · p. 15
• A rigorous proof of Conjecture 1 may require a worst-case-hard uniform circuit family supporting analytic continuation of quasi-entropies ˜S_k as k →1.Source: §1.4 · p. 15
• Numerical tests of Conjecture 2 should vary local Hilbert-space dimension and circuit depth to determine whether the algorithms eventually undergo computational phase transitions into inefficiency.Source: §1.4 · p. 15
• Future work should determine how correlation lengths and statistical-mechanical phase transitions predict simulation runtime, and whether SEBD outperforms exponential-time methods near its entanglement transition.Such understanding could enable Monte Carlo prediction of algorithmic performance for arbitrary, possibly noisy, random-circuit distributions, including regimes where direct simulation is infeasible.Source: §1.4 · p. 15

Section 2

• Section 2 specifies and analyzes SEBD and Patching, including runtime bounds, unitary-and-measurement examples, an area-law toy model, and supporting Conjecture 1’.Section 2.1 covers SEBD, Section 2.2 connects efficiency to unitary-and-measurement simulability, Section 2.3 studies the toy model, and Section 2.4 analyzes Patching.Source: §1.5 · p. 16

Section 3

• Section 3 proves a complexity separation for a particular architecture, requiring only Section 2.1 for understanding.Source: §1.5 · p. 16

Section 4

• Section 4 presents numerical evidence supporting Conjecture 1 and Conjecture 1’.Source: §1.5 · p. 16

Section 5

• Section 5 introduces statistical-mechanical mappings and applies them to one-dimensional circuits with weak measurements corresponding to the cluster-state dynamics studied in Section 2.2.Section 5.1 reviews the mapping technique, while Section 5.2 analyzes the corresponding weak-measurement circuit family.Source: §1.5 · p. 16

Section 6

• Section 6 applies the mapping to shallow random 2D circuits, supports Conjectures 1 and 2 for SEBD and Patching, and strengthens the evidence using the brickwork architecture.Section 6.1 treats shallow random 2D circuits; Sections 6.2–6.3 address SEBD and Patching; Section 6.4 studies brickwork in greater detail.Source: §1.5 · p. 16

2 Algorithms

• SEBD reduces 2D circuit sampling to a 1D process simulated with MPS methods, remaining efficient when polynomially bounded bond dimensions suffice.The untruncated algorithm samples the exact output distribution, while truncation trades accuracy for smaller bond dimensions.Source: §2 · p. 16, §2.1.1 · p. 21
• Patching samples disconnected lattice patches and stitches them into a global sample when output-distribution conditional mutual information decays exponentially, improving the runtime over [BK19] to polynomial time.The method adapts an algorithm for finite-correlation-length Gibbs-state preparation while exploiting classical outputs from constant-depth local circuits.Source: §2 · p. 17
• The two algorithms’ apparently different efficiency criteria are related through phases of a statistical-mechanical model: the ordered phase suggests both criteria hold, whereas the disordered phase suggests neither does.This motivates the conjecture that SEBD efficiently simulates a random circuit family if and only if Patching can.Source: §2 · p. 17

2.1.1 Specification of algorithm

• SEBD processes columns in measurement order, applying only previously unapplied lightcone gates and conditioning an MPS on each sampled column outcome.Without truncation, it eventually reaches bond dimension up to q^O(dL1) and samples from the true output distribution; with cutoff D, runtime is O(nD^3) for constant q and d.Source: §2.1.1 · pp. 20–21
• For constant q and d, polynomial expected bond dimension in n and 1/ϵ implies polynomial-time SEBD sampling with variational-distance error below ϵ for at least 1 − δ of circuit instances.This criterion is identified as sufficient for proving approximate sampling for uniform random circuit families with the required worst-case-hard property.Source: §2.1.1 · p. 22

2.1.2 Computing output probabilities

• SEBD computes a truncated output probability for a fixed string by projecting each column onto the prescribed outcome and contracting the conditional MPS, in time O(nD^3).If a bond dimension exceeds D, the algorithm outputs zero and terminates; otherwise it returns the product of conditional probabilities obtained during the column sweep.Source: §2.1.2 · p. 23
• If expected bond dimensions are poly(n,1/ϵ), SEBD estimates any fixed output probability to additive error ε/q^n in poly(n,1/ε,1/δ) time with probability at least 1−δ.This corollary applies for constant q and d, using polynomial truncation and bond-dimension parameters.Source: §2.1.2 · p. 24

2.2 SEBD applied to cluster state with Haar-random measurements

• CHR is worst-case hard for classical sampling unless PH collapses to the third level, while near-exact average-case output-probability computation is #P-hard.The sampling hardness follows from [BJS10], and the probability hardness follows from [Mov19].Source: §2.2 · p. 25

2.2.1 SEBD applied to CHR

• SEBD on CHR is equivalent to TEBD on a 1D chain undergoing alternating random local unitaries and weak measurements, preserving states and measurement statistics.Randomizing Haar measurement bases yields an effective process whose state sequences and output statistics are identical to those of SEBD on CHR.Source: §2.2.1 · pp. 26–27
• If TEBD efficiently simulates this effective process with polynomial expected bond dimension, then SEBD solves CHRsamp, while broader circuits map to dynamics with dimension q^O(r) and depth-dependent measurement strength.Increasing depth increases effective local dimension and decreases the fraction of measured qudits, suggesting an area-law-to-volume-law computational phase transition as q or d grows.Source: §2.2.1 · pp. 28–29

2.3 Conjectured entanglement spectrum of unitary-and-measurement dynamics in an area-law phase

• The toy unitary-and-measurement model predicts asymptotic Schmidt-spectrum decay, a truncation-rank relation, and an SEBD runtime n^1+o(1) that simulates a 1−δ fraction of instances within variational-distance error ε.These predictions support Conjecture 1’ for effective dynamics in the area-law phase and use runtime scaling O(nD^3).Source: §2.3 · p. 30
• The toy-model argument is heuristic because real unitary dynamics entangles Schmidt bases, measurement angles are random, and pair movement is idealized, although its spectrum matches numerical results.The authors expect cyclic pair movement, if consequential, to make the toy model overly pessimistic.Source: §2.3 · p. 30

2.4 Patching

• The algorithm samples separated lattice patches independently, then applies recovery maps to stitch them into connected regions and fill the remaining holes.Constant-depth lightcones make separated patches independent, while small conditional mutual information bounds the recovery-map error.Source: §2.4 · pp. 32–33
• For a fixed circuit satisfying the δ(l)-Markov condition, Patching runs in time nqO(dl) with total-variation error O(1)(n/l^2)δ(l).Choosing l = Θ(log n) yields polynomial time and inverse-polynomial accuracy when d and q are constant and δ(l) decays exponentially up to polynomial factors.Source: §2.4 · p. 32
• Patching runs in time poly(n) and samples within 1/r(n) of the output distribution with probability 1−1/s(n) when constant-depth, constant-dimension circuit distributions are poly(n)e^−Ω(l)-Markov.This follows from the patching theorem and its random-circuit corollary, using a suitable length scale l = Θ(log n).Source: §2.4 · pp. 32–33
• Analytical evidence predicts that sufficiently shallow random circuits with small qudit dimension satisfy the Markov condition, whereas larger depth or dimension violates it and supports a computational phase transition.The condition is proposed as a route to efficient approximate sampling and is expected to fail beyond critical circuit parameters.Source: §2.4 · pp. 33–34
• Under the same Markov condition, a Patching variant estimates any fixed output probability in polynomial time with probability 1−1/s(n).The algorithm replaces sampling from conditional probabilities with multiplying them, assuming invariance under a final layer of arbitrary single-qudit gates.Source: §2.4 · p. 34

Worst-case hardness

• Despite this average-case efficiency, exact sampling from arbitrary extended-brickwork instances would collapse the polynomial hierarchy to its third level, while near-exact fixed-output probabilities would enable probabilistic polynomial-time computation of a #P-hard function.The hardness applies for polynomially bounded r(L), v(L), with v(L) ≥ L^a for some a > 0, and additive error 2^−˜Θ(n^2).Source: §3 · pp. 35–36
• The architecture supports universal measurement-based quantum computation because its length-2r one-dimensional stretches can teleport the effective state while preserving the standard brickwork construction’s universality.The condition v ≥ L^a supplies polynomial overhead sufficient to simulate arbitrary BQP computations.Source: §3 · p. 35

Entanglement-decay mechanism

• Long 1-local regions contain no two-qubit gates, and their measurement-induced entanglement decay lets SEBD compress the effective MPS to constant bond dimension with high probability.For a depth-2 1D Haar-random circuit, measuring a contiguous block of length proportional to r leaves expected entanglement entropy at most 2^−Θ(r).Source: §3 · pp. 36, 38, 39

Efficient average-case simulation

• SEBD achieves this using maximal bond dimension D = Θ(1), with probability at least 1 − 2^−Θ(r), while sampling error is n2^−Θ(r) and fixed-output probability error is n2^−Θ(r)/2^n.The runtime is linear because SEBD costs O(nD^3) on qubits and D is constant.Source: §3 · pp. 37, 39
• For r = Θ(log(L)), SEBD simulates 1 − 1/poly(n) of instances with inverse-polynomial error in O(n) time; polynomially larger r yields exponentially small error and failure probability.Specifically, r = Θ(L^c) supports error at most 2^−n^(1−δ) for a 1 − 2^−n^(1−δ) fraction of instances, for any constant δ > 0.Source: §3 · p. 39

Overall simulation performance

• One-minute samples of typical 409 × 409 brickwork circuits and five-minute samples of typical 34 × 34 CHR circuits achieved variational-distance error below 0.01.The simulations used truncation errors 10−14 and 10−10 per bond, respectively, on a standard laptop.Source: §4 · p. 41
• Over 3000 brickwork trials yielded no failures, supporting a 0.999 successful-simulation probability and a 0.9 simulable fraction at error at most 0.01 with 95% confidence.The authors expect the true simulable fraction to be substantially larger because extensive entanglement appears confined to highly structured instances.Source: §4 · p. 41

Entanglement spectra

• Brickwork is cheaper than CHR because its effective dynamics have lower entanglement and much faster-decaying Schmidt spectra, whereas CHR permits more costly spectrum analysis.Brickwork simulations were limited mainly by numerical precision, while CHR’s slower-decaying spectrum increased runtime.Source: Figure 8 · p. 41, §4 · p. 42

Entanglement scaling

• The effective one-dimensional dynamics exhibit concentrated area-law entanglement rather than extensive growth, with qualitatively similar behavior for Rényi entropies Sα with α < 1.Figures 6 and 7 show saturation and concentration, supporting efficient matrix-product-state descriptions and the conjectured efficiency of SEBD.Source: Figure 6 · p. 40, Figure 7 · p. 40, §4 · p. 42

Entanglement spectra

• CHR spectra show superpolynomial eigenvalue decay consistent with λi ∼2−Θ(log2(i)), indicating that bond dimension D = poly(1/ϵ) may suffice for truncation error ϵ.The observed scaling agrees qualitatively with the toy-model prediction, although larger depths and local dimensions needed to test eventual inefficiency remain unexplored.Source: Figure 8 · p. 41, §4 · pp. 42–43

5.1 Mapping procedure

• The stat-mechanical quantity is a quasi-entropy, which converges to the expected von Neumann entropy as k → 1 but can differ from expected Rényi entropy because of averaging and logarithms.For integer k ≥ 2, prior analyses support quasi-entropy as a proxy, especially for S_2 in large-q or measurement-free settings [Von+18].Source: §5.1 · p. 45
• The mapping expresses Haar-random circuit quantities as partition functions of a classical model whose spins are permutations and whose boundary conditions encode the entanglement region.Circuit unitaries become graph nodes, edge weights arise from Haar integration and measurements, and the free energy is the negative logarithm of the partition function.Source: §5.1 · pp. 45–46
• For k = 2, the model becomes Ising-like; decimating incoming nodes removes negative weights but generates three-body interactions, enabling real-temperature classical-model analysis.The resulting positive-weight representation supports numerical methods such as Monte Carlo sampling.Source: §5.1 · pp. 47–48

5.2 Mapping applied to 1D circuits with weak measurements

• In one-dimensional circuits with weak measurements, the mapping produces a honeycomb lattice whose horizontal interactions come from Weingarten weights and diagonal interactions from the measurement process.The analysis reproduces the connection between the area-law-to-volume-law entanglement transition and a disorder-to-order thermal transition, using a weak measurement chosen for SEBD dynamics [BCA19] [Jia+19].Source: §5.2 · p. 48, Figure 10 · p. 49
• For the chosen weak measurement, the k = 2 interaction is ferromagnetic for every q > 1 and strengthens as the local dimension q increases.The interaction favors agreeing node values regardless of which weak measurement outcome occurs.Source: §5.2 · p. 50
• Decimating incoming spins converts the k = 2 honeycomb model into a triangular lattice with two-body interactions, including stronger ferromagnetic than antiferromagnetic couplings.The three-body weights factor into two-body weights on triangle edges, and the resulting model is an anisotropic Ising model.Source: §5.2 · p. 51
• qc = 3.249 separates disorder at q = 2, 3 from order at q ≥4 in the mapped anisotropic triangular-lattice Ising model.Only integer q values correspond to valid quantum circuits.Source: Figure 11 · p. 52, §5.2 · p. 52
• The mapping predicts an area-law-to-volume-law transition in output Rényi-2 entropy as the classical model changes from disorder to order.The quasi-entropy scales as O(1) in the disordered phase and O(min(|A|,d)) in the ordered phase.Source: §5.2 · p. 52
• For q = 2 and q = 3, the quasi-2-entropy obeys an area law, whereas for q = 4 it obeys a volume law.These results use Haar-random two-qubit entangling gates and the same weak measurement studied in the effective SEBD dynamics.Source: §5.2 · p. 53
• The mapped dynamics partially explain why numerical SEBD on CHR exhibits an area law for q = 2 across several Rényi indices.Related analyses considered projective measurements and the q →∞ limit, where the model becomes a ferromagnetic Potts model [BCA19] [Jia+19].Source: §5.2 · p. 53

6 Evidence for efficiency of algorithms from statistical mechanics

• The mapping is not a rigorous efficiency proof because its quasi-entropy equals average entanglement entropy only in an inaccessible limit, though it can guide numerical runtime and error estimates.It remains the most promising analytical tool presented for Haar-random gates.Source: §6 · pp. 53–54
• Both algorithms are predicted efficient for sufficiently small depth and local dimension, including depth 3 and q = 2 brickwork circuits, while becoming inefficient beyond critical q_c or d_c.These transitions correspond to disorder-to-order transitions in the mapped classical model.Source: §6 · p. 54

6.1 Mapping applied to general 2D circuits

• The 2D circuit mapping produces a roughly √n × √n × d three-dimensional slab whose domain-wall energy competes with configurational entropy, yielding q- and depth-dependent phase transitions.Increasing q strengthens domain-wall energy, whereas increasing depth amplifies both energy and entropy; a depth transition is therefore expected but not definitively established.Source: §6.1 · pp. 54, 56, 57, Figure 12 · p. 55
• For the depth-3 brickwork architecture, the model is disordered at q = 2 and is estimated to transition to the ordered phase near q_c ≈ 6.The large-q limit is expected to be ordered for any depth and architecture.Source: §6.1 · pp. 56–57

6.2 Efficiency of SEBD algorithm from stat mech

• The SEBD interpretation assumes larger-Rényi-entropy behavior reflects the k < 1 area law required for efficient truncation, supported by numerical evidence that Rényi entropies scale similarly.The mapping cannot directly probe the required 0 < k < 1 regime.Source: §6.2 · p. 57
• For SEBD, a disordered mapped model implies area-law quasi-entropy and polynomial runtime, whereas an ordered model implies volume-law quasi-entropy and exponential runtime.Near the transition in the volume-law phase, the exponential runtime may have a small constant prefactor.Source: §6.2 · p. 58, Figure 13 · p. 59

6.3 Efficiency of Patching algorithm from stat mech

• In a disordered mapped model, quasi-conditional mutual information decays exponentially with shield separation, implying Patching efficiently samples and estimates output probabilities with high precision and probability.This conclusion treats quasi-2-CMI as a proxy for the average classical CMI.Source: §6.3 · pp. 59–60
• In the ordered q → ∞ limit, strict output subregions have maximal entropy, and the mapped model suggests Patching is unsuccessful.The entropy result is exact in the q → ∞ limit, where all integer quasi-entropies coincide and analytically continue to Shannon entropy.Source: §6.3 · p. 61
• In the ordered statistical-mechanics phase, the expected output-distribution CMI approaches the constant (1−γ) ln(2), so Patching is not expected to sample efficiently with small error.The entropy is 1−γ ln(2) less than maximal in the q →∞ limit, and the global spin-flip symmetry prevents quasi-CMIs from decaying.Source: §6.3 · p. 62

6.4 Depth-3 2D circuits with brickwork architecture

• The brickwork architecture reduces the mapped model to a planar graph with only two-body interactions, simplifying analysis while preserving universality for measurement-based quantum computation.Higher-depth architectures generally do not collapse straightforwardly to a single plane with two-body interactions.Source: §6.4 · p. 64
• The depth-3 brickwork mapping is disordered for q = 2 and q = 3, remains likely disordered for q = 4 and q = 5, and may cross toward order near q = 6.For q = 2, Jvert = 0.112 and Jhoriz = 0.319, both below Jsquare = 0.441; the averaged interaction slightly exceeds Jsquare for q = 6.Source: §6.4 · p. 65
• For Haar-random depth-3 brickwork circuits, SEBD has ˜S2 = O(1) for q = 2 or q = 3, with quasi-2-CMI decaying exponentially in dist(A,C), supporting efficient SEBD and Patching.The evidence likely extends to q = 4 and q = 5.Source: §6.4 · p. 65

Limitation of truncated-Taylor reductions

• [Bou+19] cannot show that SEBD and Patching make exact output-probability computation or output-distribution sampling for constant-depth Haar-random circuits classically hard with high probability.Its interpolation argument relies on slightly non-unitary circuit families, whereas the algorithms exploit unitarity by ignoring gates outside relevant lightcones.Source: A Relation to worst-to-average-case… · p. 66
• Increasing the interpolation parameter K makes the circuit family more Haar-like but also raises polynomial degree, leaving insufficient robustness to tolerate the algorithms’ simulation errors for any K.Thus, the required precision cannot be achieved even if SEBD and Patching simulate Haar-random circuit families well.Source: A Relation to worst-to-average-case… · p. 66

Implications

• The existence of unitarity-exploiting algorithms such as SEBD and Patching may obstruct worst-to-average-case reductions that obtain polynomial structure by sacrificing unitarity.The section frames this as a potential obstruction rather than a general impossibility result.Source: A Relation to worst-to-average-case… · p. 66

Alternative reduction

• The alternative Cayley-path reduction [Mov19] does not suffer from the robustness limitation affecting the truncated-Taylor approach.It is based on Cayley paths rather than truncated Taylor series.Source: A Relation to worst-to-average-case… · p. 66

Truncated Haar-random ensembles

• The construction multiplies each hard-circuit gate by a θ-pulled-back, K-truncated Haar-random gate, recovering Haar-random circuits at θ=0 and the hard circuit approximately at θ=1.For finite K, the resulting circuits are slightly non-unitary; sufficiently large K preserves hardness of the perturbed worst-case circuit.Source: Background: truncated Haar-random… · p. 66

Polynomial interpolation

• For an m-gate circuit, the output probability p0(A,θ,K) is a polynomial in θ of degree 2mK, with p0(A,1,∞)=p0(C).Source: Background: truncated Haar-random… · p. 67
• Accurate simulation for θ≤ϵ at 2mK+1 evenly spaced points enables construction of an interpolating polynomial that approximates p0 on a nontrivial interval, by Rakhmanov.Source: Background: truncated Haar-random… · p. 67

Worst-to-average-case contradiction

• Paturi’s lemma [Pat92] extends the approximation from the small-θ interval to θ=1, making q0(A,1,K) exponentially accurate when c is sufficiently large.The bound depends on the polynomial degree and the interval width, yielding |p0(A,1,K)−q0(A,1,K)|≤2^-poly(n).Source: Background: truncated Haar-random… · p. 67
• Therefore, under standard hardness conjectures, output probabilities for D(C,θ,K) remain hard to compute within 2^-nc for θ≤1/poly(n), for suitable K and sufficiently large c.Source: Background: truncated Haar-random… · p. 67

• The argument proves average-case classical hardness for a non-unitary family D(C,θ,K) that is 2^-poly(n)-close to the corresponding Haar-random family, assuming classical hardness of simulating C.Source: Limitation of the interpolation argument · p. 67
• Taylor truncation and polynomial interpolation cannot establish hardness for exactly computing Haar-random output probabilities with high probability.Source: Limitation of the interpolation argument · pp. 67–68
• To control errors across 2mK + 1 interpolation points, the parameter must satisfy ϵ ≤ O(1/m2K), while truncation contributes error δ ≤ 2O(nm)/K!.Source: Limitation of the interpolation argument · pp. 67–68
• Substituting these bounds yields an interpolation error no better than 2O(nm)/K!, which diverges as n →∞ for any scaling of m and K.Source: Limitation of the interpolation argument · p. 68
• Increasing K suppresses truncation error but raises the interpolating polynomial’s degree, making interpolation more sensitive to errors.Source: Limitation of the interpolation argument · p. 68

• [Bou+19] applies to slightly non-unitary distributions exponentially close to Haar, not directly to truly Haar-random circuits, so it cannot establish exact simulation hardness there.Source: Inapplicability to SEBD and Patching · p. 68
• The limitation might be fundamental: modifying an exact Haar-simulation algorithm to simulate truncated Haar circuits with interpolation-level precision is not evidently possible.Source: Inapplicability to SEBD and Patching · p. 68
• SEBD and Patching rely on constant-radius lightcones to ignore external gates, but this argument breaks down for non-unitary circuits, requiring general tensor-network contraction with runtime 2^O(d√n).Source: Inapplicability to SEBD and Patching · p. 68
• An interpolation error bounded by 2^O(nm)/K! from neglected non-unitary gates already exceeds the permitted tolerance, ruling out this reduction for SEBD and Patching.Source: Inapplicability to SEBD and Patching · pp. 68–69

SEBD truncation-error bound

• SEBD’s total sampling error is bounded by the accumulated square-root truncation errors, using MPS truncation bounds and contractivity of TPCP maps.The proof compares untruncated and truncated evolutions recursively and identifies each step’s expected 1-norm error with the corresponding truncation error.Source: B Deferred proofs · pp. 69–70

Toy-model Schmidt spectrum

• With high probability, the toy model’s tail Schmidt values obey asymptotic scaling that yields a controlled post-truncation Schmidt rank as a function of truncation error.The argument groups coefficients into strict-partition sectors, bounds sector fluctuations with Hoeffding’s inequality, and derives the index-to-coefficient scaling used for the rank estimate.Source: B Deferred proofs · pp. 70, 72, 73

Random-circuit entanglement decay

• Measuring a contiguous region in a 1D Haar-random circuit contracts expected entanglement across the remaining cut by a constant factor per measured layer, giving exponential decay with region size.A two-qubit technical lemma shows a constant entropy contraction under random gates and measurement; iterating it across the measured region preserves the bound under subsequent local unitaries.Source: B Deferred proofs · pp. 73, 75

Haar integration

• Haar-measure integration invokes a formula involving permutations σ and τ in the symmetric group Sk and the Weingarten function wg(τσ −1,q2) [Col03; C´S06].The Weingarten function can be defined by an expansion over irreducible characters of the symmetric group Sk.Source: C Justification of stat mech mapping · p. 75

Partition-function construction

• Applying this formula to all gates expresses E_U(Z_k,∅/A) as a weighted sum over permutation assignments and measurement choices, with factors depending locally on neighboring permutations.Each resulting tensor network decomposes into disjoint loops, whose unitary and weak-measurement contributions produce the weights in Eqs. (38)–(40).Source: C Justification of stat mech mapping · p. 76

Boundary conditions

• Auxiliary output nodes are fixed to e for Z_k,∅ and to (1...k) on qudits in A for Z_k,A, encoding the trace and output permutation boundary conditions.The trace pairs output indices without permutation, whereas W^(A) applies the k-cycle permutation before contraction on region A.Source: C Justification of stat mech mapping · p. 77
• No auxiliary input nodes are needed because the assumed pure product input forces the incoming indices to 0 and contributes a factor of 1.For a maximally mixed initial state, an auxiliary input layer fixed to e would instead be required.Source: C Justification of stat mech mapping · p. 77