PaperlayerView exact revision on arXiv

Source-linked AI summary

Efficient classical simulation of random shallow 2D quantum circuits

John Napp, Rolando L. La Placa, Alexander M. Dalzell, Fernando G. S. L. Brandao, Aram W. Harrow

arXiv:2001.00021v2quant-phcond-mat.stat-mechcs.CC

TL;DR

The paper addresses whether typical uniformly random shallow quantum circuits are almost as hard to simulate as worst-case circuits. It combines complexity separations with patching and a 2D-to-1D simulation reduction, finding efficient approximate simulation for some shallow families and evidence for phase transitions as depth or local dimension increases.

  • Problem

    It was unclear whether approximate simulation of typical uniformly random circuits is nearly as hard as exact or worst-case simulation.

  • Method

    The paper proposes patching and a space-evolving block-decimation approach that reduces 2D shallow-circuit simulation to effective 1D unitary-and-measurement dynamics.

  • Results

    Some shallow random circuit families remain worst-case hard but admit approximate simulation in O(n) time for almost all instances, with numerical and analytical evidence supporting broader efficiency.

  • Takeaways & Limitations

    Approximate average-case simulation can be much easier than worst-case or near-exact simulation for sufficiently shallow random circuits.

  • Takeaways & Limitations

    The rigorous separations use a contrived non-uniform architecture, while broader claims remain conjectural and depth beyond a constant may be inefficient.

Abstract

from arXiv · show

Random quantum circuits are commonly viewed as hard to simulate classically. In some regimes this has been formally conjectured, and there had been no evidence against the more general possibility that for circuits with uniformly random gates, approximate simulation of typical instances is almost as hard as exact simulation. We prove that this is not the case by exhibiting a shallow circuit family with uniformly random gates that cannot be efficiently classically simulated near-exactly under standard hardness assumptions, but can be simulated approximately for all but a superpolynomially small fraction of circuit instances in time linear in the number of qubits and gates. We furthermore conjecture that sufficiently shallow random circuits are efficiently simulable more generally. To this end, we propose and analyze two simulation algorithms. Implementing one of our algorithms numerically, we give strong evidence that it is efficient both asymptotically and, in some cases, in practice. To argue analytically for efficiency, we reduce the simulation of 2D shallow random circuits to the simulation of a form of 1D dynamics consisting of alternating rounds of random local unitaries and weak measurements -- a type of process that has generally been observed to undergo a phase transition from an efficient-to-simulate regime to an inefficient-to-simulate regime as measurement strength is varied. Using a mapping from quantum circuits to statistical mechanical models, we give evidence that a similar computational phase transition occurs for our algorithms as parameters of the circuit architecture like the local Hilbert space dimension and circuit depth are varied.

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

Classical simulation is widely expected to become hard for shallow 2D random circuits because randomness produces near-maximal entanglement, yet this paper shows that sufficiently shallow random circuits can sometimes be simulated efficiently.

  • The central question is where the boundary lies between classically simulable and classically hard quantum circuits, and which gate sequences are hardest at fixed size and runtime.
  • The paper challenges this picture by proving that some constant-depth random architectures admit approximate simulation in O(L1L2) time despite worst-case hardness.
  • Worst-to-average-case results make near-exact output-probability computation for random circuits hard on most instances, including architectures that are hard at depth three.
  • Random 2D circuits are expected to be nearly worst-case hard because random gates generate near-maximal entanglement and few known algorithms exploit random inputs.This expectation is supported by entanglement-growth results and the limited availability of randomness-specific simulation techniques.
  • The proposed algorithms exploit either a 2D-to-1D reduction or patch stitching, with efficiency governed by entanglement-related quantities.
  • The analysis suggests a noiseless computational phase transition: sufficiently strong entanglement-destroying measurements permit efficient simulation, while ordered statistical-mechanical phases obstruct it.

1.2 Our results

The paper combines rigorous complexity separations with conjectures, analytical reductions, and numerical evidence to argue that shallow random circuits can be easy on typical instances while remaining hard in the worst case.

  • The paper proves rigorous separations for a contrived architecture and supplies analytical and numerical evidence for efficient approximate simulation in more natural shallow random circuits.
  • Provable complexity separations: For a non-uniform architecture, exact worst-case sampling is hard, yet an O(n)-time algorithm approximately samples typical instances with error 2−nc and probability at least 1−2−nc.
  • Provable complexity separations: The same architecture permits O(n)-time estimation of any fixed output probability to additive error 2−n/2nc on all but a 2−nc fraction of circuit instances.
  • Provable complexity separations: These algorithms improve over the previous exact tensor-contraction runtime 2^Θ(L)=2^Θ(nc′) for the relevant architecture family.
  • Conjectures for uniform architectures: For uniform architectures, the paper conjectures efficient high-probability approximate simulation in some regimes and computational phase transitions as depth or qudit dimension increases.
  • Conjectures for uniform architectures: The analytical strategy reduces 2D simulation to effective 1D unitary-and-measurement dynamics, while SEBD bounds error and can certify its own simulation confidence.

1.3 Overview of proof ideas and evidence for conjectures

The paper reduces shallow 2D random-circuit simulation to effective 1D unitary-and-measurement dynamics and uses numerical and statistical-mechanical evidence to support efficient simulation and computational phase transitions.

  • Reduction to “unitary-and-measurement” dynamics: SEBD rigorously reduces shallow 2D circuit simulation to effective 1D dynamics and gives error and efficiency bounds for sampling and estimating output probabilities.The effective dynamics can be viewed as iterated on one grid dimension, while SEBD applies time-evolving block decimation along it.
  • Numerical evidence for conjectures: Numerics show entanglement quickly saturates independently of qubit number, including an area law for Rényi entropies with α < 1 that supports asymptotic SEBD efficiency.Such a condition is known to imply efficient matrix-product-state representations.
  • Numerical evidence for conjectures: The observed superpolynomial Schmidt-spectrum decay supports Conjectures 1 and 1′, including polynomial-time SEBD and stronger scaling with error parameters.The spectrum behavior is consistent with the paper’s toy model for unitary-and-measurement dynamics in the area-law phase.
  • Analytical evidence for conjectures from statistical mechanics: For brickwork circuits, quasi-entropy obeys an area law at q = 2 and q = 3, but transitions to a volume law near q_c ≈ 6 as local dimension increases.The area-law result corroborates SEBD efficiency in the qubit regime, while the estimated critical point marks the proposed computational transition.
  • Analytical evidence for conjectures from statistical mechanics: The statistical-mechanics mapping links boundary-twist free energies to quasi-entropies and gives evidence for area-law-to-volume-law transitions as qudit dimension increases.The analysis focuses on depth-3 brickwork because it is worst-case hard yet analytically tractable.
  • Analytical evidence for conjectures from statistical mechanics: Patching uses exponentially decaying conditional mutual information to stitch exactly simulated disconnected regions, with rigorous conditions for asymptotic efficiency.In an ordered phase, quasi-CMI fails to decay, providing evidence against Patching’s efficiency.

1.4 Future work and open questions

The paper identifies open questions about extending its simulation framework to noisy, deeper, nonrandom, and more efficiently characterized circuit dynamics.

  • Noise: The authors ask whether noise produces a three-dimensional phase diagram involving circuit depth, qudit dimension, and noise strength.They heuristically expect noise to weaken statistical-mechanical interactions and potentially permit simulation at larger depths and dimensions.
  • Depth and circuit family: A central open problem is whether random 2D circuits of arbitrary depth can be approximately simulated efficiently, especially beyond the constant-depth regime relevant to Google’s experiment.Under Conjecture 2, the proposed algorithms become inefficient beyond some constant depth, but it is unclear whether that reflects the problem or only the methods.
  • Beyond random circuits: Further questions concern whether the algorithms remain efficient for shallow nonrandom evolutions, such as short-time dynamics generated by a fixed local 2D Hamiltonian.The algorithms are defined for all 2D circuits, but efficiency beyond random circuits is unresolved.
  • Theory and quantitative prediction: The paper proposes proving Conjecture 1 by finding a worst-case-hard uniform family whose quasi-entropies admit analytic continuation to k → 1.It also calls for numerical tests of Conjecture 2 and sharper links between statistical-mechanical quantities and algorithmic runtime.
  • Algorithmic comparisons: When SEBD is inefficient, an open comparison is whether it still outperforms prior exponential-time methods near the entanglement transition.The authors expect this may hold close to the transition point, but present it as an intuition rather than a result.

1.5 Outline for remainder of paper

The remainder of the paper develops the algorithms and complexity separation, presents numerical evidence, and applies statistical-mechanical mappings to analyze both proposed simulators.

  • Algorithms and bounds: Section 2 specifies SEBD and Patching, derives runtime bounds, and studies their connection to unitary-and-measurement processes.It also analyzes a toy area-law model for such dynamics.
  • Complexity separation: Section 3 proves the complexity separation for a particular architecture, using only the SEBD analysis from Section 2.1.
  • Numerical evidence: Section 4 presents numerical evidence supporting Conjectures 1 and 1′.
  • Statistical-mechanics mapping: Section 5 introduces the circuit-to-statistical-mechanics mapping and applies it to weakly measured 1D dynamics associated with the cluster-state model.Section 5.2 is optional for readers focused only on the later shallow-circuit analysis.
  • Applications of the mapping: Section 6 applies the mapping to shallow random 2D circuits and supports Conjectures 1 and 2 for SEBD and Patching, with a detailed brickwork analysis.

2 Algorithms

The paper develops two classical algorithms for shallow 2D random-circuit simulation: SEBD reduces the problem to effective 1D dynamics represented by MPS, while Patching stitches samples from disconnected regions. Their efficiency is tied to bounded entanglement or exponentially decaying conditional mutual information, with analytical and numerical evidence supporting efficient simulation in suitable regimes.

  • SEBD: SEBD reduces 2D circuit simulation to 1D unitary-and-measurement dynamics simulated with TEBD, and is efficient when the effective state has polynomially bounded MPS representation.The algorithm tracks columns and periodically compresses the MPS; its efficiency depends on bond-dimension control.
  • Patching: Patching samples small disconnected lattice regions and stitches them into a global sample, achieving polynomial time when output-distribution conditional mutual information decays exponentially.The method improves a prior quasipolynomial approach to polynomial time by exploiting classical output distributions from constant-depth local circuits.
  • Efficiency evidence: The algorithms’ efficiency criteria appear related through statistical-mechanical phases: ordered phases suggest both criteria hold, whereas disordered phases suggest neither does.This provides a common framework for a computational phase transition as circuit parameters vary.
  • SEBD guarantees: Polynomially bounded expected bond dimension lets SEBD sample with inverse-polynomial total-variation error on all but a δ fraction of random circuit instances.For q=O(1) and d=O(1), the resulting runtime is polynomial in n, 1/ε, and 1/δ.
  • SEBD guarantees: The same bond-dimension condition lets SEBD estimate any fixed output probability to additive error ε/q^n with high probability over circuit instances.This connects efficient effective-1D simulation to approximate probability computation for uniform worst-case-hard circuit families.
  • Efficiency evidence: Numerical studies find area-law effective dynamics with compatible entanglement spectra, while the toy model predicts superpolynomial Schmidt-value decay sufficient for polynomial-time simulation.The effective process generalizes to random local unitaries followed by weak measurements, with depth increasing local dimension and reducing measurement strength.

3 Rigorous complexity separation for the “extended brickwork architecture”

The extended brickwork architecture separates worst-case classical hardness from typical-instance approximate simulability. SEBD achieves linear-time approximate simulation for almost all instances when the extension parameter is sufficiently large.

  • Worst-case hardness: The extended brickwork family remains worst-case hard: efficient exact sampling would collapse the polynomial hierarchy, while near-exact output-probability computation is linked to #P-hardness.The architecture supports universal measurement-based quantum computation, enabling the stated hardness consequences.
  • SEBD mechanism: Measuring columns left to right reduces the two-dimensional simulation to effective one-dimensional dynamics with random local unitaries and measurements.The algorithm applies only gates in the measurement column’s lightcone, leaving post-measurement bipartite states across row cuts.
  • SEBD mechanism: Long 1-local regions suppress expected entanglement exponentially in r, allowing constant bond dimension with high probability across the sweep.The expected post-measurement entanglement is bounded by 2^−Θ(r), and truncation plus union bounds control failures over all bonds.
  • Provable average-case efficiency: SEBD simulates almost all extended brickwork instances in linear time with constant bond dimension and exponentially small truncation error.Lemma 12 gives success probability at least 1 − 2^−Θ(r), variational-distance error n2^−Θ(r), and runtime Θ(n).
  • Provable average-case efficiency: For r = Θ(log(L)), SEBD achieves inverse-polynomial error for all but an inverse-polynomial fraction of instances; polynomial r yields superpolynomially small error and failure rates.The corollary also gives error and failure fractions of 2^−n^(1−δ) for sufficiently large polynomial extension parameters.

4 Numerical results

Numerical experiments show that SEBD can simulate very large random brickwork instances and that both studied effective one-dimensional dynamics remain consistent with efficient, area-law simulation. The brickwork model is faster because its entanglement and Schmidt spectra decay more rapidly than CHR’s.

  • Simulation performance: A standard laptop simulated typical 409 × 409 brickwork instances in about one minute per sample and 34 × 34 CHR instances in about five minutes.The corresponding per-bond truncation errors were 10^−14 for brickwork and 10^−10 for CHR.
  • Simulation performance: Over 3000 trials found no failed 409 × 409 brickwork simulations, supporting a 0.9 simulable fraction with 95% confidence at variational-distance error at most 0.01.Each sample used truncation error 10^−14 per bond; the statistical guarantee is weaker than the expected true simulable fraction.
  • Scope and outlook: The authors conjecture polynomial dependence on n, 1/ε, and 1/δ for SEBD, while noting that simulations were limited to low depths and small sizes.The relationship between circuit depth, local dimension, statistical-mechanical models, and simulation performance remains for future work.
  • Entanglement evidence: The effective one-dimensional dynamics exhibit area-law entanglement, with entropy saturating rather than growing extensively with sidelength.The same qualitative behavior was observed for some Rényi entropies with α < 1, which is sufficient for efficient MPS descriptions.
  • Entanglement evidence: The CHR entanglement spectrum decays superpolynomially, consistent with λ_i ∼ 2^−Θ(log^2(i)), while brickwork decays too quickly for comparable numerical statistics.The observed CHR spectrum supports polynomial bond dimension in inverse error; brickwork’s faster decay also explains its lower runtime.

5 Mapping random circuits to statistical mechanical models

The paper maps random quantum circuits with Haar-random unitaries and weak measurements to statistical-mechanical models, using quasi-entropies to study output-state entanglement. The mapping links ordered or disordered phases to volume-law or area-law entanglement, with a transition at q_c = 3.249 in the analyzed model.

  • 5 Mapping random circuits to statistical mechanical models: The mapping represents random circuit structure through statistical-mechanical degrees of freedom, with Weingarten and measurement-dependent weights associated with circuit elements.The construction accounts for Haar-random unitaries, measurement operators, outcomes, and auxiliary nodes connected to final circuit outputs.
  • 5 Mapping random circuits to statistical mechanical models: The stat-mechanical calculation naturally produces a quasi-entropy, which serves as a proxy for the expected von Neumann entropy through its relation to the k → 1 limit.The proxy is motivated by the relationship between quasi-entropy and actual expected entropy, including prior random-circuit analyses.
  • 5.2 Mapping applied to 1D circuits with weak measurements: The critical point occurs at q_c = 3.249, so the analyzed model is disordered for q = 2 or 3 and ordered for q ≥4.Only integer q values correspond to valid quantum circuits in this analysis.
  • 5 Mapping random circuits to statistical mechanical models: The disorder-to-order transition is expected to correspond to an area-law-to-volume-law transition in the output circuit’s Rényi-2 entanglement entropy.In the ordered phase, twisted boundary conditions create a domain wall whose free-energy cost grows with the boundary, producing volume-law scaling; the disordered phase supports area-law scaling.
  • 5.2 Mapping applied to 1D circuits with weak measurements: For the associated 1D random-unitary process, quasi-entropy obeys an area law at q = 2 and 3 but a volume law at q = 4.This behavior helps explain numerical observations that SEBD on CHR has area-law average entanglement for q = 2.

6 Evidence for efficiency of algorithms from statistical mechanics

The statistical-mechanical mapping links simulation efficiency to disorder and order in an associated model: disordered phases support efficient SEBD and Patching, while ordered phases indicate inefficiency. Evidence suggests transitions controlled by local dimension and depth, although the mapping is not fully rigorous because quasi-entropy only matches entanglement entropy in an inaccessible limit.

  • 6 Evidence for efficiency of algorithms from statistical mechanics: The mapping offers useful efficiency intuition but not a fully rigorous proof because its quasi-entropy equals average entanglement entropy only in a limit inaccessible to the mapping.The needed area-law justification also technically concerns k-Rényi entropy for 0<k<1.
  • 6.1 Mapping applied to general 2D circuits: The mapping predicts an efficient-to-inefficient transition when local dimension exceeds a critical q_c or circuit depth exceeds a critical d_c.This computational transition is associated with a disorder-to-order transition in the classical statistical-mechanical model.
  • 6.3 Efficiency of Patching algorithm from stat mech: In the disordered phase, quasi-CMI decays with separation, making the output distribution approximately Markov and supporting efficient Patching.The boundary influence is attenuated over the correlation length, yielding a poly(n,q)e^-Θ(l)-Markov structure.
  • 6.3 Efficiency of Patching algorithm from stat mech: In the ordered phase, quasi-CMI is not expected to decay, providing evidence that Patching cannot efficiently sample with small error.The ordered model's global spin-flip contribution prevents the relevant quasi-CMIs from vanishing.
  • 6.4 Depth-3 2D circuits with brickwork architecture: For depth-3 brickwork circuits, the mapped interactions are disordered at q=2 and q=3, while the estimated transition to order occurs near q_c≈6.At q=5 the averaged interaction remains below the square-lattice critical strength, whereas it slightly exceeds it at q=6.
  • 6.4 Depth-3 2D circuits with brickwork architecture: For depth-3 brickwork circuits, the mapping predicts efficient SEBD and Patching at q=2 and q=3, probably also q=4 and q=5, with constant quasi-entropy and exponentially decaying quasi-CMI.These properties are taken as evidence that both algorithms efficiently simulate typical Haar-random circuits in this regime.

A Relation to worst-to-average-case reductions based on truncated Taylor series

The paper examines whether polynomial-interpolation worst-to-average-case hardness applies to its simulation algorithms. It argues that this approach does not establish hardness for Haar-random circuits because the relevant interpolation concerns slightly non-unitary families.

  • A Relation to worst-to-average-case reductions based on truncated Taylor series: The analysis relates SEBD and Patching to a prior worst-to-average-case hardness result based on polynomial interpolation.The comparison concerns computing output probabilities for random circuits.
  • A Relation to worst-to-average-case reductions based on truncated Taylor series: The interpolation argument is insufficient to show that exact output-probability computation or sampling from constant-depth Haar-random circuits is hard with high probability.This remains true despite worst-case hardness of the circuits.
  • A Relation to worst-to-average-case reductions based on truncated Taylor series: The central distinction is that the algorithms exploit unitary lightcone structure, whereas the hardness result applies to circuits that are slightly non-unitary.This mismatch prevents directly transferring the hardness argument to the algorithms’ setting.

Background: truncated Haar-random circuit ensembles and polynomial interpolation

The interpolation construction deforms Haar-random circuits into truncated, generally non-unitary families and uses polynomial evaluations near the Haar point to recover a hard worst-case quantity. Its hardness claim relies on controlling approximation errors across the interpolation.

  • Background: truncated Haar-random circuit ensembles and polynomial interpolation: The construction applies a θ-contracted and K-truncated transformation to each Haar-random gate, producing a circuit family D(C,θ,K).Finite Taylor truncation makes the transformed gates slightly non-unitary.
  • Background: truncated Haar-random circuit ensembles and polynomial interpolation: At θ=0 the ensemble is Haar-random, while at θ=1 it recovers the hard circuit up to truncation corrections.Increasing K improves the approximation to the intended deformation.
  • Background: truncated Haar-random circuit ensembles and polynomial interpolation: For a circuit with m gates, the output probability becomes a polynomial in θ of degree 2mK, with p0(A,1,∞)=p0(C).The polynomial connects random-instance evaluations to the worst-case hard probability.
  • Background: truncated Haar-random circuit ensembles and polynomial interpolation: If an algorithm accurately evaluates the polynomial at 2mK+1 points near θ=0, interpolation and polynomial bounds can transfer that accuracy toward θ=1.The argument uses an interval supplied by Rakhmanov’s result and Paturi’s lemma.
  • Background: truncated Haar-random circuit ensembles and polynomial interpolation: The resulting hardness statement applies to truncated families D(C,θ,K) for sufficiently small θ and sufficiently accurate output-probability computation.The claimed error scale is 2^-poly(n) under standard hardness assumptions.

Limitation of the interpolation argument

The interpolation proof fails when applied directly to truly Haar-random circuits. The failure arises because controlling sampling and truncation errors conflicts with the sensitivity of the high-degree interpolating polynomial.

  • Limitation of the interpolation argument: The interpolation argument establishes hardness for slightly non-unitary ensembles, but does not establish hardness for Haar-random output probabilities.The authors explicitly distinguish the truncated ensembles from the Haar-random distribution.
  • Limitation of the interpolation argument: The required interpolation interval must satisfy ϵ ≤ O(1/m2K) to control errors across all 2mK+1 evaluation points.This constraint follows from the probability that at least one evaluation is erroneous.
  • Limitation of the interpolation argument: Taylor truncation introduces an error bounded by 2^O(nm)/K!, which propagates through interpolation toward the hard quantity.The error bound is combined with Paturi’s lemma.
  • Limitation of the interpolation argument: The resulting interpolation error is no better than 2^O(nm), so the technique cannot prove high-probability hardness for Haar-random output probabilities.This bound diverges as n grows for any scaling of m and K.
  • Limitation of the interpolation argument: Increasing K suppresses truncation error but raises polynomial degree, making interpolation more sensitive to errors.This tradeoff is the intuitive source of the limitation.

Inapplicability to SEBD and Patching

The interpolation limitation is especially relevant to SEBD and Patching because their unitary lightcone approximations do not directly extend to the non-unitary truncated ensembles required by the reduction.

  • Inapplicability to SEBD and Patching: The interpolation argument applies to distributions close to Haar-random circuits but does not directly establish hardness for truly Haar-random distributions.The distinction is between slightly non-unitary truncated families and unitary Haar-random circuits.
  • Inapplicability to SEBD and Patching: It is not known whether an algorithm that simulates Haar-random circuits exactly could also simulate truncated Haar-random families with the precision interpolation requires.The paper presents this as an open possibility rather than a resolved equivalence.
  • Inapplicability to SEBD and Patching: SEBD and Patching cannot be straightforwardly used to simulate the truncated families at the required precision.For non-unitary gates, the general-purpose contraction cost is 2^O(d√n) on a square grid.
  • Inapplicability to SEBD and Patching: The issue arises because the algorithms ignore gates outside the current lightcone, effectively treating them as unitary.That approximation is compatible with unitary circuits but introduces error for truncated non-unitary circuits.
  • Inapplicability to SEBD and Patching: The resulting error, bounded by 2^O(nm)/K!, already exceeds the tolerance needed for the degree-2mK interpolation.Therefore the reduction cannot show that SEBD or Patching exactly simulate worst-case-hard shallow Haar-random circuits with high probability.

B Deferred proofs

The deferred proofs establish error control for sequential tensor-network simulation and analyze Schmidt-spectrum decay in the toy unitary-and-measurement process. They also formalize the effective dynamics produced by measuring columns of the 2D circuit.

  • Sequential simulation: The MPS approximation error is bounded by the sum of per-iteration discarded Schmidt-value contributions, using contractivity of quantum channels.The proof relates each truncation’s 1-norm error to the squared discarded singular values and then sums these bounds recursively.
  • Sequential simulation: Sequentially applying column maps produces the exact output distribution before truncation, while truncation errors accumulate through the resulting classical-quantum states.The construction defines ρ_t through maps N_t, with the final state ρ_{L2+1} representing the circuit’s output distribution.
  • Toy-model spectrum: The toy model’s Schmidt values decay superpolynomially with their index, and this decay holds with probability at least 1−δ after sufficient iterations.Lemma 7 derives the scaling from sector-wise coefficient bounds and the relation between sector index and Schmidt index.
  • Toy-model spectrum: After truncation to error ϵ, the toy-model state has a bounded Schmidt rank with probability at least 1−δ, establishing a route to efficient MPS approximation.The rank bound follows by controlling the tail of the Schmidt spectrum after discarding coefficients beyond a suitable index.
  • Effective 1D dynamics: The effective one-dimensional process alternates Haar-random two-qubit layers with computational-basis measurements on contiguous regions, producing post-measurement states on the unmeasured qubits.This setup is the effective dynamics used to connect the 2D circuit simulation problem to MPS truncation analysis.

C Justification of stat mech mapping

The appendix derives the statistical-mechanical representation by applying Haar integration to replicated circuit tensors. Permutation variables label the resulting configurations, while local weights and closed-loop factors produce the partition-function expression.

  • Haar integration: Haar integration replaces each random unitary integral with a weighted sum over pairs of permutations in the symmetric group S_k.The permutations encode pairings among replicated U and U† indices, and Weingarten functions supply the corresponding weights.
  • Haar integration: Applying the formula to every gate converts the replicated circuit tensor network into a weighted sum of networks labeled by local permutation choices and measurement configurations.Each term is organized by the choices associated with every unitary and its measurement operators.
  • Tensor-network decomposition: Shared qudits between successive gates force permutation pairings that close into disjoint loops, allowing each component of a network term to be evaluated independently.These loop factors depend only on neighboring permutation variables and generate the local statistical-mechanical interactions.
  • Statistical-mechanical weights: The resulting partition function uses local factors from Weingarten weights, loop evaluations, and expectations over the measurement distributions.The appendix identifies these contributions with the weights in Eqs. (38), (39), and (40).
  • Boundary conditions: The output trace and the region-A permutation are represented by identity or k-cycle boundary conditions, implemented through auxiliary nodes where needed.The trace closes output indices without permutation, while the k-cycle acts only on replicated indices in region A.
Loading 2001.00021v2…