Zhong-Xia Shang

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.

Classical simulation of quantum systems is fundamental to understanding the boundary between classical and quantum computing. The two leading approaches, tensor networks (TN) and the stabilizer formalism (SF), have traditionally been viewed as distinct, with seemingly disconnected sources of computational hardness. The complexity of TN methods is dictated by entanglement, while SF complexity is governed by the amount of "magic". This leads to a disconnect: states that are simple for one formalism can be maximally complex for the other. For instance, highly entangled stabilizer states are trivial for SF but can be intractable for TN methods. This raises a crucial question: Is there a unified framework or a single indicator that can diagnose the relationship between these two simulation paradigms? In this work, we provide such an indicator, which we term bra-ket entanglement (BKE). We investigate the classical simulation of the general process U OU†, where O can be any operator, from a quantum resource perspective. We show that BKE serves as a crucial diagnostic tool that reveals a deep connection between the resources governing TN and SF. Our central finding is that as the BKE of the initial operator O increases, the simulation resources required by the two approaches transition from being uncorrelated to being highly correlated.

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.