Strong Simulation of 1D Quantum Circuits via Reduced Transition Matrices

Technical Summary: Strong Simulation of 1D Quantum Circuits via Reduced Transition Matrices

Problem Statement
The simulation of non-equilibrium quantum many-body systems is fundamentally limited by the rapid growth of spatial entanglement, which renders standard tensor-network methods (such as TEBD, tDMRG, and TDVP) inefficient for chaotic unitary circuits. While these methods restrict dynamics to low-complexity manifolds, they eventually fail as entanglement grows extensively.

This paper addresses a more targeted computational task: the approximate strong simulation of a specified output probability $p(x|y) = |\langle x|U(T)|y\rangle|^2$ for a 1D chaotic brick-wall circuit, given a fixed relative precision $\epsilon_p$ (or $\epsilon_A$ for the amplitude). This task differs from sampling the full output distribution, which is conjectured to be classically hard. While exact evaluation of specific probabilities is generally #P-hard, the authors note that established hardness results typically apply to regimes where relative errors vanish with system size. The paper investigates the computational complexity of achieving a fixed finite relative precision, a regime where hardness has not been rigorously established.

Methodology: The Sweeping RTM Algorithm
The authors propose a transverse tensor-network contraction strategy based on Reduced Transition Matrices (RTMs). Instead of contracting the space-time tensor network along the time direction (which leads to exponential bond dimension growth due to spatial entanglement) or approximating left and right temporal boundary states independently, the algorithm targets the overlap between these boundaries directly.

1. Transverse Formulation: The circuit amplitude is viewed as the overlap $\langle L|R\rangle$ of left and right temporal boundary states. The transition matrix is defined as $T = |R\rangle\langle L| / \langle L|R\rangle$.
2. RTM Compression: The algorithm utilizes the singular-value decomposition (SVD) of the reduced transition matrix $T_A = \text{Tr}_{\bar{A}} T$ across a temporal bipartition. The singular vectors of $T_A$ identify the directions most relevant to the overlap, rather than the entanglement structure of the individual boundaries.
3. Sweeping Procedure: The algorithm constructs the left and right boundary states as temporal Matrix Product States (tMPS). It performs alternating left-to-right and right-to-left sweeps across the spatial direction. At each step, the tMPS bonds are truncated based on the singular spectrum of the local RTM to preserve the overlap, rather than the individual states.
4. Convergence Diagnostics: The method employs internal consistency checks, monitoring the spread of amplitude estimates across different spatial cuts ($\Delta_{cut}$), between sweeps ($\Delta_{sweep}$), and between different bond dimensions ($\Delta_{\chi}$). Convergence is declared when these diagnostics fall below a prescribed tolerance $\epsilon_A$.

Key Results
The authors benchmarked the algorithm on three families of two-qubit gates: a deterministic chaotic kicked-Ising circuit, an exchange-symmetric random ensemble, and a random Haar ensemble.

• Subexponential Bond Dimension Growth: For chaotic 1D circuits at fixed relative precision, numerical evidence indicates that the bond dimension $\chi$ required for stable estimates grows subexponentially over the accessible time window. This contrasts with the exponential growth required for faithful representation of the full state or for standard transverse TEBD.
• Spectral Properties: The singular spectra of the RTMs exhibit approximately exponential tails ($\lambda_n \sim e^{-n/F}$). The characteristic decay scale $F(T)$ grows as a power law $T^\alpha$. This spectral structure suggests that the RTM SVD entropy $S_{RTM}$ grows logarithmically ($S_{RTM} \sim \alpha \log T$) in the infinite-size, translationally invariant limit, though finite-size systems show deviations due to excited states.
• Accuracy Validation:
  • For small systems ($N=20$), the algorithm's results match exact forward evolution within the prescribed tolerance.
  • For larger systems ($N=60$), where exact evolution is infeasible, the algorithm reproduces the statistical properties of the output probabilities, specifically converging to the Porter–Thomas prediction for the log moment of the probabilities.
  • The method maintains stability across different tolerances ($\epsilon_A = 0.1, 0.5, 0.8$), with the relative discrepancy between amplitudes computed at different thresholds remaining bounded.

Significance and Applications
The paper claims that this approach opens a direct route to classical probability queries for chaotic quantum circuits, provided the simulation time remains within the subexponential scaling window. The authors identify three specific applications:

1. Benchmarking (XEB): The method enables the classical evaluation of Linear Cross-Entropy Benchmarking (XEB) for large quantum devices by computing ideal probabilities for sampled strings without storing the full output state. The relative error in the XEB estimator is bounded by the relative error of the probability queries.
2. Shadow-Overlap Certification: The algorithm can supply the complex amplitude queries required for the shadow-overlap certification protocol, allowing for fidelity bounds on quantum devices with errors controlled by the amplitude accuracy.
3. Learning Tasks: It facilitates likelihood-based learning of parametrized quantum circuit models by evaluating the empirical negative log-likelihood, even when individual probabilities are exponentially small, provided the contractions remain tractable.

Limitations and Outlook
The authors emphasize that their findings are numerical and heuristic. They do not rigorously establish an asymptotic complexity bound (i.e., whether the growth is strictly polynomial or subexponential in the thermodynamic limit). The internal convergence checks do not constitute rigorous error bounds. Furthermore, the current work is restricted to 1D circuits; extending the strategy to two spatial dimensions (using PEPS) is noted as a nontrivial challenge due to the increased cost of contracting and compressing 2D temporal boundaries. Future work is required to establish rigorous bounds and develop a variational formulation for the overlap problem.