Quantum algorithms based on quantum trajectories

1. Problem Statement

The paper addresses the challenge of simulating open quantum systems governed by the Lindblad master equation:
$$\frac{d\rho}{dt} = -i[H, \rho] + \sum_{\mu=1}^m \left( L_\mu \rho L_\mu^\dagger - \frac{1}{2} \{L_\mu^\dagger L_\mu, \rho\} \right)$$
where $H$ is the system Hamiltonian and $\{L_\mu\}$ are the jump operators describing the interaction with a Markovian environment.

The Core Challenge:
While optimal algorithms for simulating closed systems (Hamiltonian simulation) have achieved an additive query complexity of $O(T + \log(1/\epsilon))$ (where $T$ is time and $\epsilon$ is precision), algorithms for open systems (Lindbladian simulation) have historically been limited to a multiplicative complexity of $O(T \cdot \text{polylog}(T/\epsilon))$. The open question was whether an additive complexity $O(T + \text{polylog}(1/\epsilon))$ is achievable for Lindbladian simulation, specifically regarding queries to the jump operators.

2. Methodology

The authors propose a novel quantum algorithm inspired by the Quantum Trajectories (Monte Carlo Wavefunction) method used in classical simulations. Instead of simulating the full density matrix evolution, the algorithm simulates individual stochastic pure-state trajectories and averages the results.

Key Technical Components:

• Constraint on Lindbladians: The algorithm targets a specific class of Lindbladians satisfying the condition:
  $$\sum_{\mu=1}^m L_\mu^\dagger L_\mu = \Gamma I$$
  for some constant $\Gamma > 0$. This condition implies that the "decay rate" is independent of the system state.
• Simplification of Dynamics: Under this constraint, the non-Hermitian effective Hamiltonian $\tilde{H} = H - \frac{i}{2}\sum L_\mu^\dagger L_\mu$ simplifies such that the deterministic evolution between jumps becomes a standard unitary evolution under $H$ (the decay factor becomes a global phase). Furthermore, the probability distribution of the time between jumps (holding time) becomes independent of the quantum state, following an exponential distribution $P(t_h \le \tau) = 1 - e^{-\Gamma \tau}$.
• Randomized Compilation:
  1. Sampling: The algorithm classically samples a sequence of holding times $\{t_h^{(i)}\}$ from the exponential distribution until the total time exceeds $T$. The number of jumps $N$ follows a Poisson distribution $N(T) \sim \text{Pois}(\Gamma T)$.
  2. Circuit Construction: A quantum circuit is compiled for a specific trajectory consisting of:
     • Unitary evolution blocks $K(t_h^{(i)})$ simulating $e^{-iHt}$.
     • Quantum channel blocks $L$ simulating the average jump map $J(\rho) = \sum_\mu \frac{L_\mu}{\sqrt{\Gamma}} \rho \frac{L_\mu^\dagger}{\sqrt{\Gamma}}$.
  3. Amplitude Amplification: To implement the jump channel $J$ deterministically (without post-selection failure), the authors use oblivious amplitude amplification. This boosts the success probability of the block-encoding implementation of the jump operators.

3. Key Contributions

1. Additive Query Complexity: The primary contribution is the construction of an algorithm that achieves a query complexity of $O(T + \frac{\log(1/\epsilon)}{\log\log(1/\epsilon)})$ to the jump operators. This is the first result to demonstrate that the additive lower bound (previously known only for Hamiltonian simulation) is reachable for a large class of Lindbladian simulations.
2. Optimality for Dissipative Systems: For purely dissipative Lindbladians (where $H=0$) satisfying the constraint, the algorithm achieves optimal query complexity with respect to time $T$.
3. Characterization of the Restricted Class: The paper rigorously characterizes the set of Lindbladians $\{L\}_c$ satisfying $\sum L_\mu^\dagger L_\mu = \Gamma I$.
   • It proves that this set is a strict subset of all Lindbladians (e.g., it cannot represent the amplitude damping channel directly).
   • It demonstrates that embedding an arbitrary Lindbladian into this restricted set via a larger system (subsystem simulation) is impossible. This implies that the algorithm cannot be used as a generic "black box" for all open systems; structural modifications would be required to generalize it.

4. Results and Complexity Analysis

The main theorem (Theorem 5) establishes the resource costs for simulating a Lindbladian satisfying the constraint with precision $\epsilon$ over time $T$:

• Jump Operator Queries: $O\left( \sqrt{\frac{\sum \alpha_\mu^2}{\Gamma}} \left( \Gamma T + \frac{\log(1/\epsilon)}{\log(e + \frac{\log(1/\epsilon)}{\Gamma T})} \right) \right)$.
  • This scales additively with $T$ and $\log(1/\epsilon)$.
• Hamiltonian Queries: $O\left( (\alpha + \Gamma)T \left[ \frac{\log((\alpha+\Gamma)T/\epsilon)}{\log(e + \dots)} \right]^2 \right)$.
  • Note: The Hamiltonian query complexity remains multiplicative (sub-optimal compared to the jump operator complexity), indicating a trade-off in the current approach.
• Ancilla Qubits: $O(\log m + a)$, where $m$ is the number of jump operators and $a$ is the ancilla count for block encoding.
• Gate Complexity: The 1- and 2-qubit gate count scales similarly to the query complexity but includes logarithmic factors related to the block encoding size.

Error Analysis:
The total simulation error is bounded by the sum of:

1. Truncation Error: The probability that the number of jumps exceeds the maximum allowed $r$ (bounded by the tail of the Poisson distribution).
2. Approximation Error: The error from approximating the unitary evolution and the jump channel (controlled by $\epsilon_H$).
   By setting the maximum number of jumps $r \approx \Gamma T + \log(1/\epsilon)$, the total error is kept within $O(\epsilon)$.

5. Significance and Future Directions

• Theoretical Breakthrough: This work resolves a significant open question in quantum complexity theory by showing that the "no-fast-forwarding" lower bound for open systems can be additive, matching the efficiency of closed-system simulation for jump operators.
• Practical Implications: The algorithm is applicable to many physically relevant systems, including Pauli channel dissipation, thermal state preparation, frustration-free Hamiltonian ground state preparation, and continuous-time error correction.
• Limitations: The requirement $\sum L_\mu^\dagger L_\mu = \Gamma I$ limits universality. The authors prove that arbitrary Lindbladians cannot be embedded into this class, suggesting that future work must focus on modifying the algorithm's structure rather than simple black-box embedding.
• Trade-offs: While jump operator complexity is optimal, Hamiltonian complexity is not yet additive. Future research directions include lifting the constraint on jump operators and improving the Hamiltonian query scaling.

In summary, the paper presents a trajectory-based quantum algorithm that leverages the statistical properties of Poisson-distributed quantum jumps to achieve additive query complexity for a significant class of open quantum systems, marking a major step forward in the efficiency of quantum simulation for dissipative dynamics.