Inspired by classical Markov Chain Monte Carlo (MCMC) methods, dissipative quantum algorithms are an emerging class of methods for preparing quantum states on a quantum computer. They operate by simulating a dissipative process governed by a mathematical operator known as the Lindbladian. The performance of these algorithms can be limited by the sequential implementation of the Lindbladian's constituent jump operators, which leads to high circuit depth. To address this issue, this work analyzes a parallelization scheme to implement jump operators simultaneously. We leverage the structure of geometric locality to show that individual jump operators remain spatially localized. This exponentially reduces the circuit depth per time step, resulting in an overall polynomial improvement. Numerical experiments demonstrate a 53x reduction in query depth for a 1D benchmark system of 100 qubits. The reduced circuit depth makes dissipative algorithms more practical for near-term quantum computing.
Inspired by classical Markov Chain Monte Carlo (MCMC) methods, dissipative quantum algorithms are an emerging class of methods for preparing quantum states on a quantum computer. They operate by simulating a dissipative process governed by a mathematical operator known as the Lindbladian. The performance of these algorithms can be limited by the sequential implementation of the Lindbladian's constituent jump operators, which leads to high circuit depth. To address this issue, this work analyzes a parallelization scheme to implement jump operators simultaneously. We leverage the structure of geometric locality to show that individual jump operators remain spatially localized. This exponentially reduces the circuit depth per time step, resulting in an overall polynomial improvement. Numerical experiments demonstrate a 53x reduction in query depth for a 1D benchmark system of 100 qubits. The reduced circuit depth makes dissipative algorithms more practical for near-term quantum computing.
Simulating open quantum systems is an essential technique for understanding complex physical phenomena and advancing quantum technologies. Some quantum algorithms simulate Lindblad dynamics exponentially accurately, i.e., they achieve logarithmically short circuit depth in terms of accuracy, but they need to coherently encode all possible jump operators with a large ancilla consumption. Minimizing the gate and ancilla counts while achieving such a logarithmic scaling in accuracy remains an important challenge. In this work, we present two randomized quantum algorithms for simulating general Lindblad dynamics with multiple jump operators aimed at an observable estimation that achieves a circuit depth with not only logarithmic scaling in accuracy but also either partial or complete independence from the parameters specifying the Lindbladian. This is based on a novel random circuit compilation method that leverages dissipative processes with only a single jump operator, leading to the proposed methods using minimal ancilla qubits— 4 + ⌈ log 2 M ⌉ in the first case and seven in the other, where each single jump operator has at most M Pauli strings. In addition, we numerically demonstrate the practical advantage over existing approaches by providing a detailed analysis of the required gate and ancilla counts. This work represents a significant step toward making open quantum system simulations more feasible on early fault-tolerant quantum computing devices.
Simulating the dynamics of open quantum systems is a crucial task in quantum computing, offering wide-ranging applications but remaining computationally challenging. In this paper, we propose two quantum algorithms for simulating the dynamics of open quantum systems governed by Lindbladians. We introduce a new approximation channel for short-time evolution, inspired by the quantum trajectory method, which underpins the efficiency of our algorithms. The first algorithm achieves a gate complexity independent of the number of jump operators, m , marking a significant improvement in efficiency. The second algorithm achieves near-optimal dependence on the evolution time t and precision ϵ and introduces only an additional O ~ ( m ) factor, which strictly improves upon state-of-the-art gate-based quantum algorithm that has an O ~ ( m 2 ) factor. The improvement stems from the integration of the new approximation channel with a novel structured linear combination of unitaries method. In both our algorithms, the reduction of dependence on m significantly enhances the efficiency of simulating practical dissipative processes characterized by a large number of jump operators.
Open-system dynamics govern decoherence, transport, and engineered dissipation in quantum many-body systems. We propose a quantum algorithm for simulating time-independent, finite-range Lindblad dynamics with bounded local strength on a constant-dimensional lattice of n sites, allowing noncommuting jump operators. For time T≥1 and diamond-norm error at most ε, it has depth O(Tpolylog(nT/ε)) and gate count O(nTpolylog(nT/ε)). These results extend the HHKL spatial decomposition to open systems. The main obstacle is that the reversible overlap corrections used for unitary dynamics have no direct analogue for dissipative channels. We overcome this by retaining the environment in a shared unitary dilation, keeping information lost from the system coherently available and making the spatial corrections reversible. We prove exponential occupation bounds for the environmental states generated by the decomposition, allowing compact representation and coherent simulation of local factors on the inputs that arise. The construction reduces each short-time evolution to a constant number of parallel layers on regions of logarithmic diameter, using nearest-neighbour gates and polylogarithmic auxiliary density.
We also prove unconditional worst-case lower bounds using time-independent, purely dissipative processes that transport quantum information. For circuits with local quantum and classical communication, the lower bounds are Ω(nT) for the expected gate count and Ω(T) for depth on time scales up to the lattice diameter. They match the upper bounds' leading time and volume dependence up to polylogarithmic factors. At fixed time and sufficiently small fixed error, we further prove a depth lower bound of Ω(logn/loglogn), showing that global accuracy can require increasing depth as the lattice grows.
Abstract Dissipative engineering is a powerful tool for quantum state preparation, and has drawn significant attention in quantum algorithms and quantum many-body physics in recent years. In this work, we introduce a novel approach using the Lindblad dynamics to efficiently prepare the ground state for general ab initio electronic structure problems on quantum computers, without variational parameters. These problems often involve Hamiltonians that lack geometric locality or sparsity structures, which we address by proposing two generic types of jump operators for the Lindblad dynamics. Type-I jump operators break the particle number symmetry and should be simulated in the Fock space. Type-II jump operators preserves the particle number symmetry and can be simulated more efficiently in the full configuration interaction space. For both types of jump operators, we prove that in a simplified Hartree-Fock framework, the spectral gap of our Lindbladian is lower bounded by a universal constant. For physical observables such as energy and reduced density matrices, the convergence rate of our Lindblad dynamics with Type-I jump operators remains universal, while the convergence rate with Type-II jump operators only depends on coarse grained information such as the number of orbitals and the number of electrons. To validate our approach, we employ a Monte Carlo trajectory-based algorithm for simulating the Lindblad dynamics for full ab initio Hamiltonians, demonstrating its effectiveness on molecular systems amenable to exact wavefunction treatment.
Parallel computation enables multiple processors to execute different parts of a task simultaneously, improving processing speed and efficiency. In quantum computing, parallel gate implementation involves executing gates independently in different registers, directly impacting the circuit depth, the number of sequential quantum gate operations, and thus the algorithm execution time. This work examines a method for reducing circuit depth by introducing auxiliary qubits to enable parallel gate execution, potentially enhancing the performance of quantum simulations on near-term quantum devices. We show that any circuit on n qubits with depth O(Mn2), where M=M(n) is some function of n, can be transformed into a circuit with depth O(log2(M)n2) operating on O(Mn) qubits. This technique may be particularly useful in noisy environments, where recent findings indicate that only the final O(logn) layers influence the expectation value of observables. It may also optimize Trotterization by exponentially reducing the number of Trotter steps. Additionally, the method may offer advantages for distributed quantum computing, and the intuition of treating quantum states as gates and operators as vectors used in this work may have broader applications in quantum computation.
Simulating the dynamics of dissipative quantum many-body systems governed by local Lindbladians is a fundamental task in quantum computation. While the near-optimal gate count has been achieved for Hamiltonian simulation, comparable results for Lindbladian simulation remain elusive. In this work, we develop quantum algorithms for lattice Lindbladians by exploiting their locality. First, we consider sparsely dissipative systems, in which the dissipation is sparsely located, including boundary-driven systems. We establish a near-optimal quantum algorithm for their dynamics with gate count O(Ntpolylog(Nt/ε)), where N is the system size, t is the evolution time, and ε is the allowable error. We then consider generic lattice Lindbladians with finite-range interactions and dissipation, and develop an algorithm for simulating time-evolved observables with gate count O((Nt)4/3polylog(Nt/ε)) per sample with the sampling complexity Θ(ε−2). The gate count has the smallest known dependence on the system size among algorithms retaining polylogarithmic dependence on 1/ε. Our algorithms are based on two techniques that exploit locality: patching and merging. Patching decomposes dissipative dynamics into dynamics on subsystems with exponentially small error, generalizing a key idea underlying the Haah-Hastings-Kothari-Low algorithm for near-optimal Hamiltonian simulation. Merging absorbs reversed dissipative dynamics into other parts of the evolution, substantially reducing the overhead associated with quasi-probabilistic sampling. These results demonstrate that locality can be fully exploited to achieve fast quantum simulation of dissipative many-body dynamics, opening the way to applications such as predicting nonequilibrium phenomena and preparing desirable quantum states.