Qi Zhao

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.

Quantum algorithms promise transformative speedups, yet their practical impact is often limited by prohibitively deep circuits, with two recurring sources of depth: costly preparation of structured input states and the execution of subroutines based on truncated series approximations. We introduce a unified, resource-efficient paradigm that uses classical randomness as an algorithmic primitive to improve accuracy–depth trade-offs. For realistic states with hierarchical amplitude structure, we propose a randomized state-preparation protocol that probabilistically amplifies small amplitudes using ensembles of low-complexity circuits, reducing the number of amplitudes that must be encoded and achieving up to 99% reductions in CNOT and T-gate counts in simulations on LiH wavefunctions and power-law decay states. Target quantum algorithms, we develop Randomized Truncated Series, a generic acceleration principle for any quantum algorithm built from truncated series, which quadratically suppresses truncation error while enabling continuous tuning of the effective truncation order via random mixing of shallow circuits. Together, these results broaden the regime where end-to-end quantum advantage is feasible on near-term and early fault-tolerant hardware.

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.

Simulating noiseless quantum dynamics classically faces a fundamental dilemma: tensor-network methods become inefficient as entanglement saturates, while Pauli-truncation approaches typically rely on noise or randomness. To close the gap, we propose the Low-weight Pauli Dynamics (LPD) algorithm that efficiently approximates local observables for short-time dynamics in the absence of noise. We prove that the truncation error admits an average-case bound without assuming randomness, provided that the state is sufficiently entangled. Counterintuitively, entanglement--usually an obstacle for classical simulation--alleviates classical simulation error. We further show that such entangled states can be generated either by tensor-network classical simulation or near-term quantum devices. Therefore, our results establish a rigorous synergy between existing classical simulation methods and provide a complementary route to quantum simulation that reduces circuit depth for long-time dynamics, thereby extending the accessible regime of quantum dynamics.