Document Open Access Logo

Efficient Quantum Algorithms for Simulating Lindblad Evolution

Authors Richard Cleve, Chunhao Wang

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2017.17.pdf
  • Filesize: 0.74 MB
  • 14 pages

Document Identifiers

Author Details

Richard Cleve
Chunhao Wang

Cite AsGet BibTex

Richard Cleve and Chunhao Wang. Efficient Quantum Algorithms for Simulating Lindblad Evolution. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 17:1-17:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.ICALP.2017.17

Abstract

We consider the natural generalization of the Schrodinger equation to Markovian open system dynamics: the so-called the Lindblad equation. We give a quantum algorithm for simulating the evolution of an n-qubit system for time t within precision epsilon. If the Lindbladian consists of poly(n) operators that can each be expressed as a linear combination of poly(n) tensor products of Pauli operators then the gate cost of our algorithm is O(t polylog(t/epsilon) poly(n)). We also obtain similar bounds for the cases where the Lindbladian consists of local operators, and where the Lindbladian consists of sparse operators. This is remarkable in light of evidence that we provide indicating that the above efficiency is impossible to attain by first expressing Lindblad evolution as Schrodinger evolution on a larger system and tracing out the ancillary system: the cost of such a reduction incurs an efficiency overhead of O(t^2/epsilon) even before the Hamiltonian evolution simulation begins. Instead, the approach of our algorithm is to use a novel variation of the "linear combinations of unitaries" construction that pertains to channels.
Keywords
  • quantum algorithms
  • open quantum systems
  • Lindblad simulation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. D. Aharonov and A. Ta-Shma. Adiabatic quantum state generation and statistical zero knowledge. In Proceedings of the 35th ACM Symposium on Theory of Computing, pages 20-29, 2003. URL: http://dx.doi.org/10.1145/780542.780546.
  2. D. W. Berry, A. M. Childs, R. Cleve, R. Kothari, and R. D. Somma. Exponential improvement in precision for simulating sparse Hamiltonians. In Proceedings of the 46th ACM Symposium on Theory of Computing, pages 283-292, 2014. http://arxiv.org/abs/arXiv:1312.1414, URL: http://dx.doi.org/10.1145/2591796.2591854.
  3. D. W. Berry, A. M. Childs, R. Cleve, R. Kothari, and R. D. Somma. Simulating Hamiltonian dynamics with a truncated Taylor series. Phys. Rev. Lett., 114:090502, Mar 2015. URL: http://dx.doi.org/10.1103/PhysRevLett.114.090502.
  4. D. W. Berry, A. M. Childs, and R. Kothari. Hamiltonian simulation with nearly optimal dependence on all parameters. In Proceedings of FOCS 2015, 2015. URL: http://arxiv.org/abs/arXiv:1501.01715.
  5. D. W. Berry, R. Cleve, and S. Gharibian. Gate-efficient discrete simulations of continuous-time quantum query algorithms. Quantum Information and Computation, 14(1-2):1-30, 2014. URL: http://arxiv.org/abs/arXiv:1211.4637.
  6. D. W. Berry and L. Novo. Corrected quantum walk for optimal Hhamiltonian simulation, 2016. arXiv:1606.03443. Google Scholar
  7. R. Di Candia, J. S. Pedernales, A. del Campo, E. Solano, and J. Casanova. Quantum simulation of dissipative processes without reservoir engineering. Sci. Rep., 5:9981, 2015. Google Scholar
  8. A. M. Childs. Quantum information processing in continuous time. PhD thesis, Massachusetts Institute of Technology, 2014. Google Scholar
  9. A. M. Childs and T. Li. Efficient simulation of sparse markovian quantum dynamics, 2016. arXiv:1611.05543. Google Scholar
  10. Richard Cleve and Chunhao Wang. Efficient quantum algorithms for simulating lindblad evolution. arXiv preprint arXiv:1612.09512, 2016. Google Scholar
  11. R. Dorner, J. Goold, and V. Vedral. Towards quantum simulations of biological information flow. Interface focus, page rsfs20110109, 2012. Google Scholar
  12. R. P. Feynman. Simulating physics with computers. International Journal of Theoretical Physics, 21(6-7):467-488, 1982. Google Scholar
  13. V. Gorini, A. Kossakowski, and E. C. G. Sudarshan. Completely positive dynamical semigroups of n-level systems. Journal of Mathematical Physics, 17:821-825, 1976. Google Scholar
  14. S. F. Huelga and M. B. Plenio. Vibrations, quanta and biology. Contemporary Physics, 54(4):181-207, 2013. Google Scholar
  15. M. J. Kastoryano and F. G. S. L. Brandao. Quantum gibbs samplers: the commuting case. Communications in Mathematical Physics, 344(3):915-957, 2016. Google Scholar
  16. M. J. Kastoryano, F. Reiter, and A. S. Sørensen. Dissipative preparation of entanglement in optical cavities. Physical review letters, 106(9):090502, 2011. Google Scholar
  17. M. Kliesch, T. Barthel, C. Gogolin, M. Kastoryano, and J. Eisert. Dissipative quantum church-turing theorem. Physical review letters, 107(12):120501, 2011. Google Scholar
  18. R. Kothari. Efficient algorithms in quantum query complexity. PhD thesis, University of Waterloo, 2014. Google Scholar
  19. B. Kraus, H. P. Büchler, S. Diehl, A. Kantian, A. Micheli, and P. Zoller. Preparation of entangled states by quantum markov processes. Physical Review A, 78(4):042307, 2008. Google Scholar
  20. A. J. Leggett, S. Chakravarty, A. T. Dorsey, M. P. A. Fisher, A. Garg, and W. Zwerger. Dynamics of the dissipative two-state system. Reviews of Modern Physics, 59(1):1, 1987. Google Scholar
  21. G. Lindblad. On the generators of quantum dynamical systems. Communications in Mathematical Physics, 48:119-130, 1976. Google Scholar
  22. S. Lloyd. Universal quantum simulators. Science, 273(5278):1073-1078, 1996. Google Scholar
  23. G. H. Low and I. L. Chuang. Optimal Hamiltonian simulation by quantum signal processing, 2016. arXiv:1606.02685. Google Scholar
  24. E. Magesan, D. Puzzuoli, C. E. Granade, and D. G. Cory. Modeling quantum noise for efficient testing of fault-tolerant circuits. Physical Review A, 87(1):012324, 2013. Google Scholar
  25. V. May and O. Kühn. Charge and energy transfer dynamics in molecular systems. John Wiley &Sons, 2008. Google Scholar
  26. S. Mostame, P. Rebentrost, A. Eisfeld, A. J. Kerman, D. I. Tsomokos, and A. Aspuru-Guzik. Quantum simulator of an open quantum system using superconducting qubits: exciton transport in photosynthetic complexes. New Journal of Physics, 14(10):105013, 2012. Google Scholar
  27. A. Nitzan. Chemical dynamics in condensed phases: relaxation, transfer and reactions in condensed molecular systems. Oxford university press, 2006. Google Scholar
  28. A. Patel and A. Priyadarsini. Optimization of quantum hamiltonian evolution: from two projection operators to local hamiltonians. International Journal of Quantum Information, page 1650027, 2016. Google Scholar
  29. F. Reiter, D. Reeb, and A. S. Sørensen. Scalable dissipative preparation of many-body entanglement. Physical Review Letters, 117(4):040501, 2016. Google Scholar
  30. M. Suzuki. General theory of fractal path integrals with applications to many-body theories and statistical physics. Journal of Mathematical Physics, 32(2):400-407, 1991. Google Scholar
  31. F. Verstraete, M. M. Wolf, and J. I. Cirac. Quantum computation and quantum-state engineering driven by dissipation. Nature physics, 5(9):633-636, 2009. Google Scholar
  32. U. Weiss. Quantum dissipative systems. World scientific, 2012. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact