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

Open Quantum Random Walks on Graphs

Stéphane Attal, Francesco Petruccione, Ilya Sinayskiy

Published Jan 1, 2012• 1 citation
OpenAlex

Abstract

Open quantum walks (OQW) are formulated as quantum Markov chains on graphs. It is shown that OQWs are a very useful tool for the formulation of dissipative quantum computing algorithms and for dissipative quantum state preparation. In particular, single qubit gates and the CNOT-gate are implemented as OQWs on fully connected graphs. Also, dissipative quantum state preparation of arbitrary single qubit states and of all two-qubit Bell-states is demonstrated. Finally, the discrete time version of dissipative quantum computing is shown to be more efficient if formulated in the language of OQWs.

Related papers

Open Quantum Walks as a Tool for Dissipative Quantum Computing

Francesco Petruccione, Ilya Sinayskiy

Recently, open quantum walks (OQW) have been formulated as quantum Markov chains on graphs. It is shown that OQWs are a very useful tool for the formulation of dissipative quantum computing algorithms and for dissipative quantum state preparation.

Research in Optical Sciences•Jan 1, 2012•0 citations

Open Quantum Walks: a short introduction

Ilya Sinayskiy, Francesco Petruccione

The concept of open quantum walks (OQW), quantum walks exclusively driven by the interaction with the external environment, is reviewed. OQWs are formulated as discrete completely positive maps on graphs. The basic properties of OQWs are summarised and new examples of OQWs on and their simulation by means of quantum trajectories are presented.

arXiv:1402.2146•Journal of Physics Conference Series•Jun 10, 2013•29 citations

Microscopic derivation of open quantum walks

Ilya Sinayskiy, Francesco Petruccione

Open quantum walks (OQWs) are exclusively driven by dissipation and are formulated as completely positive trace-preserving (CPTP) maps on underlying graphs. The microscopic derivation of discrete and continuous-in-time OQWs is presented. It is assumed that connected nodes are weakly interacting via a common bath. The resulting reduced master equation of the quantum walker on the lattice is in the generalized master equation form. The time discretization of the generalized master equation leads to the OQW formalism. The explicit form of the transition operators establishes a connection between dynamical properties of the OQWs and thermodynamical characteristics of the environment. The derivation is demonstrated for the examples of the OQW on a circle of nodes and on a finite chain of nodes. For both examples, a transition between diffusive and ballistic quantum trajectories is observed and found to be related to the temperature of the bath.

arXiv:1510.01677•Physical Review A•Sep 8, 2015•19 citations

State Preparation Protocols for Entangled States via Open Quantum Walks

Pedro Linck, Nadja K. Bernardes

Open quantum walks couple transitions on a graph to quantum operations on an internal degree of freedom. We use this structure to formulate protocols for quantum state preparation with nonunitary Kraus operators. We construct a ring-shaped OQW preparing an ensemble of Dicke states, with W states appearing as the single-excitation case, from which any individual Dicke state is recovered by postselecting the walker position; its convergence is governed by the spectral gap of the underlying Markov chain, for which we obtain a closed-form approximate expression. For GHZ states we present a two-node protocol using Kraus operators built from projective measurements that prepares them deterministically without requiring a measurement of the walker, and analyze how unsharp measurements affect the results and the convergence of the walk. We also show that the quantum trajectories method embeds naturally in the OQW framework as a graph-structured collision model.

quant-pharXiv:2608.07695•Aug 11, 2026•0 citations

Lazy open quantum walks

Garreth Kemp, Ilya Sinayskiy, Francesco Petruccione

Open quantum walks (OQWs) describe a quantum walker on an underlying graph whose dynamics is purely driven by dissipation and decoherence. Mathematically, they are formulated as completely positive trace preserving (CPTP) maps on the space of density matrices for the walker on the graph. Any microscopically derived OQW must include the possibility of remaining on the same site on the graph when the map is applied. We extend the CPTP map to describe a lazy OQW. We derive a central limit theorem for lazy OQWs on a $d$-dimensional lattice, where the distribution converges to a Gaussian. We show that the properties of this Gaussian computed using conventional methods agree with the general formulas derived from our central limit theorem.

arXiv:1908.04124•Physical Review A•Jul 27, 2020•8 citations

Dynamics and computation in linear open quantum walks

Pedro Linck, Nadja K. Bernardes

Open Quantum Walks (OQW) are a type of quantum walk governed by the system's interaction with its environment. We explore the time evolution and the limit behavior of the OQW framework for Quantum Computation and show how we can represent random unitary quantum channels, such as the dephasing and depolarizing channels, in this model. We also develop a simulation protocol with circuit representation for this model, which is heavily inspired by the fact that graphs represent OQW and are, thereby, local (meaning that the state in a particular node interacts only with its neighborhood). We obtain asymptotic advantages in the system's dimension, circuit depth, and CNOT count compared to other simulation methods.

arXiv:2503.17591•Physical Review A•Sep 4, 2025•2 citations
Open quantum walks (OQW) are formulated as quantum Markov chains on graphs. It is shown that OQWs are a very useful tool for the formulation of dissipative quantum computing algorithms and for dissipative quantum state preparation. In particular, single qubit gates and the CNOT-gate are implemented as OQWs on fully connected graphs. Also, dissipative quantum state preparation of arbitrary single qubit states and of all two-qubit Bell-states is demonstrated. Finally, the discrete time version of dissipative quantum computing is shown to be more efficient if formulated in the language of OQWs.
Open quantum walks (OQWs) are exclusively driven by dissipation and are formulated as completely positive trace-preserving (CPTP) maps on underlying graphs. The microscopic derivation of discrete and continuous-in-time OQWs is presented. It is assumed that connected nodes are weakly interacting via a common bath. The resulting reduced master equation of the quantum walker on the lattice is in the generalized master equation form. The time discretization of the generalized master equation leads to the OQW formalism. The explicit form of the transition operators establishes a connection between dynamical properties of the OQWs and thermodynamical characteristics of the environment. The derivation is demonstrated for the examples of the OQW on a circle of nodes and on a finite chain of nodes. For both examples, a transition between diffusive and ballistic quantum trajectories is observed and found to be related to the temperature of the bath.
Open quantum walks couple transitions on a graph to quantum operations on an internal degree of freedom. We use this structure to formulate protocols for quantum state preparation with nonunitary Kraus operators. We construct a ring-shaped OQW preparing an ensemble of Dicke states, with W states appearing as the single-excitation case, from which any individual Dicke state is recovered by postselecting the walker position; its convergence is governed by the spectral gap of the underlying Markov chain, for which we obtain a closed-form approximate expression. For GHZ states we present a two-node protocol using Kraus operators built from projective measurements that prepares them deterministically without requiring a measurement of the walker, and analyze how unsharp measurements affect the results and the convergence of the walk. We also show that the quantum trajectories method embeds naturally in the OQW framework as a graph-structured collision model.
Open quantum walks (OQWs) describe a quantum walker on an underlying graph whose dynamics is purely driven by dissipation and decoherence. Mathematically, they are formulated as completely positive trace preserving (CPTP) maps on the space of density matrices for the walker on the graph. Any microscopically derived OQW must include the possibility of remaining on the same site on the graph when the map is applied. We extend the CPTP map to describe a lazy OQW. We derive a central limit theorem for lazy OQWs on a ddd-dimensional lattice, where the distribution converges to a Gaussian. We show that the properties of this Gaussian computed using conventional methods agree with the general formulas derived from our central limit theorem.
Open Quantum Walks (OQW) are a type of quantum walk governed by the system's interaction with its environment. We explore the time evolution and the limit behavior of the OQW framework for Quantum Computation and show how we can represent random unitary quantum channels, such as the dephasing and depolarizing channels, in this model. We also develop a simulation protocol with circuit representation for this model, which is heavily inspired by the fact that graphs represent OQW and are, thereby, local (meaning that the state in a particular node interacts only with its neighborhood). We obtain asymptotic advantages in the system's dimension, circuit depth, and CNOT count compared to other simulation methods.