Technical Summary: Faster Quantum Simulation of Markovian Open Quantum Systems Via Randomisation

Problem Statement

The simulation of Markovian open quantum systems (OQS) on quantum computers requires approximating the dynamical evolution governed by the Gorini-Kossakowski-Sudarshan-Lindblad (GKSL) master equation. A critical constraint is that the simulation must preserve the physicality of the evolution, meaning the approximating map must be Completely Positive and Trace Preserving (CPTP).

While Trotter-Suzuki (TS) product formulas are standard for closed systems, their application to OQS is limited. First and second-order deterministic TS formulas guarantee CPTP approximations, but higher-order deterministic formulas often fail this requirement due to recursive constructions involving negative time steps, which do not yield CPTP maps for Lindbladians. Conversely, existing probabilistic algorithms for OQS, while offering improved precision and gate complexity, introduce a non-zero probability of failure. There remains a need for non-probabilistic algorithms that offer improved scaling in gate complexity and precision without sacrificing the CPTP nature of the evolution or relying on complex subroutines with significant overhead.

Methodology

The authors introduce novel non-probabilistic algorithms that leverage randomisation to simulate Markovian OQS. The core methodology involves three distinct approaches, all implemented using Classical Sampling (CS) to construct gate sets from discrete distributions:

1. Randomised First-Order TS Formula:

   • Instead of a fixed ordering of constituent channels (as in deterministic TS), this method constructs a convex combination of the forward ($S_1^\rightarrow$) and reversed ($S_1^\leftarrow$) first-order product formulas.
   • $S_1^{(ran)}(\tau) = \frac{1}{2}(S_1^\rightarrow(\tau) + S_1^\leftarrow(\tau))$.
   • The implementation uses a classical oracle to randomly select between the forward and reversed orderings for each time step.

2. Randomised Second-Order TS Formula:

   • This method generalizes the randomisation to the second order by taking a convex combination over all permutations $\sigma \in \text{Sym}(M)$ of the constituent generators.
   • $S_2^{(ran)}(\tau) = \frac{1}{M!} \sum_{\sigma \in \text{Sym}(M)} S_\sigma^2(\tau)$.
   • The implementation samples a permutation uniformly at random for each time step.

3. QDRIFT Channel for OQS:

   • Inspired by the QDRIFT protocol for Hamiltonian simulation, this method probabilistically applies constituent channels $e^{\omega L_k}$ with probability $p_k = \gamma_k / \Gamma$, where $\Gamma = \sum \gamma_k$ is the total decay rate.
   • The channel is defined as $\mathcal{E}_\omega^{(QD)}(\rho) = \sum_{k=1}^M p_k e^{\omega L_k}$.
   • Unlike the TS formulas, the gate complexity of this method is independent of the number of generator terms $M$ in its explicit formula, depending instead on the total rate $\Gamma$.

Key Technical Distinction:
A significant methodological contribution is the derivation of error bounds for these randomised OQS simulations without relying on the mixing lemma (Campbell and Hastings). The mixing lemma is specific to the geometry of unitary operators (Hamiltonian simulation) and does not apply to CPTP maps. The authors instead employ direct Taylor expansion and combinatorial arguments to bound the diamond norm error, proving that the randomised formulas achieve higher-order accuracy in the time step $\tau$ despite the non-unitary nature of the dynamics.

Key Results and Gate Complexity

The paper derives rigorous error bounds and step count limits ($N$) for a target precision $\epsilon$ and simulation time $t$. The gate complexity is defined as the total number of "simple channels" (constituent exponentials) required.

Let $M$ be the number of terms in the GKSL generator, $\Lambda = \max_k \|\hat{L}_k\|_\diamond$ (where $\hat{L}_k$ includes decay rates), and $\Omega = \max_k \|L_k\|_\diamond$ (rate-normalized generators).

• First-Order Deterministic TS: Scales as $O((t\Lambda)^2 M^3 / \epsilon)$.
• First-Order Randomised TS (CS): Scales as $O((t\Lambda)^{3/2} M^{5/2} / \sqrt{\epsilon})$.
  • Improvement: Matches the scaling of the second-order deterministic formula but with a simpler structure. It improves the dependence on $M$ from $M^3$ to $M^{5/2}$.
• Second-Order Deterministic TS: Scales as $O((t\Lambda)^{3/2} M^{5/2} / \sqrt{\epsilon})$.
• Second-Order Randomised TS (CS): Scales as $O((t\Lambda)^{3/2} M^2 / \sqrt{\epsilon})$.
  • Improvement: Achieves a quadratic dependence on $M$, significantly outperforming both deterministic and first-order randomised formulas.
• QDRIFT Channel (CS): Scales as $O((t\Gamma\Omega)^2 / \epsilon)$.
  • Improvement: The gate complexity has no explicit dependence on $M$, depending instead on the total rate $\Gamma = \sum \gamma_k$. However, this independence is conditional: since $\Gamma \le M \max_k \gamma_k$, the total rate grows linearly with $M$ whenever dissipation rates are comparable, in which case the QDRIFT channel scales similarly to deterministic TS formulas in $M$. The method offers a distinct advantage for systems where $\Gamma$ is small or remains bounded independently of $M$ (e.g., systems dominated by a few strong dissipators).

Significance and Claims

The authors claim that this work systematically extends powerful randomisation techniques from Hamiltonian simulation to the general setting of Markovian open quantum systems. The significance of the work is framed around three main points:

1. Non-Probabilistic Efficiency: The proposed methods are non-probabilistic (deterministic in their error bounds, though the circuit construction involves random sampling) and maintain the CPTP nature of the evolution, avoiding the failure probability associated with other probabilistic OQS algorithms.
2. Scalability: The randomised TS formulas offer improved scaling with respect to the number of generator terms $M$ compared to deterministic TS formulas. Specifically, the second-order randomised formula reduces the $M$-dependence to quadratic, and the QDRIFT channel removes explicit $M$-dependence (though conditional on the behavior of $\Gamma$).
3. Implementation Simplicity: The methods rely on Classical Sampling to construct gate sets, avoiding the complex subroutines (such as block-encodings or quantum signal processing) required by advanced deterministic algorithms that achieve near-linear scaling in time $t$. The authors argue that for early fault-tolerant quantum computers, the lower overhead and structural simplicity of these randomised methods make them a practical choice, particularly for systems with large $M$.

The paper explicitly notes that while the randomised methods have less favorable scaling in simulation time $t$ (quadratic or higher) compared to some advanced deterministic methods (near-linear), their polynomial improvement in $M$ and lower implementation overhead render them advantageous for specific scenarios, such as simulating large dissipative systems for short to moderate times.

The work concludes by identifying open problems, including the generalisation of the mixing lemma to CPTP maps, finding optimal convex mixtures for higher-order scaling, and extending these results to non-Markovian dynamics. It also highlights the challenge of extending to higher-order randomised formulas due to the non-CPTP nature of backward-time Lindbladian evolution ($e^{-tL}$).