PaperlayerView exact revision on arXiv

Source-linked AI summary

Single-ancilla ground state preparation via Lindbladians

Zhiyan Ding, Chi-Fang Chen, Lin Lin

arXiv:2308.15676v4quant-ph

TL;DR

Ground-state preparation remains a bottleneck for quantum simulation, and existing approaches can require restrictive overlap assumptions or intricate control. This paper constructs a Monte Carlo-style Lindbladian with the ground state as a fixed point and simulates it using one ancilla qubit. The method avoids post-selection, while convergence depends on mixing time and the discrete-time variant can reduce simulation cost.

  • Problem

    Ground-state preparation is a bottleneck for end-to-end quantum simulation, and Gibbs-state approaches can require intricate control while common guarantees rely on suitable initial-state overlap.

    Source: §I · p. 2

  • Method

    The paper constructs an algorithmic Lindbladian with a single jump operator that makes the ground state a fixed point, and simulates its continuous-time evolution using one ancilla qubit.

    Source: §II · p. 2

  • Results

    The Lindblad evolution uses a CPTP map without post-selection, while numerical observations indicate comparable mixing times for continuous and discrete dynamics and reduced total Hamiltonian simulation time for the discrete version.

    Source: §II · p. 2, II.3. Simulating discrete-time… · p. 4

  • Takeaways & Limitations

    The discrete-time reformulation offers a route to reduced simulation cost while retaining the ground state as a stationary state.

    Source: II.3. Simulating discrete-time… · p. 4

    Other fixed points may exist, ergodicity is not guaranteed, and mixing time can vary by system.

    Source: §IV · p. 8

Abstract

from arXiv · show

We design a quantum algorithm for ground state preparation in the early fault tolerant regime. As a Monte Carlo-style quantum algorithm, our method features a Lindbladian where the target state is stationary. The construction of this Lindbladian is algorithmic and should not be seen as a specific approximation to some weakly coupled system-bath dynamics in nature. Our algorithm can be implemented using just one ancilla qubit and efficiently simulated on a quantum computer. It can prepare the ground state even when the initial state has zero overlap with the ground state, bypassing the most significant limitation of methods like quantum phase estimation. As a variant, we also propose a discrete-time algorithm, demonstrating even better efficiency and providing a near-optimal simulation cost depending on the desired evolution time and precision. Numerical simulation using Ising and Hubbard models demonstrates the efficacy and applicability of our method.

I. INTRODUCTION

Ground-state preparation is a bottleneck for end-to-end quantum simulation, while common approaches rely on a suitable initial-state overlap or careful Gibbs-state preparation. The paper asks whether an algorithmic Lindbladian can prepare ground states in the early fault-tolerant regime, with cost governed by simulation and mixing time.

I. INTRODUCTION

  • Few-body ground states can be QMA-hard to prepare, and common guarantees assume an efficiently prepared state with inverse-polynomial ground-state overlap.Choosing such a trial state can be instance-dependent and nontrivial to justify in practical systems.Source: §I · p. 1
  • Monte Carlo-style quantum algorithms seek to reproduce cooling principles, but the required system-bath coupling and bath size remain unclear.The paper treats Lindblad dynamics as an algorithmic construction, not necessarily an approximation to natural weakly coupled system-bath dynamics.Source: §I · p. 1
  • Gibbs-state preparation requires detailed balance between heating and cooling rates, while existing simulation methods use intricate block encodings and control circuits.The latter methods assume fully fault-tolerant computers, motivating simplification when logical qubits are limited.Source: §I · p. 2
  • The guiding question is whether a Monte Carlo-style ground-state algorithm can operate in the early fault-tolerant regime with near-optimal cost in evolution time T and precision ϵ.The relevant cost is simulation cost per unit time multiplied by mixing time; the authors do not expect efficient solutions to QMA-hard problems in general.Source: §I · p. 2

II. MAIN RESULTS

The paper proposes a single-jump-operator Lindbladian whose ground state is stationary, along with single-ancilla simulation and a discrete-time variant. Its CPTP evolution shovels high-energy components downward without post-selection, though convergence depends on mixing time.

II. MAIN RESULTS

  • A single jump operator makes the ground state a fixed point, and the continuous-time evolution can be simulated with one ancilla qubit and minimal control logic.The jump operator is built from Heisenberg evolutions of a coupling operator weighted by a filter function, and its choice is algorithmic.Source: §II · p. 2
  • The jump operator is designed to shovel high-energy components toward lower energies through a CPTP map, avoiding post-selection and its zero-overlap failure mode.The required mixing time can vary by system, and analysis of these strategies remains at an early stage.Source: §II · pp. 2–3
  • The circuit uses one ancilla qubit, discards its measurement result, and resets it to |0⟩ after each measurement.Continuous- and discrete-time circuit structures are similar; their main difference is the time-step size.Source: Figure 1 · p. 3

II.1. Correctness

The filter condition makes the jump operator forbid energy increments and favor energy decreases. This ensures that the ground state is an exact fixed point, whether or not the coherent Hamiltonian term is included.

II.1. Correctness

  • The filter condition makes ⟨ψi|K|ψj⟩ vanish when λi ≥ λj, so the jump operator forbids energy increments and favors decreases.The passage states that the filter function is weighted by energy differences and should be real and nonnegative.Source: II.1. Correctness · p. 3
  • The dissipative term fixes the ground-state projector, and the Hamiltonian term also fixes it, making the projector stationary under the full Lindblad dynamics.The fixed-point property remains valid with or without the coherent part; numerical findings suggest that including it can significantly reduce mixing time.Source: II.1. Correctness · p. 3

II.2. Simulating continuous-time Lindblad dynamics

The section presents a single-ancilla algorithm for continuous-time Lindblad simulation, addressing the substantial ancilla requirements of existing block-encoding approaches. Its complexity scales approximately as T^2/ϵ.

II.2. Simulating continuous-time Lindblad dynamics

  • The approach avoids block-encoding K and extra ancillas, using controlled-A rather than controlled Hamiltonian simulation.The authors identify Hamiltonian simulation as the most resource-intensive component; it may be further Trotterized for end-to-end cost analysis.Source: II.2. Simulating continuous-time… · pp. 3–4
  • Theorem 1 establishes continuous-time Lindblad simulation using one ancilla qubit for any Hamiltonian H and coupling operator A.The theorem states a cost in total Hamiltonian simulation time for simulation time T and precision ϵ, but the supplied passage omits the full expression.Source: II.2. Simulating continuous-time… · p. 3
  • The algorithm’s complexity scales approximately as T^2/ϵ, with a reasonable evolution time choice of the mixing time.The cost is quantified by total Hamiltonian simulation time; the authors note that implementing the dissipative evolution with one ancilla requires a nontrivial argument.Source: II.2. Simulating continuous-time… · p. 4

II.3. Simulating discrete-time Lindblad dynamics

The section recasts the update as discrete-time Lindblad dynamics with a step τ = O(1), for which the ground state remains stationary. This variant has improved simulation-cost scaling, while its effective mixing time may differ from the continuous-time case.

II.3. Simulating discrete-time Lindblad dynamics

  • At step size τ = O(1), the discretized dynamics keeps the ground state stationary and its simulation cost depends on ∆^-1 rather than linearly on ||H||/∆.The passage notes that this can be significantly faster for large-scale systems or Hamiltonians with unbounded operators.Source: II.3. Simulating discrete-time… · p. 4
  • Theorem 2 gives a one-ancilla algorithm for simulating the discrete-time Lindblad dynamics.The supplied theorem passages do not include the complete cost expression.Source: II.3. Simulating discrete-time… · p. 4
  • The discrete-time algorithm’s total Hamiltonian simulation time scales nearly linearly with T and sub-polynomially with 1/ϵ.The sub-polynomial precision dependence uses a high-order Trotter formulation; its preconstant scales exponentially with the order p.Source: II.3. Simulating discrete-time… · p. 4
  • The discrete dynamics’ effective mixing time may differ from the continuous-time mixing time, although numerical observations indicate they can be comparable.In those observations, the discrete-time version requires significantly less total Hamiltonian simulation time and cost.Source: II.3. Simulating discrete-time… · p. 4

III. DETAILS OF SIMULATING LINDBLAD DYNAMICS

The method draws on thermal-state preparation work but simplifies its detailed-balance condition for ground-state preparation. The section outlines a three-step simulation plan, focusing on the continuous-time case and leaving discrete-time details to an appendix.

III. DETAILS OF SIMULATING LINDBLAD DYNAMICS

  • For ground-state preparation, the quantum detailed-balance condition can be simplified to an energy-reduction condition.The construction is inspired by thermal-state preparation work using jump operators indexed by a and ω; their rates depend on temperature through f and γ.Source: §III · p. 4
  • The simulation is organized into three steps, with the section focusing on continuous-time dynamics and deferring discrete-time details to Appendix C..Source: §III · p. 4

Step 1: first-order Trotter splitting

The section uses first-order Trotter splitting to separate coherent Hamiltonian evolution from the dissipative Lindblad component. Extending this approach to higher order is nontrivial because dissipative evolution is not generally reversible and single-ancilla simulation adds another source of first-order error.

Step 1: first-order Trotter splitting

  • First-order Trotter splitting approximates the dynamics by alternating Hamiltonian and dissipative evolutions over a time step τ.The Hamiltonian component is simulated directly, leaving the short-time dissipative evolution as the main focus.Source: Step 1: first-order Trotter splitting · pp. 4–5
  • Higher-order splitting is not directly applicable because simulating exp(-L_Kτ) is not physically realizable as a CPTP map.The standard approach requires this inverse evolution to achieve order higher than two.Source: Step 1: first-order Trotter splitting · p. 5
  • Single-ancilla simulation of the dissipative step creates another source of first-order scaling, making higher-order extensions nontrivial.The passage also notes that a recent alternative approach requires block encoding of the jump operator K.Source: Step 1: first-order Trotter splitting · p. 5

problem

The Lindblad step is implemented by dilating its jump operator with one ancilla, then tracing out and resetting that ancilla. Discretization and second-order Trotterization make the construction simulable, while cancellation reduces repeated Hamiltonian evolution.

III.3. Step 3: Simulation of exp

  • A single-ancilla dilation approximates each Lindblad step through Hamiltonian simulation, ancilla trace-out, and reset.The trace-out can use measure-and-discard; the per-step error is O(τ^2).Source: problem · p. 5

Second-order Trotter splitting

  • Second-order Trotterization gives O(τ^2) local truncation error, whereas first-order splitting would yield O(τ) local error and O(1) global error.Higher-order formulas do not improve accuracy beyond the Lindbladian-simulation bound, so second order is adequate here.Source: problem · pp. 5–7

Discretizing the time integral

  • The time integral is truncated and uniformly discretized, with a trapezoidal rule; rapid decay of f(s) controls quadrature error.The analysis assumes a smooth filter with Gevrey structure, which ensures super-polynomial decay in time.Source: problem · p. 6

Canceling out back-and-forth Hamiltonian evolution

  • Consecutive Heisenberg-evolution factors nearly cancel, and long-time Hamiltonian evolutions cancel exactly between steps.Removing those long-time operations reduces the system-Hamiltonian simulation cost of W(τ).Source: problem · p. 7

Single-ancilla simulation

  • The implementation may include a coherent term because omitting it can leave the algorithm stuck at other fixed points in numerical observations.The dissipative part alone still fixes the ground state.Source: problem · p. 7

IV. ERGODICITY AND MIXING TIME WITH RANDOM COUPLING MATRIX

This section considers ergodicity and mixing for a Lindbladian with a single jump operator. Under a random-coupling assumption, it establishes uniqueness of the ground-state fixed point in expectation, while noting that mixing behavior is system-dependent.

Ergodicity

  • A single jump operator can leave other fixed points, and choosing A to ensure ergodicity is generally case-dependent.Existing sufficient conditions for irreducibility and ergodicity generally do not apply to this single-jump, rank-one-fixed-point setting.Source: §IV · p. 8

Random coupling matrix

  • The analysis assumes independent, zero-mean off-diagonal matrix elements of a random Hermitian coupling, filter support across ground-to-excited energy differences, and a diagonal initial state.These are the stated components of Assumption 6.Source: §IV · p. 8

Ergodicity

  • Under Assumption 6, the ground state is the unique fixed point in expectation, so expected observables converge to their ground-state values.The expectation is over the randomness of A; it is not itself the density operator stored in quantum memory.Source: §IV · p. 8

Mixing time

  • The mixing time is not known a priori and is expected to depend on the system; the paper gives a polynomial-mixing argument only under additional assumptions.The authors do not make mixing-time analysis their primary objective.Source: §IV · p. 8

V. NUMERICAL RESULTS

Numerical simulations test continuous- and discrete-time Lindblad dynamics on TFIM-4, TFIM-6, and a Hubbard model. Both variants prepare ground states in the reported tests, while the discrete-time variant uses substantially less Hamiltonian simulation time in the two TFIM cases.

V. NUMERICAL RESULTS

  • The numerical tests use TFIM-4, TFIM-6, and a Hubbard model to evaluate algorithm efficiency.Each Lindblad simulation is repeated 100 times in the stated TFIM and Hubbard setups.Source: §V · p. 9, §V.1 · p. 9, §V.2 · p. 9

V.1. TFIM-4 model; V.2. TFIM-6 model

  • Across TFIM-4 and TFIM-6, both dynamics prepare ground states from zero-overlap initial states, while discrete-time simulation uses about one-tenth the Hamiltonian simulation time.The TFIM-4 comparison reports one order of magnitude less; TFIM-6 reports almost one-tenth.Source: §V.1 · p. 9, §V.2 · p. 9, Figure 4 · p. 10

V.2. TFIM-6 model

  • The continuous and discrete TFIM-6 trajectories differ noticeably, yet both prepare the ground state with comparable mixing times.The discrete-time setting uses τ = 1 and r = 2, versus τ = 0.1 for continuous time.Source: §V.2 · p. 9, Figure 5 · p. 11

V.3. Hubbard model

  • For Hubbard-4, both continuous- and discrete-time dynamics decrease energy to λ0 and increase ground-state overlap to 1.The simulations report fast convergence and accurate ground-state construction.Source: §V.3 · p. 10, Figure 6 · p. 11

VI. DISCUSSION

  • Mixing time, coupling-matrix choice, and filter choice may depend on the system, and mixing time is not known a priori.The authors also note that required Hamiltonian simulation time, and consequently circuit depth, may exceed device capabilities.Source: §VI · pp. 11–12

Appendix B: Choice of filter function

The appendix develops filter-function conditions for controlling quadrature error, then describes one-ancilla discrete-time Lindblad simulation and analyzes its costs. The discrete-time formulation permits larger steps while preserving the ground state as a fixed point, with higher-order splitting improving the cost scaling.

Appendix B: Choice of filter function

  • Gevrey-based filter assumptions yield superpolynomial time-domain decay and logarithmic dependence of the filter’s L1 norm on the gap.The Gevrey assumption also simplifies the quadrature-error analysis.Source: Appendix B · pp. 16–17

Appendix C: Discrete-time Lindblad dynamics with one ancilla qubit

  • The circuit discards the ancilla measurement result and resets the ancilla to |0⟩ after each measurement; the segment count r controls Trotter error.The step size τ can be independent of precision ϵ.Source: Figure 7 · p. 19
  • The discrete-time dynamics uses a large step τ even when the resulting state does not track the exact continuous trajectory, relying instead on the ground state remaining fixed for any τ.If the discrete mixing time is not much larger than the continuous mixing time, larger τ can reduce simulation cost.Source: Appendix C · p. 19

D.1. Simulation cost of continuous-time Lindblad dynamics

  • The continuous-time simulation cost analysis gives a Hamiltonian-simulation-time bound and states that this cost is independent of the integral-discretization step size τs.The short-time Lindblad simulation method, rather than the Trotter splitting, limits the continuous-time scheme to first-order accuracy.Source: §D.1 · p. 20

D.2. Simulation cost of discrete-time Lindblad dynamics

  • The discrete-time analysis identifies second-order Trotter splitting as the accuracy bottleneck, while p-th order splitting can improve the asymptotic scaling to nearly linear in T.The second-order method is often sufficient in practical scenarios with τ = O(1) and r = O(1).Source: §D.2 · pp. 20–21

D.3. Proof of Lemma 3

  • The one-ancilla simulation lemma traces out the ancilla after dilated evolution, and odd powers of O(t^1/2) vanish under that partial trace.The lemma formulates the reduced system state and its Lindblad evolution from the dilated propagator.Source: §D.3 · p. 21

D.4. Proof of Theorem 18

The appendix derives continuous- and discrete-time simulation bounds by separating simulation, numerical-integration, and Trotter-splitting errors. It also gives conditional convergence results and notes a worst-case exponential dependence on qubit count for a trajectory-to-deterministic-dynamics bound.

D.4. Proof of Theorem 18

  • eΘ(T^2 ϵ^-1) is the total Hamiltonian simulation time derived for the continuous-time algorithm.The proof separates Lindblad-simulation, numerical-integration, and Trotter-splitting errors.Source: §D.4 · pp. 22, 24

D.5. Proof of Theorem 19 and Corollary 20

  • The total time is number of steps × (τ + rΘ(S_s)) = Θ(T + rTS_sτ^(-1)) = eΘ(T^(3/2)ϵ^(-1/2)); the p-order expression is eΘ(T^(1+1/p)ϵ^(-1/p)).Source: §D.5 · p. 26

Appendix E: Convergence under ETH type ansatz

  • Under appropriate assumptions, the continuous-time dynamics rapidly drives the state toward low-energy eigenstates; with the stated sub-transition-matrix mixing assumption, ground-state preparation has polynomial mixing time.After that mixing time, the ground-state overlap is Ω(1).Source: Appendix E · p. 27

E.1. Proof of Theorem 7 and Theorem 26

The appendix establishes the ground state as a fixed point and proves uniqueness and convergence under its stated assumptions. It also gives a polynomial-mixing result under additional conditions and discusses a worst-case limitation for concentration around deterministic dynamics.

E.1. Proof of Theorem 7 and Theorem 26

  • Because the filter vanishes for nonnegative frequencies, the ground state is a fixed point of the Lindblad dynamics.The proof further concludes that, under the stated assumptions, it is the unique fixed point and the dynamics converges to it as t → ∞.Source: §E.1 · pp. 27, 29

E.2. Concentration around deterministic dynamics

  • Theorem 27 addresses concentration of a single trajectory around deterministic dynamics when the scheme has at least first-order accuracy.The supplied theorem statement also defines a bound parameter using the supported random-operator distribution.Source: §E.2 · p. 30
  • In the worst case, the upper bound on the trace-norm difference between the trajectory and expected state depends exponentially on qubit count n.The passage notes that whether this bound can be improved remains open.Source: §E.2 · p. 30

Related papers

Loading 2308.15676v4…