Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1112.2184

Classical simulation of dissipative fermionic linear optics

Sergey B. Bravyi, Robert König

Published Dec 9, 2011• 4 citations
arXivHTMLPDF

Abstract

Fermionic linear optics is a limited form of quantum computation which is known to be efficiently simulable on a classical computer. We revisit and extend this result by enlarging the set of available computational gates: in addition to unitaries and measurements, we allow dissipative evolution governed by a Markovian master equation with linear Lindblad operators. We show that this more general form of fermionic computation is also simulable efficiently by classical means. Given a system of $N$ fermionic modes, our algorithm simulates any such gate in time $O(N^3)$ while a single-mode measurement is simulated in time $O(N^2)$. The steady state of the Lindblad equation can be computed in time $O(N^3)$.

DOI
10.48550/arxiv.1112.2184

Related papers

Classical simulation of dissipative fermionic linear optics

Sergey B. Bravyi, Robert König

Fermionic linear optics is a limited form of quantum computation which is known to be efficiently simulable on a classical computer. We revisit and extend this result by enlarging the set of available computational gates: in addition to unitaries and measurements, we allow dissipative evolution governed by a Markovian master equation with linear Lindblad operators. We show that this more general form of fermionic computation is also simulable efficiently by classical means. Given a system of $N$~fermionic modes, our algorithm simulates any such gate in time $O(N^3)$ while a single-mode measurement is simulated in time $O(N^2)$. The steady state of the Lindblad equation can be computed in time $O(N^3)$.

Quantum Information and Computation•Nov 1, 2012•22 citations

Classical simulation of dissipative fermionic linear optics

BravyiSergey, KönigRobert

Fermionic linear optics is a limited form of quantum computation which is known to be efficiently simulable on a classical computer. We revisit and extend this result by enlarging the set of availa...

Quantum Information and Computation•Nov 1, 2012•0 citations

Limits on Classical Simulation of Free Fermions with Dissipation

Oles Shtanko, Abhinav Deshpande, Paul S. Julienne +1 more

Free-fermionic systems are a valuable, but limited, class of many-body problems efficiently simulable on a classical computer. We examine how classical simulability of noninteracting fermions is modified in the presence of Markovian dissipation described by quadratic Lindblad operators, including, for example, incoherent transitions or pair losses. On the one hand, we establish three broad classes of Markovian dynamics that are efficiently simulable classically, by devising efficient algorithms. On the other hand, we demonstrate that, in the worst case, simulating Markovian dynamics with quadratic Lindblad operators is at least as hard as simulating universal quantum circuits. This result is applicable to an experimentally relevant setting in cold atomic systems, where magnetic Feshbach resonances can be used to engineer the desired dissipation. For such systems, our hardness result provides a direct scheme for dissipation-assisted quantum computing with a potential significant advantage in the speed of two-qubit gates and, therefore, in error tolerance.

•May 21, 2020•0 citations

Quantum algorithm to simulate Lindblad master equations

Evan Borras, Milad Marvian

We present a quantum algorithm for simulating a family of Markovian master equations that can be realized through a probabilistic application of unitary channels and state preparation. Our approach employs a second-order product formula for the Lindblad master equation, achieved by decomposing the dynamics into dissipative and Hamiltonian components and replacing the dissipative segments with randomly compiled, easily implementable elements. The sampling approach eliminates the need for ancillary qubits to simulate the dissipation process and reduces the gate complexity in terms of the number of jump operators. We provide a rigorous performance analysis of the algorithm. We also extend the algorithm to time-dependent Lindblad equations, generalize the family of Markovian master equations it can be applied to, and explore applications beyond the Markovian noise model. A new error bound, in terms of the diamond norm, for second-order product formulas for time-dependent Liouvillians is provided that might be of independent interest.

arXiv:2406.12748•Physical Review Research•Apr 22, 2025•10 citations

Efficient Quantum Algorithms for Simulating Lindblad Evolution

Richard Cleve, Chunhao Wang

We consider the natural generalization of the Schrödinger 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 $ε$. If the Lindbladian consists of $\mathrm{poly}(n)$ operators that can each be expressed as a linear combination of $\mathrm{poly}(n)$ tensor products of Pauli operators then the gate cost of our algorithm is $O(t\, \mathrm{polylog}(t/ε)\mathrm{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 Schrödinger evolution on a larger system and tracing out the ancillary system: the cost of such a \textit{reduction} incurs an efficiency overhead of $O(t^2/ε)$ 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.

arXiv:1612.09512•Leibniz international proceedings in informatics•Dec 30, 2016•41 citations

Markovian evolution from a novel scheme

Fardin Kheirandish, Zahra Iranshahi, Fatemeh Bakhtiari +1 more

The Markovian dynamics of open quantum many-body systems are typically governed by the Lindblad master equation, yet obtaining the reduced density matrix for bosonic and fermionic systems remains a formidable numerical challenge due to the exponential growth of the Hilbert space. Here, we introduce a computationally efficient framework for constructing the reduced density matrix by modeling the environment as a copy of the primary system with a monotonically decaying coupling that enforces unidirectional energy flow. Our method directly yields exact solutions that rigorously satisfy the Lindblad master equation for both bosonic and fermionic cases, bypassing the need for costly Liouvillian diagonalization. We validate our approach through applications to paradigmatic models, demonstrating accurate reproduction of dissipative dynamics across a broad parameter regime. This work provides a straightforward and powerful tool for simulating Markovian open-system evolution, with immediate applicability to quantum transport and control problems in many-body physics.

quant-pharXiv:2607.13809•Jul 16, 2026•0 citations
Fermionic linear optics is a limited form of quantum computation which is known to be efficiently simulable on a classical computer. We revisit and extend this result by enlarging the set of available computational gates: in addition to unitaries and measurements, we allow dissipative evolution governed by a Markovian master equation with linear Lindblad operators. We show that this more general form of fermionic computation is also simulable efficiently by classical means. Given a system of NNN fermionic modes, our algorithm simulates any such gate in time O(N3)O(N^3)O(N3) while a single-mode measurement is simulated in time O(N2)O(N^2)O(N2). The steady state of the Lindblad equation can be computed in time O(N3)O(N^3)O(N3).
Fermionic linear optics is a limited form of quantum computation which is known to be efficiently simulable on a classical computer. We revisit and extend this result by enlarging the set of available computational gates: in addition to unitaries and measurements, we allow dissipative evolution governed by a Markovian master equation with linear Lindblad operators. We show that this more general form of fermionic computation is also simulable efficiently by classical means. Given a system of NNN~fermionic modes, our algorithm simulates any such gate in time O(N3)O(N^3)O(N3) while a single-mode measurement is simulated in time O(N2)O(N^2)O(N2). The steady state of the Lindblad equation can be computed in time O(N3)O(N^3)O(N3).
Free-fermionic systems are a valuable, but limited, class of many-body problems efficiently simulable on a classical computer. We examine how classical simulability of noninteracting fermions is modified in the presence of Markovian dissipation described by quadratic Lindblad operators, including, for example, incoherent transitions or pair losses. On the one hand, we establish three broad classes of Markovian dynamics that are efficiently simulable classically, by devising efficient algorithms. On the other hand, we demonstrate that, in the worst case, simulating Markovian dynamics with quadratic Lindblad operators is at least as hard as simulating universal quantum circuits. This result is applicable to an experimentally relevant setting in cold atomic systems, where magnetic Feshbach resonances can be used to engineer the desired dissipation. For such systems, our hardness result provides a direct scheme for dissipation-assisted quantum computing with a potential significant advantage in the speed of two-qubit gates and, therefore, in error tolerance.
We present a quantum algorithm for simulating a family of Markovian master equations that can be realized through a probabilistic application of unitary channels and state preparation. Our approach employs a second-order product formula for the Lindblad master equation, achieved by decomposing the dynamics into dissipative and Hamiltonian components and replacing the dissipative segments with randomly compiled, easily implementable elements. The sampling approach eliminates the need for ancillary qubits to simulate the dissipation process and reduces the gate complexity in terms of the number of jump operators. We provide a rigorous performance analysis of the algorithm. We also extend the algorithm to time-dependent Lindblad equations, generalize the family of Markovian master equations it can be applied to, and explore applications beyond the Markovian noise model. A new error bound, in terms of the diamond norm, for second-order product formulas for time-dependent Liouvillians is provided that might be of independent interest.
We consider the natural generalization of the Schrödinger equation to Markovian open system dynamics: the so-called the Lindblad equation. We give a quantum algorithm for simulating the evolution of an nnn-qubit system for time ttt within precision εεε. If the Lindbladian consists of poly(n)\mathrm{poly}(n)poly(n) operators that can each be expressed as a linear combination of poly(n)\mathrm{poly}(n)poly(n) tensor products of Pauli operators then the gate cost of our algorithm is O(t polylog(t/ε)poly(n))O(t\, \mathrm{polylog}(t/ε)\mathrm{poly}(n))O(tpolylog(t/ε)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 Schrödinger evolution on a larger system and tracing out the ancillary system: the cost of such a \textit{reduction} incurs an efficiency overhead of O(t2/ε)O(t^2/ε)O(t2/ε) 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.
The Markovian dynamics of open quantum many-body systems are typically governed by the Lindblad master equation, yet obtaining the reduced density matrix for bosonic and fermionic systems remains a formidable numerical challenge due to the exponential growth of the Hilbert space. Here, we introduce a computationally efficient framework for constructing the reduced density matrix by modeling the environment as a copy of the primary system with a monotonically decaying coupling that enforces unidirectional energy flow. Our method directly yields exact solutions that rigorously satisfy the Lindblad master equation for both bosonic and fermionic cases, bypassing the need for costly Liouvillian diagonalization. We validate our approach through applications to paradigmatic models, demonstrating accurate reproduction of dissipative dynamics across a broad parameter regime. This work provides a straightforward and powerful tool for simulating Markovian open-system evolution, with immediate applicability to quantum transport and control problems in many-body physics.