Naixu Guo

Quantum phase estimation (QPE) and Lindbladian dynamics are both foundational in quantum information science and central to quantum algorithm design. In this work, we bridge these two concepts: certain simple Lindbladian processes can be adapted to perform QPE-type tasks. However, unlike QPE, which achieves Heisenberg-limit scaling, these Lindbladian evolutions are restricted to standard quantum limit complexity. This indicates that, different from Hamiltonian dynamics, the natural dissipative evolution speed of such Lindbladians does not saturate the fundamental quantum limit, thereby suggesting the potential for quadratic fast-forwarding. We confirm this by presenting a quantum algorithm that simulates these Lindbladians for time $t$ within an error $\varepsilon$ using $\mathcal{O}\left(\sqrt{t\log(\varepsilon^{-1})}\right)$ cost. This, to our knowledge, is the first example of Lindbladian fast forwarding, which shares a fundamentally different mechanism from the fast-forwarding examples of Hamiltonian dynamics. As a bonus, this fast-forwarded simulation naturally serves as a new Heisenberg-limit QPE algorithm. Therefore, our work explicitly bridges the standard quantum limit-Heisenberg limit transition to the fast-forwarding of dissipative dynamics. We also adopt our fast-forwarding algorithm for efficient Gibbs state preparation and demonstrate the counter-intuitive implication: the allowance of a quadratically accelerated decoherence effect under arbitrary Pauli noise.

Rare events, though infrequent, can have significant impacts across various domains. We present a quantum algorithm for efficiently sampling rare events from stochastic processes. Our algorithm constructs quantum sample states that superpose only rare events, defined as those occurring with probability below a threshold \(\Delta\). The algorithm consists of three key steps: (1) constructing an amplitude block encoding from the quantum sample state of the original process, (2) implementing quantum singular value transformation of a polynomial approximation of a thresholding function, and (3) performing measurement and post-selection. For sufficiently large sequence lengths, we prove that our algorithm achieves a quadratic speedup over classical methods, requiring only \(\Theta(1/\sqrt{\Delta})\) queries to prepare an even superposition over rare events, compared to the classical \(\mathcal{O}(1/\Delta)\) complexity. We demonstrate our algorithm's effectiveness through numerical simulations on the Dyson-Ising chain, showing successful identification and amplification of rare events while suppressing non-rare events.

Solving linear ordinary differential equations (ODE) is one of the most promising applications for quantum computers to demonstrate exponential advantages. The challenge of designing a quantum ODE algorithm is how to embed non-unitary dynamics into intrinsically unitary quantum circuits. In this work, we propose a new quantum algorithm for solving ODEs by harnessing open quantum systems. Specifically, we propose a novel technique called non-diagonal density matrix encoding, which leverages the inherent non-unitary dynamics of Lindbladians to encode general linear ODEs into the non-diagonal blocks of density matrices. This framework enables us to design quantum algorithms with both theoretical simplicity and high performance. Combined with the state-of-the-art quantum Lindbladian simulation algorithms, our algorithm can outperform all existing quantum ODE algorithms and achieve near-optimal dependence on all parameters under a plausible input model. We also give applications of our algorithm including the Gibbs state preparations and the partition function estimations.