Efficient simulation of sparse Markovian quantum dynamics
arXiv:1611.05543 · doi:10.26421/QIC17.11-12
Abstract
Quantum algorithms for simulating Hamiltonian dynamics have been extensively developed, but there has been much less work on quantum algorithms for simulating the dynamics of open quantum systems. We give the first efficient quantum algorithms for simulating Markovian quantum dynamics generated by Lindbladians that are not necessarily local. We introduce two approaches to simulating sparse Lindbladians. First, we show how to simulate Lindbladians that act within small invariant subspaces using a quantum algorithm to implement sparse Stinespring isometries. Second, we develop a method for simulating sparse Lindblad operators by concatenating a sequence of short-time evolutions. We also show limitations on Lindbladian simulation by proving a no-fast-forwarding theorem for simulating sparse Lindbladians in black-box models.
arXiv comment48 pages, 6 figures. v2: A complete proof of Proposition 2 is added
References in corpus (27)
- Elementary gates for quantum computation
- Quantum algorithm for solving linear systems of equations
- Optimal Hamiltonian Simulation by Quantum Signal Processing
- Simulating Hamiltonian dynamics with a truncated Taylor series
- Preparation of Entangled States by Quantum Markov Processes
- On the relationship between continuous- and discrete-time quantum walk
- Hamiltonian simulation with nearly optimal dependence on all parameters
- Quantum Metropolis Sampling
- Creating superpositions that correspond to efficiently integrable probability distributions
- The problem of equilibration and the computation of correlation functions on a quantum computer
- A positive tensor network approach for simulating open quantum many-body systems
- A Limit on the Speed of Quantum Computation in Determining Parity
- A dissipative quantum Church-Turing theorem
- A Quantum-Quantum Metropolis Algorithm
- Quantum stochastic walks: A generalization of classical random walks and quantum walks
- A random walk approach to quantum algorithms
- Quantum algorithm for simulating the dynamics of an open quantum system
- Quantum Navigation and Ranking in Complex Networks
- Simulating sparse Hamiltonians with star decompositions
- A Quantum Algorithm for the Hamiltonian NAND Tree
- Decoherence in Quantum Walks on the Hypercube
- Digital quantum simulation of many-body non-Markovian dynamics
- Simulation of single-qubit open quantum systems
- Efficient quantum circuits for arbitrary sparse unitaries
- Efficient Quantum Algorithms for Simulating Lindblad Evolution
- QSWalk: a Mathematica package for quantum stochastic walks on arbitrary graphs
- Reexamination of decoherence in quantum walks on the hypercube
Cited by in corpus (23)
- Quantum Chemistry in the Age of Quantum Computing
- Variational quantum simulation of general processes
- Collision models can efficiently simulate any multipartite Markovian quantum dynamics
- A general quantum algorithm for open quantum dynamics demonstrated with the Fenna-Matthews-Olson complex
- Quantum simulation of dissipative collective effects on noisy quantum computers
- Quantum flags, and new bounds on the quantum capacity of the depolarizing channel
- Causal limit on quantum communication
- Quantum Simulation of the Radical Pair Dynamics of the Avian Compass
- Quantum Algorithms for Open Lattice Field Theory
- On the distribution of the mean energy in the unitary orbit of quantum states
- Long-Time Error-Mitigating Simulation of Open Quantum Systems on Near Term Quantum Computers
- Efficient quantum algorithm to simulate open systems through a single environmental qubit
- QSW_MPI: a framework for parallel simulation of quantum stochastic walks
- Quantum State Discrimination on Reconfigurable Noise-Robust Quantum Networks
- Commutation simulator for open quantum dynamics
- Nonlinear Spectroscopy via Generalized Quantum Phase Estimation
- Bounding the quantum capacity with flagged extensions
- Quantum walks on hypergraphs
- Digital Quantum Simulations of the Non-Resonant Open Tavis-Cummings Model
- Quantum algorithms based on quantum trajectories
- A Randomized Method for Simulating Lindblad Equations and Thermal State Preparation
- Quantum Simulation of Two-Level -Symmetric Systems Using Hermitian Hamiltonians
- Quantum State Preparation and Non-Unitary Evolution with Diagonal Operators