Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2610.02082

Strong Simulation of 1D Quantum Circuits via Reduced Transition Matrices

Matilde Grassi, Stefano Carignano, Luca Tagliacozzo, Jacopo De Nardis

quant-phcond-mat.stat-mechSubmitted Oct 1, 2026• Announced Oct 2, 2026• 0 citations
arXivHTMLPDF

Abstract

Tensor networks are powerful tools for simulating quantum many-body systems, but the growth of spatial entanglement severely limits the direct evolution of pure states under chaotic unitary circuits. Here we consider a more targeted task: the approximate strong simulation of a specified output probability of a 1D chaotic brick-wall circuit at finite relative precision. Given input and output bit strings $\by$ and $\bx$, we evaluate $p(\bx|\by)=|\bra{\bx}U(T)\ket{\by}|^2$ using the Sweeping RTM algorithm, a transverse tensor-network contraction based on reduced transition matrices (RTMs). The algorithm compresses the left and right temporal boundary states jointly, seeking an output probability that converges across spatial cuts and as the bond dimension is increased. For chaotic one-dimensional brick-wall circuits at a fixed relative target precision, we find numerical evidence that the bond dimension required to obtain stable estimates grows subexponentially over the accessible time window. Our findings open a direct route to classical probability queries for chaotic quantum circuits, with potential applications to benchmarking and learning tasks.

AI Summary

The paper studies approximate strong simulation of a specified output probability $p(\mathbf{x}|\mathbf{y})=|\langle\mathbf{x}|U(T)|\mathbf{y}\rangle|^2$ of a chaotic one-dimensional brick-wall circuit at fixed relative precision, rather than sampling its output distribution or representing the full evolved state. The proposed Sweeping RTM algorithm contracts the circuit tensor network transversely. It jointly compresses left and right temporal matrix-product states using singular subspaces of their reduced transition matrices, targeting their overlap rather than either boundary separately. Alternating spatial sweeps and increasing bond dimension are checked for agreement across cuts, successive sweeps, and bond dimensions. Numerical tests cover a deterministic kicked-Ising circuit, exchange-symmetric random gates, and Haar-random gates. For $N=60$ and amplitude tolerances $\epsilon_{\mathcal A}=0.8,0.5,0.1$, the required bond dimensions show growth compatible with subexponential behavior over the accessible time window; Haar circuits are substantially harder. Comparisons with exact evolution at $N=20$ find mean relative amplitude errors below the chosen tolerances. Larger-system checks use cross-tolerance agreement and convergence of mean log probabilities toward Haar predictions. Retained RTM spectra exhibit approximately exponential tails, although generic finite-chain entropy data do not establish logarithmic growth. The evidence uses one circuit realization per family and up to 40 input-output pairs. No asymptotic complexity bound or rigorous relative-error guarantee is established, and sweep convergence is not proved. The paper discusses conditional applications to cross-entropy benchmarking, phase-sensitive fidelity certification, and likelihood-based learning; extending the method to two dimensions remains nontrivial.

Little sign of AI-generated textMissing comparison

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
comments welcome

Related papers

Complexity of tensor network simulation for noisy quantum circuits

Yuguo Shao, Zishuo Zhao, Song Cheng +1 more

We aim to rigorously address how local noise affects classical simulability of quantum dynamics benchmarked by tensor-network methods. Using operator entanglement entropy (OEE), we prove the following: (1) For single-qubit depolarizing noise on arbitrary circuits, tensor networks with $\mathrm{poly}(n)$ bond dimension suffice for fixed absolute Hilbert-Schmidt error after $\order{1}$ depth, while relative error demands $\order{\log n}$ depth; and this bound is optimal. (2) For single-qubit depolarizing noise on 1D local circuits, the existence of whole-trajectory error-bounded matrix product operator (MPO) of $\mathrm{poly}(n)$ bond dimension at all depths. (3) For general single-qubit noise in 1D brickwall circuits, random two-design gates with contraction coefficient $c<1/3$ yield an $\order{1}$ OEE plateau with probability $1-Te^{-Ω(n)}$, while arbitrary gates with $c<1/48$ give $\order{\log n}$ OEE in the worst case. (4) In higher dimensions, these bounds yield uniform-in-depth $\mathrm{poly}(n)$ average boundary-bond dimensions for projected entangled pair operators~(PEPO) across every cut -- under depolarizing noise at either absolute or relative accuracy, and under general noise with strong contraction at absolute accuracy. Our results establish a rigorous connection between certain noise models, circuit types, and their classical simulability.

cond-mat.str-elCross-listedarXiv:2606.00474•Jun 2, 2026•2 citations

Approximate strong simulation of one-dimensional quantum dynamics via reduced transition matrix

Matilde Grassi

Tensor networks enable the classical simulation of quantum many-body systems by restricting the description to the weakly entangled region of the Hilbert space. For the real-time dynamics of one-dimensional chains, the standard Time-Evolving Block Decimation algorithm compresses the evolved state as a matrix product state, whose bond dimension grows exponentially in time after a global quench (the entanglement barrier). This thesis addresses the approximate strong simulation of the dynamics: the computation of a single amplitude between two product states, to a prescribed relative precision. The spatio-temporal network is contracted along the spatial direction rather than in time (transverse contraction), and the amplitude becomes the overlap of a left and a right temporal matrix product state. Instead of truncating each half on its reduced density matrix, we truncate on the reduced transition matrix (RTM), built from both halves at once, so as to retain the directions relevant to their overlap. The resulting self-consistency problem is solved by sweeping the cut across the system until the amplitude converges. The algorithm, based on recent proposals and modified in its convergence criteria and bond-dimension schedule, was implemented from scratch in Julia and tested on kicked Ising and random brickwork circuits, and on the Trotterised mixed-field Ising chain in the gapped, critical and chaotic regimes. For circuits, we find numerical evidence that the required bond dimension grows subexponentially over the accessible time window. We relate this behaviour to the exponential decay of the RTM singular values: the cost is set by the tail of the spectrum, while the RTM entropy serves as a diagnostic of its structure. For Hamiltonian evolution, the accessible window is too short to determine the growth law. This method evaluates single probabilities without representing the evolved state, with potential applications to cross-entropy benchmarking.

•Oct 29, 2026•0 citations

Efficient tensor-network simulations of weakly-measured quantum circuits

Darren Pereira, Leonardo Banchi

We present a tensor-network-based method for simulating a weakly-measured quantum circuit. In particular, we use a Markov chain to efficiently sample measurements and contract the tensor network, propagating their effect forward along the spatial direction. Applications of our algorithm include validating quantum computers (capable of mid-circuit measurements) in regimes of easy classical simulability, and studying generative-machine-learning applications, where sampling from complex stochastic processes is the main task. As a demonstration of our algorithm, we consider a (1+1)-dimensional brickwall circuit of Haar-random unitaries, interspersed with generalized single-qubit measurements of variable strength. We simulate the dynamics for tens to hundreds of qubits if the circuit exhibits area-law entanglement (under strong measurements), and tens of qubits if it exhibits volume-law entanglement (under weak measurements). We observe signatures of a measurement-induced phase transition between the two regimes as a function of measurement strength.

arXiv:2510.07211•Oct 8, 2025•1 citation

Truncated hybrid tensor networks for distributed quantum simulation

Yong Liu, Guangyao Huang, Weixu Shi +4 more

Simulation of quantum many-body systems is a principal application of quantum computing, but available devices remain limited by the number of qubits and cannot accommodate systems of the desired size. One approach is to host a large evolution across several modest distributed systems that exchange classical information alone. Current protocols such as circuit knitting incur a quasi-probability sampling cost that grows exponentially with the number of remote gates across the cut, even when physical correlations across the cut are actually bounded. In this work, we present a truncated hybrid tensor network (THTN) framework in which a remote two-body gate is applied as a sum of local unitaries on the subsystems, linked by a classical connecting tensor, and an interface truncation retains Schmidt modes across the cut. Remote gates between the same subsystems can be merged on one connector, so non-one-dimensional models, such as layered partitions with strong intra-layer and weaker interlayer couplings, may be cast onto a one-dimensional cut. The retained non-negative Schmidt coefficients also define a sampling rule for local observables. We validate this distributed protocol by classical simulation against time-evolving block decimation (TEBD) at the same bond dimension. The truncated dynamics track the TEBD references on chains and ladders, with the clearest gain on a layered model.

quant-pharXiv:2609.16520•Sep 16, 2026•0 citations

Quantum-inspired classical simulation through randomized time evolution

Fredrik Hasselgren, Bálint Koczor

Tensor-network simulations of quantum many-body dynamics are fundamentally limited by entanglement build-up, which leads to exponentially growing computational costs. Furthermore, these classical simulation algorithms are inherently sequential as typically a tensor network representation of the quantum state is updated incrementally at each time step. We build on recently introduced randomized quantum algorithms for time evolution (TE-PAI), and adapt them to the classical simulation context with the purpose of enabling massive parallelisation. Our MPS TE-PAI approach achieves exact time evolution on average (unbiased estimator) and proceeds by representing an ensemble of randomized shallow Trotter-variant circuits as tensor networks. As each circuit instance yields a deterministic quantum state (or observable expecation value), the only source of randomness is the sampling of circuit variants; the absence of shot noise therefore yields a reduced estimator variance relative to quantum hardware implementations of TE-PAI. We simulate representative disordered one-dimensional spin-ring Hamiltonians, and numerically observe reductions in the per-sample gate-count by a factor of up to $10^3$ relative to Trotterized MPS evolution, yielding orders of magnitude reduction in the time-to-solution under realistic levels of parallelisation. Finally, we numerically observe that MPS TE-PAI is substantially more robust against severe bond-dimension truncation than product formulas, potentially making it useful for the simulation of strongly correlated systems where truncation is necessary in practice. We also demonstrate that the approach can be used naturally in combination with existing time evolution algorithms, effectively extending their time depth via parallelisation.

quant-pharXiv:2604.13144•Apr 15, 2026•2 citations

Low Rank Structure of the Reduced Transition Matrix

Cathy Li, Bruno Bertini, Katja Klobas +1 more

The influence-matrix formalism provides an alternative route to the classical simulation of quantum dynamics. Because influence matrices retain information only about the effective bath seen by local observables, they are expected to be easier to simulate than the full wavefunction. Recent work, however, has shown that they carry strong temporal correlations even in maximally chaotic systems, making them difficult to represent efficiently. Here we show that the reduced transition matrix, a suitable combination of influence matrices that directly determines local expectation values, can nevertheless be efficiently approximated. We first show that the truncation error is controlled by its singular-value spectrum, which naturally motivates a low-rank approximation. We then prove that, for chaotic dual-unitary circuits, the associated entropy grows at most logarithmically in time. Our conclusions follow from exact results for random dual-unitary circuits and are further supported by numerical results for fixed instances of both dual-unitary and random circuits.

quant-pharXiv:2605.12665•May 14, 2026•3 citations
Tensor networks are powerful tools for simulating quantum many-body systems, but the growth of spatial entanglement severely limits the direct evolution of pure states under chaotic unitary circuits. Here we consider a more targeted task: the approximate strong simulation of a specified output probability of a 1D chaotic brick-wall circuit at finite relative precision. Given input and output bit strings \by\by\by and \bx\bx\bx, we evaluate p(\bx∣\by)=∣⟨\bx∣U(T)∣\by⟩∣2p(\bx|\by)=|\bra{\bx}U(T)\ket{\by}|^2p(\bx∣\by)=∣⟨\bx∣U(T)∣\by⟩∣2 using the Sweeping RTM algorithm, a transverse tensor-network contraction based on reduced transition matrices (RTMs). The algorithm compresses the left and right temporal boundary states jointly, seeking an output probability that converges across spatial cuts and as the bond dimension is increased. For chaotic one-dimensional brick-wall circuits at a fixed relative target precision, we find numerical evidence that the bond dimension required to obtain stable estimates grows subexponentially over the accessible time window. Our findings open a direct route to classical probability queries for chaotic quantum circuits, with potential applications to benchmarking and learning tasks.
The paper studies approximate strong simulation of a specified output probability p(x∣y)=∣⟨x∣U(T)∣y⟩∣2p(\mathbf{x}|\mathbf{y})=|\langle\mathbf{x}|U(T)|\mathbf{y}\rangle|^2p(x∣y)=∣⟨x∣U(T)∣y⟩∣2 of a chaotic one-dimensional brick-wall circuit at fixed relative precision, rather than sampling its output distribution or representing the full evolved state.
The proposed Sweeping RTM algorithm contracts the circuit tensor network transversely. It jointly compresses left and right temporal matrix-product states using singular subspaces of their reduced transition matrices, targeting their overlap rather than either boundary separately. Alternating spatial sweeps and increasing bond dimension are checked for agreement across cuts, successive sweeps, and bond dimensions.
Numerical tests cover a deterministic kicked-Ising circuit, exchange-symmetric random gates, and Haar-random gates. For N=60N=60N=60 and amplitude tolerances ϵA=0.8,0.5,0.1\epsilon_{\mathcal A}=0.8,0.5,0.1ϵA​=0.8,0.5,0.1, the required bond dimensions show growth compatible with subexponential behavior over the accessible time window; Haar circuits are substantially harder. Comparisons with exact evolution at N=20N=20N=20 find mean relative amplitude errors below the chosen tolerances. Larger-system checks use cross-tolerance agreement and convergence of mean log probabilities toward Haar predictions. Retained RTM spectra exhibit approximately exponential tails, although generic finite-chain entropy data do not establish logarithmic growth.
The evidence uses one circuit realization per family and up to 40 input-output pairs. No asymptotic complexity bound or rigorous relative-error guarantee is established, and sweep convergence is not proved. The paper discusses conditional applications to cross-entropy benchmarking, phase-sensitive fidelity certification, and likelihood-based learning; extending the method to two dimensions remains nontrivial.
We aim to rigorously address how local noise affects classical simulability of quantum dynamics benchmarked by tensor-network methods. Using operator entanglement entropy (OEE), we prove the following: (1) For single-qubit depolarizing noise on arbitrary circuits, tensor networks with poly(n)\mathrm{poly}(n)poly(n) bond dimension suffice for fixed absolute Hilbert-Schmidt error after $\order{1}$ depth, while relative error demands $\order{\log n}$ depth; and this bound is optimal. (2) For single-qubit depolarizing noise on 1D local circuits, the existence of whole-trajectory error-bounded matrix product operator (MPO) of poly(n)\mathrm{poly}(n)poly(n) bond dimension at all depths. (3) For general single-qubit noise in 1D brickwall circuits, random two-design gates with contraction coefficient c<1/3c<1/3c<1/3 yield an $\order{1}$ OEE plateau with probability 1−Te−Ω(n)1-Te^{-Ω(n)}1−Te−Ω(n), while arbitrary gates with c<1/48c<1/48c<1/48 give $\order{\log n}$ OEE in the worst case. (4) In higher dimensions, these bounds yield uniform-in-depth poly(n)\mathrm{poly}(n)poly(n) average boundary-bond dimensions for projected entangled pair operators~(PEPO) across every cut -- under depolarizing noise at either absolute or relative accuracy, and under general noise with strong contraction at absolute accuracy. Our results establish a rigorous connection between certain noise models, circuit types, and their classical simulability.
Tensor networks enable the classical simulation of quantum many-body systems by restricting the description to the weakly entangled region of the Hilbert space. For the real-time dynamics of one-dimensional chains, the standard Time-Evolving Block Decimation algorithm compresses the evolved state as a matrix product state, whose bond dimension grows exponentially in time after a global quench (the entanglement barrier). This thesis addresses the approximate strong simulation of the dynamics: the computation of a single amplitude between two product states, to a prescribed relative precision. The spatio-temporal network is contracted along the spatial direction rather than in time (transverse contraction), and the amplitude becomes the overlap of a left and a right temporal matrix product state. Instead of truncating each half on its reduced density matrix, we truncate on the reduced transition matrix (RTM), built from both halves at once, so as to retain the directions relevant to their overlap. The resulting self-consistency problem is solved by sweeping the cut across the system until the amplitude converges. The algorithm, based on recent proposals and modified in its convergence criteria and bond-dimension schedule, was implemented from scratch in Julia and tested on kicked Ising and random brickwork circuits, and on the Trotterised mixed-field Ising chain in the gapped, critical and chaotic regimes. For circuits, we find numerical evidence that the required bond dimension grows subexponentially over the accessible time window. We relate this behaviour to the exponential decay of the RTM singular values: the cost is set by the tail of the spectrum, while the RTM entropy serves as a diagnostic of its structure. For Hamiltonian evolution, the accessible window is too short to determine the growth law. This method evaluates single probabilities without representing the evolved state, with potential applications to cross-entropy benchmarking.
We present a tensor-network-based method for simulating a weakly-measured quantum circuit. In particular, we use a Markov chain to efficiently sample measurements and contract the tensor network, propagating their effect forward along the spatial direction. Applications of our algorithm include validating quantum computers (capable of mid-circuit measurements) in regimes of easy classical simulability, and studying generative-machine-learning applications, where sampling from complex stochastic processes is the main task. As a demonstration of our algorithm, we consider a (1+1)-dimensional brickwall circuit of Haar-random unitaries, interspersed with generalized single-qubit measurements of variable strength. We simulate the dynamics for tens to hundreds of qubits if the circuit exhibits area-law entanglement (under strong measurements), and tens of qubits if it exhibits volume-law entanglement (under weak measurements). We observe signatures of a measurement-induced phase transition between the two regimes as a function of measurement strength.
Simulation of quantum many-body systems is a principal application of quantum computing, but available devices remain limited by the number of qubits and cannot accommodate systems of the desired size. One approach is to host a large evolution across several modest distributed systems that exchange classical information alone. Current protocols such as circuit knitting incur a quasi-probability sampling cost that grows exponentially with the number of remote gates across the cut, even when physical correlations across the cut are actually bounded. In this work, we present a truncated hybrid tensor network (THTN) framework in which a remote two-body gate is applied as a sum of local unitaries on the subsystems, linked by a classical connecting tensor, and an interface truncation retains Schmidt modes across the cut. Remote gates between the same subsystems can be merged on one connector, so non-one-dimensional models, such as layered partitions with strong intra-layer and weaker interlayer couplings, may be cast onto a one-dimensional cut. The retained non-negative Schmidt coefficients also define a sampling rule for local observables. We validate this distributed protocol by classical simulation against time-evolving block decimation (TEBD) at the same bond dimension. The truncated dynamics track the TEBD references on chains and ladders, with the clearest gain on a layered model.
Tensor-network simulations of quantum many-body dynamics are fundamentally limited by entanglement build-up, which leads to exponentially growing computational costs. Furthermore, these classical simulation algorithms are inherently sequential as typically a tensor network representation of the quantum state is updated incrementally at each time step. We build on recently introduced randomized quantum algorithms for time evolution (TE-PAI), and adapt them to the classical simulation context with the purpose of enabling massive parallelisation. Our MPS TE-PAI approach achieves exact time evolution on average (unbiased estimator) and proceeds by representing an ensemble of randomized shallow Trotter-variant circuits as tensor networks. As each circuit instance yields a deterministic quantum state (or observable expecation value), the only source of randomness is the sampling of circuit variants; the absence of shot noise therefore yields a reduced estimator variance relative to quantum hardware implementations of TE-PAI. We simulate representative disordered one-dimensional spin-ring Hamiltonians, and numerically observe reductions in the per-sample gate-count by a factor of up to 10310^3103 relative to Trotterized MPS evolution, yielding orders of magnitude reduction in the time-to-solution under realistic levels of parallelisation. Finally, we numerically observe that MPS TE-PAI is substantially more robust against severe bond-dimension truncation than product formulas, potentially making it useful for the simulation of strongly correlated systems where truncation is necessary in practice. We also demonstrate that the approach can be used naturally in combination with existing time evolution algorithms, effectively extending their time depth via parallelisation.
The influence-matrix formalism provides an alternative route to the classical simulation of quantum dynamics. Because influence matrices retain information only about the effective bath seen by local observables, they are expected to be easier to simulate than the full wavefunction. Recent work, however, has shown that they carry strong temporal correlations even in maximally chaotic systems, making them difficult to represent efficiently. Here we show that the reduced transition matrix, a suitable combination of influence matrices that directly determines local expectation values, can nevertheless be efficiently approximated. We first show that the truncation error is controlled by its singular-value spectrum, which naturally motivates a low-rank approximation. We then prove that, for chaotic dual-unitary circuits, the associated entropy grows at most logarithmically in time. Our conclusions follow from exact results for random dual-unitary circuits and are further supported by numerical results for fixed instances of both dual-unitary and random circuits.