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

Limits on Classical Simulation of Free Fermions with Dissipation

Oles Shtanko, Abhinav Deshpande, Paul S. Julienne, Alexey Vyacheslavovich Gorshkov

Published May 21, 2020• 0 citations
OpenAlex

Abstract

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.

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)$.

arXiv:1112.2184•Dec 9, 2011•4 citations

Complexity of Fermionic Dissipative Interactions and Applications to Quantum Computing

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

Interactions between particles are usually a resource for quantum computing, making quantum manybody systems intractable by any known classical algorithm.In contrast, noise is typically considered as being inimical to quantum many-body correlations, ultimately leading the system to a classically tractable state.This work shows that noise represented by two-body processes, such as pair loss, plays the same role as many-body interactions and makes otherwise classically simulable systems universal for quantum computing.We analyze such processes in detail and establish a complexity transition between simulable and nonsimulable systems as a function of a tuning parameter.We determine important classes of simulable and nonsimulable two-body dissipation.Finally, we show how using resonant dissipation in cold atoms can enhance the performance of two-qubit gates.

arXiv:2005.10840•PRX Quantum•Sep 24, 2021•12 citations

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

Solving free fermion problems on a quantum computer

Maarten Stroeks, Daan Lenterman, Barbara M. Terhal +1 more

Simulating noninteracting fermion systems is a common task in computational many-body physics. In the absence of translational symmetries, modeling free fermions on N modes usually requires poly ( N ) computational resources. While often moderate, these costs can be prohibitive in practice when large systems are considered. We present several free fermion problems that can be solved by a quantum algorithm with substantially reduced computational costs. The memory costs are exponentially improved, poly log ( N ) . The run-time improvement, compared to the best known classical algorithms, is either exponential or significantly polynomial, depending on the geometry of the problem. The simulation of free fermion dynamics belongs to the BQP-hard complexity class (i.e., as hard as any (decision) problem that can be solved on a quantum computer). This implies (under standard assumptions) that our algorithm yields an exponential speedup for classical algorithm at least for some geometries. The key technique in our algorithm is the block encoding of objects such as correlation matrices and Green's functions into a unitary. We demonstrate how such unitaries can be efficiently realized as quantum circuits, in the context of dynamics and thermal states of tight-binding Hamiltonians. The special cases of disordered and inhomogeneous lattices, as well as large nonlattice graphs, are presented in detail. Finally, we show that our simulation algorithm generalizes to other promising targets, including free-boson systems.

arXiv:2409.04550•Physical Review Research•Nov 18, 2025•5 citations

Quantum dissipative search via Lindbladians

Peter J. Eder, Jernej Rudi Finžgar, Sarah Braun +1 more

Closed quantum systems follow a unitary time evolution that can be simulated on quantum computers. By incorporating nonunitary effects via, e.g., measurements on ancilla qubits, these algorithms can be extended to open-system dynamics, such as Markovian processes described by the Lindblad master equation. In this paper, we analyze the convergence criteria and speed of a Markovian, purely dissipative quantum random walk on an unstructured classical search space. Notably, we show that certain jump operators make the quantum process replicate a classical one, while others yield differences between open quantum (OQRW) and classical random walks. We also clarify a previously observed quadratic speedup, demonstrating that OQRWs are no more efficient than classical search. Finally, we analyze a dissipative discrete-time ground-state preparation algorithm with a lower implementation cost. This allows us to interpolate between the dissipative and the unitary domain and thereby illustrate the important role of coherence for the quadratic speedup.

arXiv:2407.11782•Physical Review A•Apr 25, 2025•5 citations

Efficient Simulation of Nontrivial Dissipative Spin Chains via Stochastic Unraveling

Andrew Pocklington, Aashish A. Clerk

We present a new technique for efficiently simulating (in polynomial time) a class of one-dimensional (1D) dissipative spin chains that, when mapped to fermions, have quadratic Hamiltonians, with the only nonlinearity coming from Jordan-Wigner strings appearing in the jump operators, despite the fact that these models cannot be mapped to quadratic fermionic master equations. We show that many such Lindblad master equations admit an exact stochastic unraveling, with individual trajectories evolving as Gaussian fermionic states, even though the full master equation describes a system inequivalent to free fermions. This allows one to calculate arbitrary observables efficiently without sign problems, and with bounded sampling complexity. We utilize this new technique to study three paradigmatic dissipative effects: the melting of antiferromagnetic order in the presence of local loss, many-body subradiant phenomenon in systems with correlated loss, and nonequilibrium steady states of a 1D dissipative transverse-field Ising model. Beyond simply providing a powerful numerical technique, our method can also be used to gain both qualitative and quantitative insights into the role of interactions in these models.

arXiv:2503.23469•PRX Quantum•Aug 6, 2025•1 citation
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.
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).
Interactions between particles are usually a resource for quantum computing, making quantum manybody systems intractable by any known classical algorithm.In contrast, noise is typically considered as being inimical to quantum many-body correlations, ultimately leading the system to a classically tractable state.This work shows that noise represented by two-body processes, such as pair loss, plays the same role as many-body interactions and makes otherwise classically simulable systems universal for quantum computing.We analyze such processes in detail and establish a complexity transition between simulable and nonsimulable systems as a function of a tuning parameter.We determine important classes of simulable and nonsimulable two-body dissipation.Finally, we show how using resonant dissipation in cold atoms can enhance the performance of two-qubit gates.
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).
Simulating noninteracting fermion systems is a common task in computational many-body physics. In the absence of translational symmetries, modeling free fermions on N modes usually requires poly ( N ) computational resources. While often moderate, these costs can be prohibitive in practice when large systems are considered. We present several free fermion problems that can be solved by a quantum algorithm with substantially reduced computational costs. The memory costs are exponentially improved, poly log ( N ) . The run-time improvement, compared to the best known classical algorithms, is either exponential or significantly polynomial, depending on the geometry of the problem. The simulation of free fermion dynamics belongs to the BQP-hard complexity class (i.e., as hard as any (decision) problem that can be solved on a quantum computer). This implies (under standard assumptions) that our algorithm yields an exponential speedup for classical algorithm at least for some geometries. The key technique in our algorithm is the block encoding of objects such as correlation matrices and Green's functions into a unitary. We demonstrate how such unitaries can be efficiently realized as quantum circuits, in the context of dynamics and thermal states of tight-binding Hamiltonians. The special cases of disordered and inhomogeneous lattices, as well as large nonlattice graphs, are presented in detail. Finally, we show that our simulation algorithm generalizes to other promising targets, including free-boson systems.
Closed quantum systems follow a unitary time evolution that can be simulated on quantum computers. By incorporating nonunitary effects via, e.g., measurements on ancilla qubits, these algorithms can be extended to open-system dynamics, such as Markovian processes described by the Lindblad master equation. In this paper, we analyze the convergence criteria and speed of a Markovian, purely dissipative quantum random walk on an unstructured classical search space. Notably, we show that certain jump operators make the quantum process replicate a classical one, while others yield differences between open quantum (OQRW) and classical random walks. We also clarify a previously observed quadratic speedup, demonstrating that OQRWs are no more efficient than classical search. Finally, we analyze a dissipative discrete-time ground-state preparation algorithm with a lower implementation cost. This allows us to interpolate between the dissipative and the unitary domain and thereby illustrate the important role of coherence for the quadratic speedup.
We present a new technique for efficiently simulating (in polynomial time) a class of one-dimensional (1D) dissipative spin chains that, when mapped to fermions, have quadratic Hamiltonians, with the only nonlinearity coming from Jordan-Wigner strings appearing in the jump operators, despite the fact that these models cannot be mapped to quadratic fermionic master equations. We show that many such Lindblad master equations admit an exact stochastic unraveling, with individual trajectories evolving as Gaussian fermionic states, even though the full master equation describes a system inequivalent to free fermions. This allows one to calculate arbitrary observables efficiently without sign problems, and with bounded sampling complexity. We utilize this new technique to study three paradigmatic dissipative effects: the melting of antiferromagnetic order in the presence of local loss, many-body subradiant phenomenon in systems with correlated loss, and nonequilibrium steady states of a 1D dissipative transverse-field Ising model. Beyond simply providing a powerful numerical technique, our method can also be used to gain both qualitative and quantitative insights into the role of interactions in these models.