PaperlayerView exact revision on arXiv

Source-linked AI summary

Query-Optimal and Gate-Efficient Lindbladian Simulation

Boyang Chen, Minbo Gao, Xinzhao Wang, Shuo Zhou

arXiv:2609.18757v1quant-phcs.DS

TL;DR

This paper asks whether arbitrary dissipation can be simulated with the Hamiltonian-optimal joint dependence on time and precision, a question left open for general Lindbladians. It gives a general Lindbladian algorithm matching that lower bound, with the same query bound for Lipschitz-continuous time-dependent dynamics under coherent time-indexed oracle access.

  • Problem

    For general Lindbladians, the optimal joint query dependence on evolution time and precision remained open, despite being known for Hamiltonian simulation.

    Source: §1 · p. 2

  • Method

    The construction uses a transducer and a reuse circuit to remove the need to supply its catalyst.

    Source: §5 · p. 22

  • Results

    The query complexity matches the Hamiltonian joint time–precision lower bound, and the same query bound holds for Lipschitz-continuous time-dependent Lindbladians under coherent time-indexed oracle access.

    Source: §10 · p. 47

  • Takeaways & Limitations

    In the considered oracle model, adding dissipative terms does not worsen the optimal dependence on normalized time and precision.

    Source: §10 · p. 47

    Whether locality, small commutators, or other generator properties can further reduce simulation cost while retaining optimal time–precision dependence remains open.

    Source: §10 · p. 47

Abstract

from arXiv · show

We give a quantum algorithm for Lindbladian simulation given a block encoding of the Hamiltonian $H$ and a projected unitary encoding of the stacked jump operator $B=\sum_{k=1}^m \lvert k\rangle\otimes L_k$, with normalization factors $\alpha_H$ and $\alpha_B$, respectively. For evolution time $t$, set $\tau=(\alpha_H+\alpha_B^2)t$. The algorithm approximates the evolution channel to diamond-norm error $\varepsilon$ using $O\!\left(\tau+\frac{\log(1/\varepsilon)}{\log\!\left(e+\log(1/\varepsilon)/\tau\right)}\right)$ oracle queries, matching the query lower bound for Hamiltonian simulation. The number of additional one- and two-qubit gates is linear in the query complexity up to polylogarithmic factors. The query- and gate-complexity bounds extend to Lipschitz-continuous time-dependent Lindbladians under coherent time-indexed oracle access. Our construction uses a one-query transducer that implements a product of rational approximations to short-time evolution when supplied with a catalyst. We bound the error from omitting the catalyst by exploiting orthogonality between different sequences of Kraus labels. The gate implementation combines a compressed Kraus-label representation, which stores only the positions and values of the nonzero labels, with the rotation factorization of Chen et al.

1 Introduction

The section presents a query-optimal algorithm for Lindbladian simulation, extending Hamiltonian time–precision bounds to dissipative dynamics and describing its transducer, catalyst-removal analysis, and compressed Kraus-label implementation. It also discusses query costs in time-dependent evolution and state-preparation applications, and situates the algorithm’s query and gate complexity among related approaches.

1 Introduction

  • The introduction frames the problem as whether arbitrary dissipation adds asymptotic query cost beyond the optimal joint time–precision dependence for Hamiltonian simulation.Earlier algorithms achieved nearly linear time and polylogarithmic precision dependence, while the additive time-and-precision result of Borras and Marvian required a constraint on the jump operators.Source: §1 · p. 2

1.1 Model and main result

  • For time-independent Lindbladian evolution, an algorithm approximates the channel to diamond-norm error ε and matches the Hamiltonian query lower bound for normalized evolution time τ ≥ 1.The same query bound extends to Lipschitz-continuous time-dependent Lindbladians under coherent time-indexed oracle access; additional one- and two-qubit gates are linear in query complexity up to polylogarithmic factors.Source: §1 · pp. 2–3, §1.1 · p. 5

1.2 Algorithm overview

  • The algorithm approximates evolution by a product of CPTP steps and implements that product with a one-query transducer whose catalyst is returned unchanged.Sequential composition combines the local transducers into one transducer for the full product, with a direct-sum catalyst across steps.Source: §1.2 · pp. 5–6

Reuse without preparing the catalyst.

  • Catalyst-free reuse approximates the product isometry by recombining outputs from repeated transducer calls, and orthogonality between Kraus-label sequences sharpens the error bound.The analysis uses monotone time indices and squared-norm addition for terms with nonzero Kraus labels at different positions, leaving the bound dependent on J only through τ = Jαδ.Source: Reuse without preparing the catalyst · pp. 6–8

Combining reuse lengths.

  • Combining reuse lengths with an LCU polynomial yields bounded normalization, while compressed Kraus-label storage and rotation factorization reduce gate costs.The compressed representation stores positions and values of O(q) nonzero labels; interval-based rotation factorization gives only polylogarithmic dependence on J per call.Source: Combining reuse lengths · pp. 8–9
  • For time-dependent simulation, the precision-dependent term no longer multiplies τ, removing the squared logarithmic factor in the previous bound.The comparison is stated for τ = αV T.Source: Combining reuse lengths · p. 9
  • Replacing the simulator improves query complexity for Gibbs-state and ground-state preparation without changing their mixing times or oracle-construction costs.The cited applications are Chen et al.’s exact detailed-balance Lindbladian method and Ding et al.’s engineered single-jump method [DCL24].Source: Combining reuse lengths · p. 9

1.3 Related work

  • Concurrent work reports the same asymptotic query complexity, while this paper’s compressed-label implementation and rotation factorization use eO(mq) additional gates.Wang and Ye [WY26] use eO(mq3/ε) additional gates under the same oracle-access assumptions; Kitchen also studies time-dependent simulation.Source: §1.3 · p. 9
  • Related approaches include structure-dependent simulation, Hamiltonian dilations or repeated interactions, and randomized or trajectory-based methods.The structure-dependent results rely on additional assumptions not required here [SAS26] [GJL26].Source: §1.3 · p. 10
  • Other methods estimate observables from repeated circuit executions or use copy-counted quantum program-state inputs, unlike this paper’s full-channel diamond-norm simulation.Observable-estimation methods target Tr[O etL(ρ)] for a specified input state and observable; Patel and Wilde [PW23a] [PW23b] study wave matrix Lindbladization.Source: §1.3 · p. 10

2 Rational CPTP discretization

The evolution is approximated by composing rational CPTP steps, each with a Stinespring isometry that records Kraus labels. The analysis bounds the one-step error and then controls the accumulated diamond-norm error.

2 Rational CPTP discretization

  • Composing J rational CPTP steps of duration δ=t/J approximates the evolution, with a telescoping argument bounding the accumulated diamond-norm error.Both the step channel and exact short-time evolution are CPTP, so each has diamond norm one.Source: §2 · pp. 10, 11, 14
  • The step isometry has orthogonal no-jump and jump ranges, making it an isometry and eliminating cross terms when the environment register is traced out.The resulting map has a Kraus representation and is CPTP.Source: §2 · p. 11
  • Tracing the first j Kraus-label registers recovers j applications of Φδ, by induction over the recursively defined product isometries.Each step uses a fresh register to store its Kraus label coherently.Source: §2 · pp. 11–12
  • The error analysis compares Φδ with Id+δL by bounding the no-jump and jump contributions separately, then compares Id+δL with e^δL.The one-step bounds are combined before telescoping over J steps.Source: §2 · pp. 12–14

3 A one-query transducer for a rational step

The section constructs a one-query transducer for a rational short-time step, using an oracle call followed by an oracle-independent unitary. Its output implements the step while restoring the input-dependent catalyst.

3 A one-query transducer for a rational step

  • One oracle query followed by G implements the rational step Wδ and restores the catalyst γψ.The transducer first applies Ω = U_H ⊕ U_B ⊕ U†_B to the private space, then applies G to the public and private spaces.Source: §3 · pp. 14–15
  • The queried state is reorganized into public no-jump and jump outputs, with the jump component obtained by projecting the fourth queried entry.The construction identifies the no-jump output through the first, third, and fifth queried entries and obtains the jump output from the fourth.Source: §3 · p. 16
  • G applies M to selected system components and routes the orthogonal remainders through separate unitary actions.The selected components are the system vectors in s, the zero-ancilla part of h, and the zero-ancilla part of b; the remainders receive phases in orthogonal output subspaces.Source: §3 · p. 17
  • The construction verifies that G is unitary by mapping orthogonal input subspaces isometrically onto orthogonal output subspaces.The proof separately checks the selected system components, the orthogonal remainders, and the components involving ℓ and z.Source: §3 · p. 17

4 A one-query transducer for the full product

Sequential composition combines J local one-query transducers into a transducer for the full product isometry. The construction uses one controlled oracle application and restores the global catalyst.

4 A one-query transducer for the full product

  • The global catalyst places each step’s catalyst in a separate direct-sum component of the private space.The construction uses sequential composition of transducers and labels the private-space components by step.Source: §4 · p. 20
  • One controlled application of Ω suffices for the transducer implementing the full product isometry W_J.The global transducer S is built by composing J local transducers, each implementing one step.Source: §4 · pp. 20–21
  • After the J updates, the public state is W_Jψ and the private state is restored to Γψ.The induction over local updates establishes the global transducer identity.Source: §4 · p. 22
  • The construction also establishes a bound on the global catalyst map.The proof combines the local catalyst bound with the fact that each W_j is an isometry.Source: §4 · p. 22

5 Reuse without preparing the catalyst

To avoid supplying the input-dependent catalyst, the section reuses the transducer across orthogonal copies of the public space while sharing one private space. The resulting circuit encodes an approximation to W_J.

5 Reuse without preparing the catalyst

  • The reuse circuit replaces the unavailable input-dependent catalyst with N sequential calls to S and a shared private input initialized to zero.It distributes the public input uniformly over N mutually orthogonal copies, passes each private output to the next call, and recombines the public outputs.Source: §5 · p. 22
  • For each reuse length N, the circuit implements a projected unitary encoding of P_N using N calls to S.The circuit uses a register to label the N public copies and isometries defining its input and output spaces.Source: §5 · pp. 22–23
  • The approximation error is expressed as W_J − P_N = S01 g_N(S11)Γ.The error depends on the averaging polynomial g_N applied to the private block S11 and on the catalyst Γ.Source: §5 · p. 24

6 Combining reuse lengths

The section combines reuse lengths so their approximation errors can cancel while keeping the linear-combination normalization bounded. It first constructs the general linear-combination encoding, then selects smoothed coefficients for the target approximation.

6 Combining reuse lengths

  • Combining reuse lengths replaces the single-length error polynomial with a weighted sum that can cancel and decay rapidly.The approach forms a linear combination of reuse maps with coefficients summing to one.Source: §6 · p. 24

6.1 A general LCU construction

  • A general LCU construction coherently selects reuse maps and yields a projected unitary encoding of their weighted sum.The construction uses at most R calls to S for reuse lengths up to R; its normalization is the coefficients’ ℓ1 norm.Source: §6.1 · pp. 25–26

6.2 Choosing the coefficients

  • Smoothing the polynomial coefficients keeps the LCU normalization constant while controlling the approximation error.Multiplication by g_12q averages the monomial coefficients before changing basis to the reuse polynomials g_N.Source: §6.2 · p. 26
  • Under the stated conditions, the chosen coefficients give a normalization-2 projected unitary encoding of fW_J using at most 20q calls to S.The proposition assumes αδ ≤ 1/2, J ≥ 8q, and q ≥ C0τ.Source: §6.2 · p. 28

7 The final algorithm

Section 7 uses oblivious amplitude amplification to turn an approximate projected isometry into a channel approximation, then chooses parameters to meet the error target while controlling query use.

7.1 Oblivious amplitude amplification

  • Oblivious amplitude amplification converts the normalization-2 projected encoding into an isometry approximating WJ.The proof compares the amplified projected block with WJ and bounds the component outside the output subspace.Source: §7.1 · pp. 29–30
  • The isometry error bounds the resulting channel error after auxiliary registers are traced out, since partial trace does not increase trace norm.The argument takes the supremum over reference systems and input states to obtain a diamond-norm bound.Source: §7.1 · pp. 30–31

7.2 Parameter choice

  • The polynomial degree q is chosen to control the approximation error while scaling as stated in Theorem 1.2.The parameter lemma ensures ηq ≤ ε/20 and q ≥ C0τ.Source: §7.2 · p. 31
  • The parameter choices combine amplification and discretization errors to meet the target accuracy using at most 60q queries; increasing J affects gates and ancillas, not query count.For 2τ ≤ ε, the identity channel already meets the accuracy target.Source: §7.2 · pp. 31–32

8 Time-dependent Lindbladians

Section 8 extends the simulation to Lipschitz-continuous time-dependent Lindbladians using coherent time-indexed oracle access. It discretizes the evolution into rational steps and controls both the approximation and discretization errors.

8 Time-dependent Lindbladians

  • Under the stated Lipschitz condition and coherent time-indexed oracle access, the time-dependent evolution is approximated to diamond-norm error ε with the query complexity of Theorem 8.1.The Lipschitz constant affects discretization and gate complexity, but not query complexity.Source: §8 · pp. 32–35
  • At each grid time, the algorithm uses a rational channel and Stinespring isometry built from H(tj) and B(tj), with a shared step size and encoding structure.The discretization size J can be increased to control the discretization error.Source: §8 · pp. 32–34
  • Duhamel’s formula bounds the error from replacing the generator within each interval, and telescoping sums the per-step errors across the evolution.The propagators used in the comparison are CPTP and have diamond norm one.Source: §8 · p. 33
  • The shared transducer unitary uses a time-indexed query and induces the composition of the rational channels across grid steps.The construction uses a possibly different catalyst map at each step.Source: §8 · p. 34
  • For Lipschitz-continuous H and B, the generator’s Lipschitz constant is bounded by 2LH + 4αB LB.This bound is used to control the time-dependent discretization error.Source: §8 · p. 35

9 Gate complexity

This section develops a gate-efficient circuit for ε-accurate channel simulation at the query complexity of Theorem 8.1. It factors the update product, stores only nonzero Kraus labels, implements rotations with coherent interval controls, and assembles the exchange and rotation products while bounding the total gate cost.

9 Gate complexity

  • For one J-step segment, O(q) transducer calls each update O(q) stored Kraus labels, yielding a q^2 gate-count term; choosing degree q=O(ℓε) per segment keeps total queries within Theorem 8.1’s bound.Source: §9 · p. 35

9.1 Factoring the update product

  • The update product is reorganized into a query with private-summand operations, followed by rotation and exchange products, avoiding individual implementation of all J factors.The factorization separates Kraus-label exchanges from rotations so the products can be implemented more efficiently.Source: §9.1 · pp. 37–38

9.2 Compressing and updating the Kraus labels

  • O(q[log J + log(m + 1)] + a) gates implement Kraus-label exchanges using compressed registers for nonzero position–label pairs.The representation stores at most 60q + 1 pairs, using O(q[log J + log(m + 1)]) qubits; a call to S or S† changes the number of nonzero labels by at most one.Source: §9.2 · pp. 38, 40

9.3 Implementing the rotations

  • Only rotations R_j with j > j_w act for a given encoded label string; aligned power-of-two intervals implement their reduced two-dimensional rotation using [CGJ+26, Lemma 10].The basis change leaves the z component fixed and applies Rot(d) to the other two components.Source: §9.3 · pp. 41–42
  • The rotation product is implemented coherently by computing interval endpoints from the compressed position–label encoding, applying controlled factors on nonempty intervals, and uncomputing the endpoints.The interval controls implement R_{J−1} ··· R_0 on every valid encoding.Source: §9.3 · pp. 42–43

9.4 The complete circuit and its gate count

  • Algorithm 2 combines Q′ with the exchange and rotation products to implement S exactly on valid encodings with w ≤ 60q, and reversing it implements S†.The only oracle-dependent operation is a single query, so a controlled call to S or S† uses one query.Source: §9.4 · pp. 43–44
  • The OAA circuit uses exact calls to S and S† on valid encodings and induces the channel whose error is bounded in Section 7.The input to every such call is supported on valid encodings with w ≤ 60q.Source: §9.4 · p. 45
  • The completed simulation’s one- and two-qubit gate count satisfies the gate bound in Theorem 9.1, with q, log J, and log(n + 1) each O(ℓε).The section identifies this bound with Eq. (104); setting T = t and L_L = 0 gives Eq. (8) in Theorem 1.2.Source: §9.4 · p. 47

10 Conclusion

The conclusion states that general Lindbladian simulation matches the Hamiltonian joint time–precision lower bound, including for Lipschitz-continuous time-dependent dynamics with coherent time-indexed access.

10 Conclusion

  • General Lindbladian simulation matches the Hamiltonian joint time–precision lower bound, and the same query bound holds for the stated time-dependent setting.For time-dependent Lindbladians, the Lipschitz constant affects discretization and gate complexity, but not query complexity.Source: §10 · p. 47
  • Whether locality, small commutators, or other generator properties can further reduce simulation cost while retaining optimal time–precision dependence remains open.Source: §10 · p. 47

A Proof of the polynomial bound for the private block

This section proves the private-block polynomial bound by comparing S11 with a special block annihilated by p and bounding perturbation terms through their structure and Kraus-label orthogonality. It also extends the bound to the time-dependent construction, using term expansion and counting when private spaces may use their own oracles.

Proof strategy

  • p(S11(0)) = 0, so expanding p(S11) around S11(0) makes every term contain a perturbation factor, split into no-jump and jump parts.The proof then bounds ordered products of S11(0), ∆0, and ∆1 to establish Proposition 6.2.Source: A Proof of the polynomial bound for… · p. 48

Perturbation bounds

Ordered-product bound

  • Proposition A.2 bounds any ordered product of S11(0), ∆1, and ∆0 in terms of its numbers of jump and no-jump factors.The proof organizes product terms by nondecreasing time indices and their increments at ∆1 and ∆0 factors.Source: A Proof of the polynomial bound for… · p. 55

Kraus-label orthogonality

  • For fixed no-jump increments, distinct jump increments have orthogonal output ranges because their values are recoverable from the positions of nonzero Kraus labels.Each ∆1 factor creates a nonzero label at its output position, while S11(0) and diagonal ∆0 factors preserve earlier labels.Source: A Proof of the polynomial bound for… · pp. 48, 56

A Proof of the polynomial bound for the private block

  • Distinct values of a are recoverable from the output’s nonzero-label positions and yield orthogonal ranges; outputs in different K_jL are orthogonal as well.For fixed b, the final index and the r largest positions carrying nonzero output labels determine a.Source: A Proof of the polynomial bound for… · pp. 56–57
  • The possible a and b are counted by relaxing their increment constraints to nonnegative integer tuples with fixed sums, using |a|+|b|=jL−j0≤J−1.This count bounds the number of terms for each fixed b before applying the decomposition and triangle inequality.Source: A Proof of the polynomial bound for… · p. 57
  • Expanding p(S11)^2q produces at most 18^2q ordered products, and splitting each Δ into Δ1+Δ0 yields at most 28^2q products to bound.Each initial term contains one to four Δ factors; the resulting products contain between 2q and 8q factors.Source: A Proof of the polynomial bound for… · pp. 57–58
  • The time-dependent private-block bound follows by replacing the common oracle Ω on K_j with Ω_j, without requiring Ω_j=Ω_k for distinct indices.The proof applies the oracle assumptions separately for each j.Source: A Proof of the polynomial bound for… · p. 58

Related papers

Loading 2609.18757v1…