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

Computational Problems Related to Open Quantum Systems

Chunhao Wang

Published Aug 22, 2018• 1 citation
OpenAlex

Abstract

A quantum system that has interaction with external resources, such as probability distribution, dissipation, and noise, is referred to as an open quantum system. Not only do open quantum systems play a vital role in the field of quantum physics, but they are also fundamental objects in quantum information and quantum computing. In this thesis, we focus on computational problems related to open quantum systems. In particular, we study efficient constructions of open quantum systems and their algorithmic applications. \n \nA unitary 2-design is a quantum analogue of universal 2-hash functions. It is an example of open quantum systems in the sense that it is a probability distribution of unitaries. As unitary 2-designs inherit many properties of the Haar randomness on the unitary group, they have many applications in quantum information, such as benchmarking and decoupling. We study the structures of unitary 2-designs and present efficient methods for their constructions. \n \nThe continuous-time evolution of a closed quantum system can be described by the Schrödinger equation. A natural generalization of the Schrödinger equation to Markovian open quantum systems, in the sense of generating dynamical semigroups, is called the Lindblad equation. We show that it is impossible for a simple reductionist approach to simulate Lindblad evolution with gate complexity that has linear dependence in evolution time. Moreover, we use a novel variation of the "linear combination of unitaries" construction that pertains to quantum channels to achieve the desired linear dependence in evolution time and poly-logarithmic dependence in precision. \n \nOpen quantum systems can also be used as building blocks of quantum algorithms. We present a dissipative query model, which is based on the amplitude damping process. With this dissipative query model, we provide a quantum algorithm that performs a fixed-point quantum search while preserving the quadratic speedup against classical algorithms.

Related papers

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•137 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•8 citations

Quantum Algorithms for Scientific Computing and Approximate Optimization

Stuart Hadfield

Quantum computation appears to offer significant advantages over classical computation and this has generated a tremendous interest in the field. In this thesis we study the application of quantum computers to computational problems in science and engineering, and to combinatorial optimization problems. We outline the results below. Algorithms for scientific computing require modules, i.e., building blocks, implementing elementary numerical functions that have well-controlled numerical error, are uniformly scalable and reversible, and that can be implemented efficiently. We derive quantum algorithms and circuits for computing square roots, logarithms, and arbitrary fractional powers, and derive worst-case error and cost bounds. We describe a modular approach to quantum algorithm design as a first step towards numerical standards and mathematical libraries for quantum scientific computing. A fundamental but computationally hard problem in physics is to solve the time-independent Schrödinger equation. This is accomplished by computing the eigenvalues of the corresponding Hamiltonian operator. The eigenvalues describe the different energy levels of a system. The cost of classical deterministic algorithms computing these eigenvalues grows exponentially with the number of system degrees of freedom. The number of degrees of freedom is typically proportional to the number of particles in a physical system. We show an efficient quantum algorithm for approximating a constant number of low-order eigenvalues of a Hamiltonian using a perturbation approach. We apply this algorithm to a special case of the Schrödinger equation and show that our algorithm succeeds with high probability, and has cost that scales polynomially with the number of degrees of freedom and the reciprocal of the desired accuracy. This improves and extends earlier results on quantum algorithms for estimating the ground state energy. We consider the simulation of quantum mechanical systems on a quantum computer. We show a novel divide and conquer approach for Hamiltonian simulation. Using the Hamiltonian structure, we can obtain faster simulation algorithms. Considering a sum of Hamiltonians we split them into groups, simulate each group separately, and combine the partial results. Simulation is customized to take advantage of the properties of each group, and hence yield refined bounds to the overall simulation cost. We illustrate our results using the electronic structure problem of quantum chemistry, where we obtain significantly improved cost estimates under mild assumptions. We turn to combinatorial optimization problems. An important open question is whether quantum computers provide advantages for the approximation of classically hard combinatorial problems. A promising recently proposed approach of Farhi et al. is the Quantum Approximate Optimization Algorithm (QAOA). We study the application of QAOA to the Maximum Cut problem, and derive analytic performance bounds for the lowest circuit-depth realization, for both general and special classes of graphs. Along the way, we develop a general procedure for analyzing the performance of QAOA for other problems, and show an example demonstrating the difficulty of obtaining similar results for greater depth. We show a generalization of QAOA and its application to wider classes of combinatorial optimization problems, in particular, problems with feasibility constraints. We introduce the Quantum Alternating Operator Ansatz, which utilizes more general unitary operators than the original QAOA proposal. Our framework facilitates low-resource implementations for many applications which may be particularly suitable for early quantum computers. We specify design criteria, and develop a set of results and tools for mapping diverse problems to explicit quantum circuits. We derive constructions for several important prototypical problems including Maximum Independent Set, Graph Coloring, and the Traveling Salesman problem, and show appealing resource cost estimates for their implementations.

arXiv:1805.03265•Jan 1, 2018•79 citations

Universal simulation of Markovian open quantum systems

Ryan Sweke, Ilya Sinayskiy, Denis Bernard +1 more

We consider the problem of constructing a ``universal set'' of Markovian processes, such that any Markovian open quantum system, described by a one-parameter semigroup of quantum channels, can be simulated through sequential simulations of processes from the universal set. In particular, for quantum systems of dimension $d$, we explicitly construct a universal set of semigroup generators, parametrized by ${d}^{2}\ensuremath{-}3$ continuous parameters, and prove that a necessary and sufficient condition for the dynamical simulation of a $d$-dimensional Markovian quantum system is the ability to implement (a) quantum channels from the semigroups generated by elements of the universal set of generators, and (b) unitary operations on the system. Furthermore, we provide an explicit algorithm for simulating the dynamics of a Markovian open quantum system using this universal set of generators, and show that it is efficient, with respect to this universal set, when the number of distinct Lindblad operators (representing physical dissipation processes) scales polynomially with respect to the number of subsystems.

arXiv:1503.05028•Physical Review A•Jun 8, 2015•68 citations

Quantum simulation of open quantum systems.

Ryan Sweke

Over the last two decades the field of quantum simulations has experienced incredible \ngrowth, which, coupled with progress in the development of controllable quantum \nplatforms, has recently begun to allow for the realisation of quantum simulations of a \nplethora of quantum phenomena in a variety of controllable quantum platforms. Within \nthe context of these developments, we investigate within this thesis methods for the \nquantum simulation of open quantum systems. \nMore specically, in the first part of the thesis we consider the simulation of Markovian \nopen quantum systems, and begin by leveraging previously constructed universal \nsets of single-qubit Markovian processes, as well as techniques from Hamiltonian simulation, \nfor the construction of an efficient algorithm for the digital quantum simulation \nof arbitrary single-qubit Markovian open quantum systems. The algorithm we provide, \nwhich requires only a single ancillary qubit, scales slightly superlinearly with respect \nto time, which given a recently proven no fast-forwarding theorem for Markovian dynamics, \nis therefore close to optimal. Building on these results, we then proceed to \nexplicitly construct a universal set of Markovian processes for quantum systems of any \ndimension. Specifically, we prove that any Markovian open quantum system, described \nby a one-parameter semigroup of quantum channels, can be simulated through coherent \noperations and sequential simulations of processes from the universal set. Under the assumption \nthat these universal Markovian processes can be efficiently implemented, this \nallows us to propose an efficient algorithm for a wide class of Markovian open quantum \nsystems, while simultaneously providing a tool for combining and exploiting existing \nsimulation methods. \nIn the second part of this thesis we then consider the simulation of many-body non- \nMarkovian open quantum systems. In particular, we develop an algorithmic procedure \nfor the quantum simulation of system propagators which are not completely positive \nmaps, which allows us to provide an explicit algorithm for the digital quantum simulation \nof many-body locally-indivisible non-Markovian open quantum systems described by \ntime-dependent master equations. Finally we construct generalised Suzuki-Lie-Trotter \ntheorems which allow us to analyse the efficiency of our method, which is expected to \nbe experimentally achievable for a variety of interesting cases.

•Jan 1, 2016•0 citations

Query-optimal quantum simulation of Lindblad evolution

Chunhao Wang, Christopher Ye

For the problem of simulating Lindblad evolution for time $t$ to precision $ε$, Hamiltonian simulation provides an additive query lower bound, informally, $Ω(t + \mathrm{polylog}(1/ε))$. However, the best previously known algorithms for general Lindblad simulation achieve a multiplicative upper bound, informally, $\mathcal{O}(t\,\mathrm{polylog}(1/ε))$, in query complexity. It has remained open whether this multiplicative dependence is necessary. In this paper, we close the gap in query complexity by giving an algorithm with optimal additive dependence on evolution time and precision in the block-encoding model. Our approach uses the transducer framework to reduce the query cost of composing first-order approximations to the evolution channel, together with linear combinations of reuse circuits of different lengths to suppress catalyst-removal error. We further achieve nearly optimal gate complexity in evolution time and precision through history compression and an efficient implementation of the query-free part of the transducer using operation reordering and linear combinations of unitaries, while preserving the optimal query complexity.

quant-pharXiv:2609.17490•Sep 16, 2026•10 citations
A quantum system that has interaction with external resources, such as probability distribution, dissipation, and noise, is referred to as an open quantum system. Not only do open quantum systems play a vital role in the field of quantum physics, but they are also fundamental objects in quantum information and quantum computing. In this thesis, we focus on computational problems related to open quantum systems. In particular, we study efficient constructions of open quantum systems and their algorithmic applications. \n \nA unitary 2-design is a quantum analogue of universal 2-hash functions. It is an example of open quantum systems in the sense that it is a probability distribution of unitaries. As unitary 2-designs inherit many properties of the Haar randomness on the unitary group, they have many applications in quantum information, such as benchmarking and decoupling. We study the structures of unitary 2-designs and present efficient methods for their constructions. \n \nThe continuous-time evolution of a closed quantum system can be described by the Schrödinger equation. A natural generalization of the Schrödinger equation to Markovian open quantum systems, in the sense of generating dynamical semigroups, is called the Lindblad equation. We show that it is impossible for a simple reductionist approach to simulate Lindblad evolution with gate complexity that has linear dependence in evolution time. Moreover, we use a novel variation of the "linear combination of unitaries" construction that pertains to quantum channels to achieve the desired linear dependence in evolution time and poly-logarithmic dependence in precision. \n \nOpen quantum systems can also be used as building blocks of quantum algorithms. We present a dissipative query model, which is based on the amplitude damping process. With this dissipative query model, we provide a quantum algorithm that performs a fixed-point quantum search while preserving the quadratic speedup against classical algorithms.
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.
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.
Quantum computation appears to offer significant advantages over classical computation and this has generated a tremendous interest in the field. In this thesis we study the application of quantum computers to computational problems in science and engineering, and to combinatorial optimization problems. We outline the results below. Algorithms for scientific computing require modules, i.e., building blocks, implementing elementary numerical functions that have well-controlled numerical error, are uniformly scalable and reversible, and that can be implemented efficiently. We derive quantum algorithms and circuits for computing square roots, logarithms, and arbitrary fractional powers, and derive worst-case error and cost bounds. We describe a modular approach to quantum algorithm design as a first step towards numerical standards and mathematical libraries for quantum scientific computing. A fundamental but computationally hard problem in physics is to solve the time-independent Schrödinger equation. This is accomplished by computing the eigenvalues of the corresponding Hamiltonian operator. The eigenvalues describe the different energy levels of a system. The cost of classical deterministic algorithms computing these eigenvalues grows exponentially with the number of system degrees of freedom. The number of degrees of freedom is typically proportional to the number of particles in a physical system. We show an efficient quantum algorithm for approximating a constant number of low-order eigenvalues of a Hamiltonian using a perturbation approach. We apply this algorithm to a special case of the Schrödinger equation and show that our algorithm succeeds with high probability, and has cost that scales polynomially with the number of degrees of freedom and the reciprocal of the desired accuracy. This improves and extends earlier results on quantum algorithms for estimating the ground state energy. We consider the simulation of quantum mechanical systems on a quantum computer. We show a novel divide and conquer approach for Hamiltonian simulation. Using the Hamiltonian structure, we can obtain faster simulation algorithms. Considering a sum of Hamiltonians we split them into groups, simulate each group separately, and combine the partial results. Simulation is customized to take advantage of the properties of each group, and hence yield refined bounds to the overall simulation cost. We illustrate our results using the electronic structure problem of quantum chemistry, where we obtain significantly improved cost estimates under mild assumptions. We turn to combinatorial optimization problems. An important open question is whether quantum computers provide advantages for the approximation of classically hard combinatorial problems. A promising recently proposed approach of Farhi et al. is the Quantum Approximate Optimization Algorithm (QAOA). We study the application of QAOA to the Maximum Cut problem, and derive analytic performance bounds for the lowest circuit-depth realization, for both general and special classes of graphs. Along the way, we develop a general procedure for analyzing the performance of QAOA for other problems, and show an example demonstrating the difficulty of obtaining similar results for greater depth. We show a generalization of QAOA and its application to wider classes of combinatorial optimization problems, in particular, problems with feasibility constraints. We introduce the Quantum Alternating Operator Ansatz, which utilizes more general unitary operators than the original QAOA proposal. Our framework facilitates low-resource implementations for many applications which may be particularly suitable for early quantum computers. We specify design criteria, and develop a set of results and tools for mapping diverse problems to explicit quantum circuits. We derive constructions for several important prototypical problems including Maximum Independent Set, Graph Coloring, and the Traveling Salesman problem, and show appealing resource cost estimates for their implementations.
We consider the problem of constructing a ``universal set'' of Markovian processes, such that any Markovian open quantum system, described by a one-parameter semigroup of quantum channels, can be simulated through sequential simulations of processes from the universal set. In particular, for quantum systems of dimension ddd, we explicitly construct a universal set of semigroup generators, parametrized by ${d}^{2}\ensuremath{-}3$ continuous parameters, and prove that a necessary and sufficient condition for the dynamical simulation of a ddd-dimensional Markovian quantum system is the ability to implement (a) quantum channels from the semigroups generated by elements of the universal set of generators, and (b) unitary operations on the system. Furthermore, we provide an explicit algorithm for simulating the dynamics of a Markovian open quantum system using this universal set of generators, and show that it is efficient, with respect to this universal set, when the number of distinct Lindblad operators (representing physical dissipation processes) scales polynomially with respect to the number of subsystems.
Over the last two decades the field of quantum simulations has experienced incredible \ngrowth, which, coupled with progress in the development of controllable quantum \nplatforms, has recently begun to allow for the realisation of quantum simulations of a \nplethora of quantum phenomena in a variety of controllable quantum platforms. Within \nthe context of these developments, we investigate within this thesis methods for the \nquantum simulation of open quantum systems. \nMore specically, in the first part of the thesis we consider the simulation of Markovian \nopen quantum systems, and begin by leveraging previously constructed universal \nsets of single-qubit Markovian processes, as well as techniques from Hamiltonian simulation, \nfor the construction of an efficient algorithm for the digital quantum simulation \nof arbitrary single-qubit Markovian open quantum systems. The algorithm we provide, \nwhich requires only a single ancillary qubit, scales slightly superlinearly with respect \nto time, which given a recently proven no fast-forwarding theorem for Markovian dynamics, \nis therefore close to optimal. Building on these results, we then proceed to \nexplicitly construct a universal set of Markovian processes for quantum systems of any \ndimension. Specifically, we prove that any Markovian open quantum system, described \nby a one-parameter semigroup of quantum channels, can be simulated through coherent \noperations and sequential simulations of processes from the universal set. Under the assumption \nthat these universal Markovian processes can be efficiently implemented, this \nallows us to propose an efficient algorithm for a wide class of Markovian open quantum \nsystems, while simultaneously providing a tool for combining and exploiting existing \nsimulation methods. \nIn the second part of this thesis we then consider the simulation of many-body non- \nMarkovian open quantum systems. In particular, we develop an algorithmic procedure \nfor the quantum simulation of system propagators which are not completely positive \nmaps, which allows us to provide an explicit algorithm for the digital quantum simulation \nof many-body locally-indivisible non-Markovian open quantum systems described by \ntime-dependent master equations. Finally we construct generalised Suzuki-Lie-Trotter \ntheorems which allow us to analyse the efficiency of our method, which is expected to \nbe experimentally achievable for a variety of interesting cases.
For the problem of simulating Lindblad evolution for time ttt to precision εεε, Hamiltonian simulation provides an additive query lower bound, informally, Ω(t+polylog(1/ε))Ω(t + \mathrm{polylog}(1/ε))Ω(t+polylog(1/ε)). However, the best previously known algorithms for general Lindblad simulation achieve a multiplicative upper bound, informally, O(t polylog(1/ε))\mathcal{O}(t\,\mathrm{polylog}(1/ε))O(tpolylog(1/ε)), in query complexity. It has remained open whether this multiplicative dependence is necessary. In this paper, we close the gap in query complexity by giving an algorithm with optimal additive dependence on evolution time and precision in the block-encoding model. Our approach uses the transducer framework to reduce the query cost of composing first-order approximations to the evolution channel, together with linear combinations of reuse circuits of different lengths to suppress catalyst-removal error. We further achieve nearly optimal gate complexity in evolution time and precision through history compression and an efficient implementation of the query-free part of the transducer using operation reordering and linear combinations of unitaries, while preserving the optimal query complexity.