PaperlayerView exact revision on arXiv

Source-linked AI summary

Wave Matrix Lindbladization II: General Lindbladians, Linear Combinations, and Polynomials

Dhrumil Patel, Mark M. Wilde

arXiv:2309.14453v1quant-ph

TL;DR

Open-system dynamics governed by the Lindblad equation pose a simulation problem, and existing approaches often assume succinct operator representations or black-box access. This paper extends wave matrix Lindbladization using program-state inputs to general Lindbladians and operator combinations. Its sample complexity is dimension-independent, unlike full tomography of encoded operators.

  • Problem

    Open-system evolution requires simulating Lindblad dynamics, while existing algorithms often assume succinct representations or black-box access to Lindblad operators.

    Source: §1 · p. 2

  • Method

    The paper encodes Lindblad operators in pure program states and proposes sampling-based and Trotter-like algorithms, extending wave matrix Lindbladization to general Lindbladians and operator combinations.

    Source: §1 · p. 3

  • Results

    Tomography's sample complexity depends on system dimension, whereas wave matrix Lindbladization's does not.

    Source: §1.1 · p. 5

  • Takeaways & Limitations

    The proposed algorithms offer a route to simulating Lindbladian evolution with dimension-independent sample complexity relative to full tomography.

    Source: §1.1 · p. 5

    Efficient implementations of the predefined Lindbladian channels used as algorithmic subroutines remain to be investigated to resolve time or gate complexities.

    Source: §3 · p. 33

Abstract

from arXiv · show

In this paper, we investigate the problem of simulating open system dynamics governed by the well-known Lindblad master equation. In our prequel paper, we introduced an input model in which Lindblad operators are encoded into pure quantum states, called program states, and we also introduced a method, called wave matrix Lindbladization, for simulating Lindbladian evolution by means of interacting the system of interest with these program states. Therein, we focused on a simple case in which the Lindbladian consists of only one Lindblad operator and a Hamiltonian. Here, we extend the method to simulating general Lindbladians and other cases in which a Lindblad operator is expressed as a linear combination or a polynomial of the operators encoded into the program states. We propose quantum algorithms for all these cases and also investigate their sample complexity, i.e., the number of program states needed to simulate a given Lindbladian evolution approximately. Finally, we demonstrate that our quantum algorithms provide an efficient route for simulating Lindbladian evolution relative to full tomography of encoded operators, by proving that the sample complexity for tomography is dependent on the dimension of the system, whereas the sample complexity of wave matrix Lindbladization is dimension independent.

1 Introduction

The paper asks whether Lindbladian evolution can be simulated from copies of an initial state and program states encoding operators, extending an earlier single-operator setting. It presents algorithms for broader Lindbladians and operator combinations, and compares their sample complexity with tomography.

1 Introduction

  • Lindblad operators are encoded in pure program states; arbitrary-norm operators are represented by their normalized versions, and the Hamiltonian is supplied as a linear combination of program states.A program state can encode any unit-norm linear operator.Source: §1 · pp. 3–4
  • The problem is to approximate e^Lt from one copy of the initial state and copies of program states, while many existing approaches assume succinct operator representations or black-box access.The Lindblad master equation captures dynamics of Markovian open systems.Source: §1 · pp. 2–4

1.1 Summary of Main Results

  • The paper presents sampling-based and Trotter-like algorithms to implement e^Lt to a desired accuracy and investigates their program-state sample complexity.Sample complexity is the number of copies of the program states needed.Source: §1.1 · p. 5
  • The extension covers general Lindbladians and cases where a Lindblad operator is a linear combination or polynomial of operators encoded in program states.The linear-combination and polynomial cases assume access to unitaries that prepare the program states.Source: §1.1 · p. 5
  • Tomography has dimension-dependent sample complexity, whereas the proposed wave matrix Lindbladization algorithms have dimension-independent sample complexity.The comparison concerns simulating Lindbladian evolution from encoded operators.Source: §1.1 · p. 5
  • Repeating the sampling-based algorithm n = O(c2t2/ε) times approximates e^Lt with error O(ε).The iterations apply a channel conditioned on the sampled state in register 4, then trace out registers 2, 3, and 4.Source: §1.1 · pp. 6–7, Figure 1 · p. 7

1.2 Notation

  • The notation section defines the norms, normalized diamond distance, partial trace, maximally entangled state, and swap operations used in the paper.The normalized diamond distance is used to measure approximation error.Source: §1.2 · pp. 7–9

2 Quantum Algorithms for Simulating Markovian Dynamics

This section develops program-state quantum algorithms for simulating Lindbladian dynamics, covering general Lindbladians, linear combinations of encoded operators, and polynomial Lindblad operators. It also analyzes sample complexity and compares wave matrix Lindbladization with tomography, reporting dimension-independent sample complexity for the former and dimension-dependent sample complexity for the latter.

2.1 Simulating General Lindbladians

  • The general-Lindbladian setting includes multiple Lindblad operators encoded in pure states and a Hamiltonian represented as a linear combination of program states.Only normalized versions of the Lindblad operators are encoded.Source: §2.1 · p. 9

2.1.1 Sampling-based Approach

  • O(c^2t^2/ε) copies of ω suffice to approximate the general Lindbladian channel e^Lt within ε error in diamond distance.The bound applies to Lindbladians with multiple encoded Lindblad operators and a Hamiltonian.Source: §2.1.1 · p. 12

2.1.2 Trotter-like Approach

  • The Trotter-like algorithm uses O((J+K)||L||^2_max t^2/ε) copies of each program state, and its total sample complexity is never lower than Algorithm 1's.It approximates e^Lt within ε error in diamond distance; the total number of program states is O((J+K)^2||L||^2_max t^2/ε).Source: §2.1.2 · p. 16

2.2 Simulating Linear Combinations

  • For L given as a positive-coefficient linear combination of normalized encoded operators, LCU with amplitude amplification prepares the program state used for simulation.The resulting algorithm uses O(c^2t^2/ε) copies of that state to approximate e^Lt within ε error in normalized diamond distance.Source: §2.2 · pp. 18–20

2.3 Simulating Lindbladian Polynomials

  • For the polynomial case, the section assumes a single Lindblad operator without a Hamiltonian and represents that operator as a sum of positive-coefficient terms of degree |s|.Each term is defined from linear operators encoded in program states; the supplied passages do not yet give an algorithm or sample-complexity result.Source: §2.3 · p. 22
  • The polynomial construction encodes operators L1, …, LK in program states and uses strings from a set S, whose maximum string length D is the polynomial degree.The desired state is prepared using linear combination of unitaries, with amplitude amplification to raise the success probability close to one.Source: §2.3 · pp. 22–23
  • For a Lindbladian with a single Lindblad operator, algorithm A uses n = O(c²t²/ε) copies of program state ϕ to approximate channel e^Lt with ε error in normalized diamond distance.For each copy, it evolves the joint state under a Lindbladian acting on S and the program registers, traces out those registers, and repeats.Source: §2.3 · pp. 23, 24, 28

2.4 Wave Matrix Lindbladization Improves upon Tomography

  • If the approximate Lindblad operator is O(ε/t)-close in Hilbert–Schmidt distance, its channel is O(ε)-close to the target in diamond distance.The paper reduces pure-state tomography to wave-matrix tomography, transferring the pure-state tomography sample-complexity lower bound to the latter.Source: §2.4 · pp. 29–31
  • For approximately simulating channel e^{Lt}, wave matrix Lindbladization needs only O(t^2/ε) copies of |ψ⟩, independent of dimension d, whereas tomography followed by simulation has sample complexity that grows with d.Source: §2.4 · pp. 29, 31, 32
  • Sending program states can enable another party to simulate the encoded Lindbladian without revealing details of the encoded operator, a form of quantum copy-protection.The authors present this as a potential response to an open question about privately executable quantum operations beyond Hamiltonian simulation.Source: §2.4 · p. 32

3 Conclusion and Open Problems

The paper extends wave matrix Lindbladization to general Lindbladians and Lindblad operators expressed as linear combinations or polynomials of encoded operators. It analyzes program-state sample complexity and compares it with full tomography.

3 Conclusion and Open Problems

  • The extension covers general Lindbladians and Lindblad operators expressed as linear combinations or polynomials of operators encoded across multiple program states.The prequel considered a single Lindblad operator and a Hamiltonian.Source: §3 · p. 33
  • The paper proposes quantum algorithms for these cases and analyzes their sample complexities, measured by the number of program-state copies needed.Source: §3 · p. 33
  • Tomography’s sample complexity depends on system dimension, whereas wave matrix Lindbladization’s does not.Source: §3 · p. 33
  • Efficient implementations of short-time evolution under a predefined Lindbladian remain to be investigated; resolving them would determine the algorithms’ time or gate complexities.Source: §3 · p. 33
  • The paper leaves open whether the analyzed sample complexities are optimal, including whether matching lower bounds exist.Source: §3 · p. 33

A Error Analysis for Trotter-like Approach

The appendix analyzes the Trotter-like approach by comparing orderings of single-operator Lindbladian steps. A modified ordering introduces symmetry that cancels terms and improves the stated sample complexity.

A Error Analysis for Trotter-like Approach

B Lemma 9 Statement and Proof

The appendix states and proves Lemma 9 using a labeled system and program-system convention. Its proof takes partial traces over the program systems.

B Lemma 9 Statement and Proof

C Proof of Theorem 6

The proof uses diamond-distance subadditivity, Taylor expansion, triangle inequalities, and a generalized Hölder inequality. Its conclusion invokes the theorem’s assumption.

C Proof of Theorem 6

D Proof of Lemma 7

The proof follows the steps of [15, Lemma I.4], adapted to bipartite vectors and their associated operators.

D Proof of Lemma 7

  • The proof adapts the steps of [15, Lemma I.4] to bipartite vectors and their associated operators.Source: D Proof of Lemma 7 · p. 54
  • For pure states, half the trace distance between their projectors equals the square root of one minus the squared magnitude of their inner product.Source: D Proof of Lemma 7 · p. 55
  • An inequality in the derivation is justified by Cauchy–Schwarz for the Hilbert–Schmidt inner product.Source: D Proof of Lemma 7 · p. 55

Related papers

Loading 2309.14453v1…