Source-linked AI summary
Query-optimal quantum simulation of Lindblad evolution
Chunhao Wang, Christopher Ye
TL;DR
General Lindblad simulation had an additive query lower bound but only multiplicative upper bounds were known, leaving open whether the gap was necessary. The paper uses transducers and reuse-circuit combinations to suppress catalyst-removal error. It achieves optimal additive query complexity in the block-encoding model and nearly optimal gate complexity.
Problem
Whether general Lindblad simulation could attain the additive query lower bound remained open, while known general algorithms had multiplicative dependence on time and precision.
Source: §1 · p. 3Method
The algorithm composes evolution steps with transducers and combines reuse circuits of different lengths to reduce catalyst-removal error.
Source: §1 · pp. 4–5Results
O(τ + polylog(τ/ϵ)) queries to each block encoding simulate e^Lt to diamond-norm error ϵ, with optimal worst-case dependence on time and precision.
Source: §1 · pp. 3–4Takeaways & Limitations
The multiplicative dependence of previous general algorithms is not intrinsic to Lindblad simulation in the block-encoding model.
Source: §1 · p. 4The stated access model assumes block encodings of the Hamiltonian and each jump operator, with controlled access to the oracles and their adjoints.
Source: §1 · p. 3
Abstract
from arXiv · showhide
For the problem of simulating Lindblad evolution for time $t$ to precision $\epsilon$, Hamiltonian simulation provides an additive query lower bound, informally, $\Omega(t + \mathrm{polylog}(1/\epsilon))$. However, the best previously known algorithms for general Lindblad simulation achieve a multiplicative upper bound, informally, $\mathcal{O}(t\,\mathrm{polylog}(1/\epsilon))$, in query complexity. It has remained open whether this multiplicative dependence is necessary. In this paper, we close the gap in query complexity by giving an algorithm with optimal additive dependence on evolution time and precision in the block-encoding model. Our approach uses the transducer framework to reduce the query cost of composing first-order approximations to the evolution channel, together with linear combinations of reuse circuits of different lengths to suppress catalyst-removal error. We further achieve nearly optimal gate complexity in evolution time and precision through history compression and an efficient implementation of the query-free part of the transducer using operation reordering and linear combinations of unitaries, while preserving the optimal query complexity.
1 Introduction
The paper closes the gap between the additive lower bound and previously multiplicative query complexity for general Lindblad simulation. It uses transducers and reuse-circuit combinations to obtain optimal additive query complexity, with a nearly optimal gate implementation.
1 Introduction
- Hamiltonian simulation gives an additive query lower bound, but whether general Lindblad simulation could match it remained open despite multiplicative bounds and restricted additive results.Earlier additive results imposed restrictions on jump operators or left Hamiltonian-query complexity multiplicative.Source: §1 · p. 3
- The algorithm achieves optimal worst-case additive dependence on evolution time and precision for general Lindblad simulation in the block-encoding model.Its query bound applies to Hamiltonian and jump-operator oracles without requiring unitary jump operators or a state-independent total jump rate.Source: §1 · pp. 3–4
- Transducers compose evolution steps by keeping catalysts in separate private sectors, allowing oracle queries to be collected while query-free operations advance the public state.This separates the number of evolution steps from the query count and controls error across the evolution.Source: §1 · p. 4
- The local dissipative transducer implements a Stinespring isometry for an exactly trace-preserving channel with local error O(δ^2) and catalyst squared norm O(δ).Distinct jump and no-jump output branches encode the channel’s Kraus operators.Source: §1 · p. 4
- Composing local dissipative and Hamiltonian steps collects oracle calls into a constant number of controlled-query layers, although query-free rotations still grow with the step count.The first-order discretization error is O(τ^2/r), while the global catalyst map has squared norm O(τ).Source: §1 · pp. 4–5
- Reuse circuits distribute the public input across branches to reduce catalyst requirements, while an LCU over different reuse lengths cancels catalyst-removal errors.One round of oblivious amplitude amplification yields the simulation channel; discretization error is controlled separately by choosing enough steps.Source: §1 · p. 5
- For dissipative evolution, the LCU error analysis restricts attention to valid chronological time-and-history labels, yielding factorial decay with polynomial degree and an additive query bound.Choosing degree q sufficiently large relative to 1 + τ makes catalyst-removal error small, using O(q) queries to each oracle.Source: §1 · p. 5
- Reordering jump-producing rotations, implementing no-jump suffixes by LCU, and compressing histories gives nearly optimal gate complexity; the algorithm also extends to time-dependent Lindbladians.The history can be compressed because the maximum number of jumps is bounded by the reuse length.Source: §1 · pp. 4–5
2 Preliminaries
The preliminaries define the operator and channel norms used to measure approximation, introduce a first-order local map for dissipative evolution, and set up transducers and reuse circuits for composing that map.
2.1 Notation
- The diamond norm measures channel distance through distinguishability, while block encodings specify the operator access model used in the paper.The section also fixes spectral and trace norm notation and defines block encodings of operators.Source: §2.1 · p. 6
2.2 The infinitesimal approximation map
- The infinitesimal approximation map gives a first-order accurate local channel for dissipative evolution, extended to multiple jump operators with a stacked Kraus-operator construction.The local time step is restricted to 0 ≤ δ ≤ 1/2.Source: §2.2 · pp. 6, 8
2.3 Transducers
- Input-restricted canonical transducers implement target isometries with a catalyst, while reuse circuits and LCU combine different circuit lengths to reduce catalyst-removal error.The reuse construction omits the scaled catalyst, and the LCU construction combines reuse block encodings of different lengths.Source: §2.3 · pp. 9–11
3 Simulating a Single Jump Operator
This section develops a transducer construction for simulating dissipative evolution with a single jump operator, progressing from a first-order local step to a composed global simulation. It bounds private-block error and uses an LCU over reuse blocks to obtain a simulation channel, establishing the construction’s query and gate costs.
3 Simulating a Single Jump Operator
- Theorem 9 establishes a simulation channel using controlled access to the jump-operator block encoding and its adjoint.The supplied theorem passages do not include the channel’s error guarantee or query count.Source: §3 · p. 12
3.1 Local Transducer
- The local transducer implements a Stinespring isometry whose induced channel approximates dissipative evolution to first order in the time step.Its two public branches represent the no-jump and jump outcomes, with a catalyst used in the construction.Source: §3.1 · pp. 12–13
3.2 Global Transducer
- Composing r local transducers records successive jump outcomes in a history register and yields a Stinespring isometry for the r-step channel.The global construction combines the oracle blocks into a single query by commuting blocks associated with distinct time steps.Source: §3.2 · pp. 17–19
3.3 Block Structure of the Valid Private-to-Private Map of the Global Transducer
- The valid private space is invariant under the composed private-to-private map, whose off-diagonal blocks encode chronological paths through public states.The analysis restricts to history blocks consistent with chronological evolution, excluding a norm-one public-to-private jump path that cannot occur from a fresh history register.Source: §3.3 · pp. 19–21
3.4 Factorial Decay
- The factorial-decay analysis bounds norms of algebraic words containing fixed numbers of ΔR and ΔJ factors using time-history block paths.The path analysis distinguishes row and column sums because output prefixes fix jump departure times, whereas input prefixes do not specify subsequent jumps.Source: §3.4 · pp. 21–22
- An error-cancellation polynomial annihilates the ideal transition operator and yields factorial decay of the private-block error under the proposition’s conditions.The proof uses the polynomial’s annihilation property so surviving terms contain transition factors, which are bounded using the earlier transition estimates.Source: §3.4 · p. 23
3.5 LCU on reuse blocks
- An LCU over reuse blocks followed by one round of oblivious amplitude amplification implements the simulation channel, using at most 30q transducer calls.Each LCU invocation uses at most 10q calls to the one-query transducer or its inverse; the amplification circuit uses at most 30q transducer calls.Source: §3.5 · pp. 24–25
3.6 Proof of Theorem 9
- The construction uses at most 60q queries to the original oracle or its inverse and O(qr) local rotations and history swaps for direct query-free work.Each global-transducer application uses one time-controlled query, and the reuse construction, LCU, and amplification use at most 30q such applications.Source: §3.6 · p. 26
4 The main theorem
The main theorem gives a Lindblad simulation channel with query complexity expressed as O(c(τ,ϵ)) and an implementation with additional gates whose cost includes block-encoding overhead.
4 The main theorem
- Theorem 19 guarantees a simulated channel approximating Lindblad evolution using O(c(τ,ϵ)) queries to each Hamiltonian and jump-operator oracle and its adjoint.The supplied theorem statement does not expose the complete approximation bound or the definition of c.Source: §4 · pp. 26–27
- The implementation uses additional arbitrary one- and two-qubit gates, with C_anc including block-encoding range-membership tests and fixed embedding operations.For the standard block encodings used, C_anc scales linearly with the number of ancilla qubits.Source: §4 · p. 27
- The general-case construction extends the algorithm to multiple jump operators and incorporates a nonzero Hamiltonian by interleaving transducers.The Hamiltonian component uses the Hamiltonian Cayley transducer in [7].Source: §4 · p. 27
4.1 Multiple Jump Operators
The multiple-jump construction modifies the local and global transducers to retain jump identities in the output and history registers.
4.1 Multiple Jump Operators
- The local transducer outputs the jump label in the public jump branch, while global histories use 0 for no jump and 1 through m for jump identities.The construction uses the stacked jump operator in place of a single jump operator.Source: §4.1 · p. 27
- The stacked jump operator is used with the local construction parameter set to α = 1.The source describes this as the modification for handling multiple jump operators.Source: §4.1 · p. 27
- Each history register records no jump or a jump index, and the position of a nonzero symbol records its jump time.The jump-type register remains within each operator block in the Schur estimate.Source: §4.1 · p. 27
4.2 Non-zero Hamiltonian
The nonzero-Hamiltonian construction combines Hamiltonian and dissipative evolution by interleaving their transducers. The resulting composed transducer supports the general simulation guarantee.
4.2 Non-zero Hamiltonian
- The combined construction interleaves Hamiltonian and dissipative simulation, using the algorithm in [7] alongside the dissipative algorithm.A local combined SELECT primitive provides access to both components.Source: §4.2 · pp. 27–28
4.2.1 Cayley Transducer
- The Hamiltonian Cayley transducer uses a Hermitian embedding to obtain a Hermitian oracle that block encodes the same matrix as a general block-encoding oracle.The local Hamiltonian catalyst map has norm at most δ_H.Source: §4.2.1 · p. 28
4.2.2 Error Bound From Composition
- The composition analysis bounds the combined error using local-error estimates, Lie–Trotter bounds, and telescoping when δ_L ≤ 1/2.The passage states these bounds hold for a universal constant C_comp.Source: §4.2.2 · p. 29
4.2.3 Composition of Hamiltonian and Dissipative Transducers
- The composed transducer interleaves local Hamiltonian and dissipative rotations and uses a time-and-stage private label.The result is a one-SELECT-query transducer for a Stinespring isometry, and the general algorithm uses O(c(τ,ϵ)) queries to each oracle.Source: §4.2.3 · pp. 29, 30, 33
4.3 Gate Complexity
The gate-efficient implementation reorganizes the query-free transducer operations and compresses jump histories. Its construction combines effective-rotation implementations with segmentation of the evolution.
4.3 Gate Complexity
- Reordering operations by the last jump event compiles the remaining no-jump dissipative and Hamiltonian rotations into an efficiently implemented unitary.Segmentation is then used to obtain the gate-complexity bound.Source: §4.3 · p. 33
4.3.1 Efficient Implementation of the no-jump and Hamiltonian rotations
- The no-jump and Hamiltonian rotations are combined in an effective rotation whose components are implemented through block-encoding constructions.For the effective rotation, the cited implementation uses an LCU decomposition and oblivious amplitude amplification.Source: §4.3.1 · p. 34, §4.3.2 · p. 38
4.3.2 Efficient implementation of the effective rotation
- The effective rotation is decomposed into contractions with efficient block encodings and implemented using a linear combination of unitaries.The cited construction reports a gate cost of O(C_anc + log(r + 1)) for the rotation.Source: §4.3.1 · pp. 34–35, §4.3.2 · p. 38
4.3.3 History Compression
- A compressed history stores time–jump-type pairs, with enough records for the maximum reuse length, because each transducer application adds at most one jump.Every forward reuse branch agrees with the full-history construction under this encoding, preserving the reuse-block and amplification error guarantees.Source: §4.3.3 · p. 38
4.3.4 Efficient Implementation of the Global Transducer
- The compiled global transducer agrees with the full-history transducer on inputs encountered in forward reuse circuits and is extended unitarily on unused states.Its query-free implementation includes jump-history updates and the effective rotation for the remaining steps.Source: §4.3.4 · p. 39
4.3.5 Segmentation
- The evolution is segmented into pieces of normalized time τ′, and the analysis establishes the gate-complexity portion of the main theorem.The construction discards each segment’s history and work registers before the next segment.Source: §4.3.5 · pp. 39–40
5 Extension to the time-dependent Lindblad equation
The construction extends to time-dependent Lindblad generators when time-controlled oracles have fixed normalization bounds. It preserves the time-independent simulation error estimates, with an additional discretization error and gate-cost dependence on the number of segments.
5 Extension to the time-dependent Lindblad equation
- The construction extends to time-dependent generators given time-controlled oracles with normalization factors fixed uniformly over the evolution interval.Time-dependent normalization factors can be rescaled; this adds O(c(τ, ϵ)Cscale) gates per combined SELECT invocation.Source: §5 · p. 40
- Replacing the oracles with time-controlled variants requires no other structural modification, and the time-independent simulation error estimates hold uniformly.The estimates depend only on normalization bounds and chronological ordering; the construction implements piecewise-constant evolution up to those error bounds.Source: §5 · p. 40
- The added discretization error is at most ϵ/4, keeping total error at most ϵ, while increasing the number of segments raises gate but not query complexity.The preceding simulation error bounds contribute at most 3ϵ/4; gate complexity grows through log(r + 1).Source: §5 · p. 41
6 AI Use
The authors disclose GPT assistance in developing the approach and proofs, implementing gates, and checking the manuscript, while taking sole responsibility for the final manuscript.
6 AI Use
- GPT 5.6-Sol helped develop the main approach and proofs, including an initial factorial-decay proof later refined and simplified by the authors.GPT 6-Astra developed the efficient gate-implementation idea and initial proof.Source: §6 · p. 41
- GPT 5.6-Sol and GPT 6-Astra also checked the manuscript and suggested revisions; the authors take sole responsibility for its correctness.Source: §6 · p. 41