Sublinear thermal state and ground state preparation for free fermions via system-bath interaction

Technical Summary: Sublinear Thermal and Ground State Preparation for Free Fermions via System-Bath Interaction

Problem Statement
The preparation of thermal (Gibbs) and ground states is a foundational challenge in quantum simulation. While dissipative algorithms—using controlled interactions with an environment (bath) to drive a system toward a target state—have shown promise, existing approaches typically require a total Hamiltonian simulation time that scales at least linearly with the system size $N$. This linear barrier arises because local dissipative transitions must collectively act on all $N$ qubits to drive an arbitrary initial state to the target. Even for free fermion systems, which are classically simulable, establishing quantum algorithms with sublinear simulation time remains a significant theoretical benchmark for understanding the limits of dissipative state preparation.

Methodology
The authors propose a system-bath interaction framework that overcomes the linear-in-$N$ barrier for free fermions by engineering an "extensive" bath, where the number of bath qubits scales proportionally with the system size ($\Theta(N)$).

1. System-Bath Framework: The algorithm iteratively applies a quantum channel $\Phi_\alpha$ induced by a joint evolution of the system and bath, followed by tracing out the bath. The joint Hamiltonian is $H_\alpha(t) = H + H_E + \alpha H_{\text{int}}(t)$, where $H$ is the system Hamiltonian, $H_E$ is the bath Hamiltonian, and $H_{\text{int}}$ describes local couplings modulated by a filter function $f(t)$.
2. Decoupling Strategy: To manage the perturbation errors introduced by $\Theta(N)$ simultaneous couplings, the authors utilize a transformation that decomposes the total system-bath Hamiltonian into $N$ independent fermionic modes. This allows for the analysis of perturbation errors on a mode-by-mode basis using the fermionic tensor-product structure, enabling a larger coupling strength $\alpha$ and achieving sublinear complexity.
3. Two Bath Protocols:
   • Zero-Bath Setting: The bath Hamiltonian $H_E = 0$. This setting is used for thermal state preparation.
   • Random-Bath Setting: The bath Hamiltonian $H_E$ involves a randomly sampled frequency $\omega$. This setting is used for ground state preparation, offering greater flexibility in filter design.

Key Contributions and Results

1. Sublinear Thermal State Preparation
For free fermions with bounded single-particle bandwidth, the authors present an algorithm that prepares the thermal state $\sigma_\beta$ with trace-norm error $\epsilon$ in total simulation time:
$$T_{\text{total}} = \tilde{O}(\sqrt{N}/\epsilon)$$
This represents a polynomial improvement over existing dissipative approaches (which scale as $\tilde{O}(N)$). The algorithm works for arbitrary initial states and relies on the zero-bath setting with a carefully designed filter function satisfying the Kubo–Martin–Schwinger (KMS) detailed-balance condition.

2. Polylogarithmic Ground State Preparation
For gapped free fermion systems with spectral gap $\Delta > 0$, the ground state preparation complexity is significantly improved to:
$$T_{\text{total}} = \tilde{O}(\Delta^{-2} \text{polylog}(N/\epsilon))$$
This nearly optimal dependence on $N$ is achieved using the random-bath setting. The analysis requires going beyond the conventional Lindblad approximation, accounting for all higher-order terms in the Dyson expansion to ensure the target state is preserved without introducing system-size dependencies.

3. Lower Bounds and Design Constraints
The paper establishes rigorous lower bounds that identify fundamental obstacles to further complexity improvements within these protocols:

• Zero-Bath Limit: Achieving complexity better than $\tilde{O}(\sqrt{N}/\epsilon)$ requires the filter function to satisfy detailed balance conditions not just at leading order, but also for fourth-order terms in the interaction strength $\alpha$. It remains an open question whether such filter functions exist.
• Random-Bath Limit: While the random frequency allows for flexibility, the paper proves that if the detailed balance condition holds only on average over the frequency distribution (rather than for almost every realization), the complexity reverts to linear scaling, $\Omega(N/\epsilon)$. The randomness introduces fluctuations that prevent the joint state from being a product state, even if single-qubit marginals are correct. This obstruction is absent in ground state preparation, where the target is a pure product state uniquely determined by marginals.

Significance and Claims
The authors claim that their results demonstrate the linear simulation time barrier in dissipative state preparation can be overcome for free fermions. By employing an extensive bath, they achieve provable reductions in simulation time while retaining local interactions and convergence from arbitrary initial states.

The work clarifies the specific design constraints governing complexity improvements:

• For thermal states, the need to control fourth-order deviations and the limitations of shared randomness in the bath are identified as the primary bottlenecks.
• For ground states, the random-bath setting allows the algorithm to fully exploit the bath's flexibility, achieving polylogarithmic scaling.

The paper positions free fermions as a controlled testbed for exploring dissipative algorithms. While acknowledging that free fermions are classically simulable, the authors argue that establishing rigorous, sublinear quantum complexity guarantees for this benchmark is crucial for understanding the potential of dissipative methods in more general, interacting quantum systems. They note that while recent work [30] achieves polylogarithmic time for ground states via coherent transport rather than dissipative mixing, their work specifically addresses the relaxation-based mechanism, highlighting the distinct challenges and constraints inherent to dissipative protocols.