PaperlayerView exact revision on arXiv

Source-linked AI summary

Efficient Quantum Algorithms for Simulating Lindblad Evolution

Richard Cleve, Chunhao Wang

arXiv:1612.09512v3quant-ph

TL;DR

Many systems of interest evolve according to the Lindblad equation rather than the Schrödinger equation, motivating algorithms to simulate Lindblad evolution. The paper uses a channel-oriented linear-combination-of-unitaries construction; its Hamiltonian-reduction analysis states an N scaling threshold for approximating the final state.

  • Problem

    Many systems of interest are open and are well-captured by the Lindblad equation, prompting the problem of simulating its quantum channel for an unknown input state.

    Source: §1 · pp. 1–2

  • Method

    The algorithm simulates the Lindblad-evolution channel with a circuit independent of the unknown input state, using a linear-combination-of-unitaries variant suitable for channels.

    Source: §1 · p. 2, §1.2 · p. 4

  • Results

    N scaling at least as t^3/epsilon^2 is stated to yield a final-state approximation within epsilon in the Hamiltonian-reduction analysis.

    Source: §1 · p. 3

  • Takeaways & Limitations

    A channel-suitable linear-combination-of-unitaries construction is a main novel ingredient of the paper's proof.

    Source: §1.2 · p. 4

    For time-independent Lindblad simulation through time-independent Hamiltonian evolution along the analyzed reduction structure, the scaling phenomenon is generally necessary.

    Source: §1 · p. 2

Abstract

from arXiv · show

We consider the natural generalization of the Schr\"{o}dinger equation to Markovian open system dynamics: the so-called the Lindblad equation. We give a quantum algorithm for simulating the evolution of an $n$-qubit system for time $t$ within precision $\epsilon$. If the Lindbladian consists of $\mathrm{poly}(n)$ operators that can each be expressed as a linear combination of $\mathrm{poly}(n)$ tensor products of Pauli operators then the gate cost of our algorithm is $O(t\, \mathrm{polylog}(t/\epsilon)\mathrm{poly}(n))$. We also obtain similar bounds for the cases where the Lindbladian consists of local operators, and where the Lindbladian consists of sparse operators. This is remarkable in light of evidence that we provide indicating that the above efficiency is impossible to attain by first expressing Lindblad evolution as Schr\"{o}dinger evolution on a larger system and tracing out the ancillary system: the cost of such a \textit{reduction} incurs an efficiency overhead of $O(t^2/\epsilon)$ even before the Hamiltonian evolution simulation begins. Instead, the approach of our algorithm is to use a novel variation of the "linear combinations of unitaries" construction that pertains to channels.

1 Introduction

The paper addresses quantum simulation of Markovian open-system dynamics, where the input state is unknown and the goal is to implement the evolution channel. It presents an efficient Lindblad-simulation algorithm, alongside bounds on a Hamiltonian-reduction approach and results for local and sparse operators.

1 Introduction

  • Lindblad dynamics model Markovian open systems and arise in quantum physics, chemistry, biology, and quantum-information tasks.The paper describes the dynamics as a continuous-time quantum channel whose future state depends only on its current state.Source: §1 · pp. 1–2
  • A Hamiltonian-reduction simulation with error ϵ requires N at least t^3/ϵ^2, giving total Hamiltonian evolution time scaling as t^2/ϵ.The paper argues that, in general, this scaling phenomenon is necessary for simulations following the reduction structure illustrated in Figure 1.Source: §1 · pp. 2–3

1.1 Previous work

  • Earlier Lindblad algorithms had costs O(t^2/ϵ) for local operators and O(t^1.5/√ϵ) for a later improvement, while related algorithms may return observable expectations rather than the final state.The paper states that none of the previous algorithms it knows of attained O(t polylog(t/ϵ)poly(n)).Source: §1.1 · p. 3

1.2 New results

  • For Lindbladians specified by Pauli sums, the paper attains O(t polylog(t/ϵ)poly(n)) gate cost when m and q are polynomial in n.Theorem 1 gives the circuit-size bound; the paper identifies this scaling as its attained performance.Source: §1.1 · p. 3, §1.2 · p. 4
  • A channel-suitable variant of linear combinations of unitaries is a main novel ingredient in the proof of Theorem 1.The theorem concerns implementing the quantum channel for Lindblad evolution.Source: §1.2 · p. 4
  • The paper also establishes simulation bounds for local Lindbladians and for d-sparse Lindbladians specified through queries to their nonzero entries.Local operators act on a constant number of qubits; d-sparse operators have at most d nonzero entries in each row or column.Source: §1.2 · p. 5

2 Brief summary of novel techniques

Standard LCU methods target unitary operations, while Lindblad simulation requires handling channels that need not be mixed unitary. The paper introduces channel-specific LCU and isometry amplification, and explains why applying standard LCU to Stinespring dilations performs poorly.

2 Brief summary of novel techniques

  • The authors develop a channel-specific variant of LCU rather than reducing channel simulation to the unitary case.Some channels are mixed unitary, but channels arising from Lindblad evolution need not be; the Stinespring-dilation route performs poorly.Source: §2 · p. 6
  • They use oblivious amplitude amplification for isometries because channel LCU produces a channel-purification isometry, not a unitary extension.The paper says a reductionist approach based on extending isometries to unitaries does not work.Source: §2 · p. 6

2.1 The standard LCU method performs poorly on Stinespring dilations

  • Standard LCU has subconstant success probability as t approaches zero, creating a problem for general Lindblad simulation.The section analyzes this issue for Stinespring dilations of channels.Source: §2.1 · pp. 6–7
  • For small t, the new method's failure probability is Θ(t), allowing Θ(1/t) repetitions before cumulative failure becomes constant.The corresponding evolution time remains constant as t approaches zero.Source: §2.1 · p. 7

3 New LCU method for channels and completely positive maps

The section constructs a channel-oriented LCU circuit from Kraus-operator decompositions, using a fixed purifier superposition so the success branch yields the channel in purified form.

3 New LCU method for channels and completely positive maps

  • The circuit's objective is to implement the channel using the implementations of the unitary terms U_jk.The construction specifies W and a fixed |µ⟩ for any n-qubit input state.Source: §3 · p. 8
  • Circuit W uses multiplexed-U and multiplexed-B gates, with the fixed state |µ⟩ supplied to the purifier register.The indicator register marks success, the purifier register purifies the channel on success, and the system register holds the state being evolved.Source: §3 · p. 8
  • The construction applies to Kraus operators of a completely positive map, with each operator decomposed into a linear combination of unitaries.The decomposition uses nonnegative coefficients α_jk and unitary U_jk terms.Source: §3 · pp. 7–9
  • Using |µ⟩ instead of a fixed Kraus index makes the success branch the superposition of Kraus outputs, the channel's purified form.The text contrasts this with selecting one Kraus operator, which captures only one branch of the quantum map.Source: §3 · p. 9

4 Overview of the main result, Theorem 1

The section proves Theorem 1 using a channel-oriented LCU construction and modified oblivious amplitude amplification, developing and implementing a small-time approximation before amplifying success and reducing multiplexed-gate costs. It bounds the encoded circuit’s gate costs and extends the simulation to arbitrary evolution times by segmentation, achieving error within ε in diamond norm for r = 1/ε.

4 Overview of the main result, Theorem 1

  • The proof combines a channel LCU variant with modified oblivious amplitude amplification, building on constructions in and.The section organizes the proof into approximation, circuit implementation, repeated simulation, amplification, gate reduction, and total-cost analysis.Source: §4 · p. 10

4.1 A simple mapping Mδ that approximates e^Lδ for small δ

  • For small δ, a map Mδ with m+1 Kraus operators approximates e^(Lδ) to precision O(δ^2), while satisfying only an approximate trace-preserving condition.In the paper’s notation, the evolution is written e^Lδ.Source: §4.1 · p. 11

4.2 Approximating Mδ by a quantum circuit via the new LCU method

  • The new LCU method constructs a circuit approximating Mδ, and its success-probability parameter differs from the actual probability by O(δ^2).The analysis tracks cumulative circuit-construction error in subsequent sections.Source: §4.2 · pp. 12–14

4.3 Simulating r iterations of MO(1/r) with constant success probability

  • This approach conditionally simulates M(r); for t ∥L∥pauli < ln(2), its success probability parameter exceeds 1/4 and can be diluted to exactly 1/4 with an additional indicator-register qubit.Source: §4.3 · pp. 14–15

4.4 Oblivious amplitude amplification for isometries

  • Modified oblivious amplitude amplification addresses the isometry and non-trace-preserving hurdles, with the latter causing only a small error, and implements a Stinespring dilation of the repeated map.The resulting circuit F implements a quantum channel after the indicator and purifier registers are traced out.Source: §4.4 · pp. 15, 17

4.5 Concentration bound and encoding scheme

  • A Hamming-weight cutoff reduces multiplexed-U gate occurrences from O(r), with error ϵ; the encoded indicator and purifier registers use O(h log(r) + h log(mq)) qubits.The cutoff retains states of Hamming weight at most h; the encoding stores nonzero components and their positions.Source: §4.5 · pp. 17–19
  • The encoded initial state is |0a⟩|0b⟩|0c⟩, with a = O(log(r)h), b = O(log(mq)h), and c = O(log(m)h); the encoding operator E represents the multiplexed-B gates.The concentration bound and encoding scheme contribute only O(epsilon) error.Source: §4.5 · p. 19, §4.6 · p. 20

4.6 Total number of gates and proof of the main theorem

  • Each multiplexed-U gate costs O(mq^2(log(mq) + n)) gates, and h occurrences give O(mq^2h(log(mq) + n)) gates for this part.The count follows from implementing O(mq^2) controlled-U gates, each multiplexed over log(mq) qubits and involving O(n) Paulis.Source: §4.6 · p. 20
  • Implementing encoding operator E and two reflections requires O(log(1/ϵ)h + m^2q^2) 1- and 2-qubit gates for this part; the reflections cost the same order as the encoded representation’s qubit count.Source: §4.6 · p. 20
  • For arbitrary t, the evolution is divided into O(t||L||pauli) segments, each simulated at precision epsilon/(t||L||pauli) before tracing out the indicator and purifier registers.The circuit is repeated for each segment.Source: §4.6 · p. 20
  • Taking r = 1/epsilon makes the simulation error at most epsilon in diamond norm.The bound follows from Eqs. (78) and (100).Source: §4.6 · p. 20

5 Lindbladians with sparse Hamiltonian and Lindblad operators

For sparse Lindbladians, the section approximates the Hamiltonian and Lindblad operators with equal-coefficient LCU sums and exploits the given operator oracles in its gate-cost analysis.

5 Lindbladians with sparse Hamiltonian and Lindblad operators

  • The analysis tracks normalized evolution time t∥L∥_pauli and the number q of unitaries in each approximation.The text identifies these as key quantities for the sparse simulation analysis.Source: §5 · p. 21
  • The sparse case assumes H is d-sparse and each L_j is both row- and column-d-sparse.The operators are approximated as linear combinations of unitaries with equal coefficient γ; the stated max-norm approximation error is O(d^2γ).Source: §5 · p. 21
  • Given oracles for H and the L_j, the implementation eliminates the m and q factors from gate complexity while retaining log(m) and log(q) factors.The encoding cost becomes O(log(1/ϵ)h + poly(n)) because the LCU coefficients for each H and L_j are equal.Source: §5 · p. 21

A Cost of expressing Lindblad evolution as Hamiltonian evolution

The section shows that a continually reset ancilla representation of Lindblad evolution can require unbounded Hamiltonian evolution, establishing a lower bound using one-qubit amplitude damping.

A Cost of expressing Lindblad evolution as Hamiltonian evolution

  • In the N→∞ limit, the continually reset Hamiltonian representation necessarily has infinite total evolution time.The discretization approximates the Lindbladian trajectory at each of its N stages.Source: A Cost of expressing Lindblad… · p. 24
  • For one-qubit amplitude damping over [0, ln 2], an N-stage discretization requires total Hamiltonian evolution time Ω(N), independent of ancilla dimension.The lower-bound argument uses the initial state |1⟩⟨1|, which evolves to the maximally mixed state.Source: A Cost of expressing Lindblad… · pp. 24, 26
  • For short evolution from a product state, tracing out the ancilla after joint Hamiltonian evolution is approximated by a system-only Hamiltonian with O(δ²) trace-norm error.The approximation error is independent of the ancillary and system-register dimensions.Source: A Cost of expressing Lindblad… · pp. 24–25, Figure 4 · p. 25
  • The lower bound follows because replacing N joint evolutions by system-only evolutions incurs O(Nδ²) error, while unitary evolution cannot map |1⟩⟨1| to the maximally mixed state.Consequently, Nδ² ∈ Ω(1).Source: A Cost of expressing Lindblad… · p. 26

B Proof that ∥eδL −(1 + δL)∥⋄≤(δ∥L∥⋄)2 for small δ

The proof bounds the exponential remainder under a small-step condition, then extends the induced trace-norm estimate to the diamond norm using an ancillary register.

B Proof that ∥eδL −(1 + δL)∥⋄≤(δ∥L∥⋄)2 for small δ

Loading 1612.09512v3…