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:2004.01332 · Electronic Proceedings in Theoretical Computer Science

Projection Theorem for Discrete-Time Quantum Walks

Václav Potoček

Published Apr 1, 2020• 0 citations
arXivHTMLPDF

Abstract

We make and generalize the observation that summing of probability amplitudes of a discrete-time quantum walk over partitions of the walking graph consistent with the step operator results in a unitary evolution on the reduced graph which is also a quantum walk. Since the effective walking graph of the projected walk is not necessarily simpler than the original, this may bring new insights into the dynamics of some kinds of quantum walks using known results from thoroughly studied cases like Euclidean lattices. We use abstract treatment of the walking space and walker displacements in aim for a generality of the presented statements. Using this approach we also identify some pathological cases in which the projection mapping breaks down. For walks on lattices, the operation typically results in quantum walks with hyper-dimensional coin spaces. Such walks can, conversely, be viewed as projections of walks on inaccessible, larger spaces, and their properties can be inferred from the parental walk. We show that this is is the case for a lazy quantum walk, a walk with large coherent jumps and a walk on a circle with a twisted boundary condition. We also discuss the relation of this theory to the time-multiplexing optical implementations of quantum walks. Moreover, this manifestly irreversible operation can, in some cases and with a minor adjustment, be undone, and a quantum walk can be reconstructed from a set of its projections.

DOI
10.4204/eptcs.315.5

Related papers

Discrete-time quantum walks in synthetic dimensions

Piergiorgio Ferraro, Caio B. Naves, Jonas Larson

In this work we introduce discrete-time quantum walks in state space, more precisely on Fock-state lattices. Fock-state lattices provide a natural and clean setting for implementing lattice models, particularly in quantum optical systems. Thus, contrary to the common setting where the walker resides in real space or phase space, here the walk takes place in a synthetic space. We present a general formalism based on Lie algebras and their properties. For each Lie algebra one can associate both a phase space and a Fock-state lattice, and by understanding how these spaces are related, together with the action of generalized displacement operators, we construct the discrete unitary operator that generates the walk. In this framework the displacement operators replace the usual nearest-neighbor shifts and lead to state-dependent tunneling on the lattice. By considering several examples we demonstrate ballistic spreading and other characteristic features of discrete-time quantum walks, such as coin-walker entanglement and symmetry-induced interference patterns. We also show that different algebraic structures can give rise to qualitatively different dynamics, including anomalous behavior such as super-ballistic spreading as well as localization effects.

quant-pharXiv:2604.09357•Apr 13, 2026•0 citations

Probing measurement-induced effects in quantum walks via recurrence

Thomas Nitsche, Sonja Barkhofen, Regina Kruse +7 more

Measurements on a quantum particle unavoidably affect its state, since the otherwise unitary evolution of the system is interrupted by a nonunitary projection operation. To probe measurement-induced effects in the state dynamics using a quantum simulator, the challenge is to implement controlled measurements on a small subspace of the system and continue the evolution from the complementary subspace. A powerful platform for versatile quantum evolution is represented by photonic quantum walks because of their high control over all relevant parameters. However, measurement-induced dynamics in such a platform have not yet been realized. We implement controlled measurements in a discrete-time quantum walk based on time-multiplexing. This is achieved by adding a deterministic outcoupling of the optical signal to include measurements constrained to specific positions resulting in the projection of the walker's state on the remaining ones. With this platform and coherent input light, we experimentally simulate measurement-induced single-particle quantum dynamics. We demonstrate the difference between dynamics with only a single measurement at the final step and those including measurements during the evolution. To this aim, we study recurrence as a figure of merit, that is, the return probability to the walker's starting position, which is measured in the two cases. We track the development of the return probability over 36 time steps and observe the onset of both recurrent and transient evolution as an effect of the different measurement schemes, a signature which only emerges for quantum systems. Our simulation of the observed one-particle conditional quantum dynamics does not require a genuine quantum particle but is demonstrated with coherent light.

arXiv:1803.04712•Science Advances•Jun 1, 2018•48 citations

Analysis of quantum walks with time-varying coin on d-dimensional lattices

Francesca Albertini, Domenico D’Alessandro

In this paper, we present a study of discrete time quantum walks whose underlying graph is a d-dimensional lattice. The dynamical behavior of these systems is of current interest because of their applications in quantum information theory as tools to design quantum algorithms. We assume that, at each step of the walk evolution, the coin transformation is allowed to change so that we can use it as a control variable to drive the evolution in a desired manner. We give an exact description of the possible evolutions and of the set of possible states that can be achieved with such a system. In particular, we show that it is possible to go from a state where there is probability 1 for the walker to be found in a vertex to a state where all the vertices have equal probability. We also prove a number of properties of the set of admissible states in terms of the number of steps needed to obtain them. We provide explicit algorithms for state transfer in low dimensional cases as well as results that allow to reduce algorithms on two-dimensional lattices to algorithms on the one-dimensional lattice, the cycle.

Journal of Mathematical Physics•Dec 1, 2009•9 citations

Unveiling and exemplifying the unitary equivalence of discrete time quantum walk models

B. F. Venancio, F M Andrade, M G E da Luz

The two major discrete time formulations for quantum walks, coined and scattering, are unitarily equivalent for arbitrary position-dependent transition amplitudes and any topology (Andrade et al 2009 Phys. Rev. A 80 052301). Although the proof explicitly describes the mapping obtention, its high technicality may hinder relevant physical aspects involved in the equivalence. Discussing concrete examples—the most general constructions for the line, square and honeycomb lattices—here we unveil the similarities and differences of these two versions of quantum walks. We moreover show how to derive the dynamics of one from the other by means of proper projections. We perform calculations for different probability amplitudes such as Hadamard, Grover, discrete Fourier transform and the uncommon in the area (but interesting) discrete Hartley transform, comparing the evolutions. Our study illustrates the models' interplay, an important issue for implementations and applications of such systems.

arXiv:1304.3690•Journal of Physics A Mathematical and Theoretical•Apr 9, 2013•12 citations

Staggered quantum walk on hexagonal lattices

Bruno Chagas, Renato Portugal, Stefan Boettcher +1 more

A discrete-time staggered quantum walk was recently introduced as a generalization that allows the unification of other versions, such as the coined and Szegedy's walk. However, it also produces forms of quantum walks not covered by previous versions. To explore their properties, we study here the staggered walk on a hexagonal lattice. Such a walk is defined using a set of overlapping tessellations that cover the graph edges, and each tessellation is a partition of the node set into cliques. The hexagonal lattice requires at least three tessellations. Each tessellation is associated with a local unitary operator and the product of the local operators defines the evolution operator of the staggered walk on the graph. After defining the evolution operator on the hexagonal lattice, we analyze the quantum walk dynamics with the focus on the position standard deviation and localization. We also obtain analytic results for the time complexity of spatial search algorithms with one marked node using cyclic boundary conditions.

arXiv:1806.10249•Physical Review A•Nov 9, 2018•5 citations

Continuous limit of discrete quantum walks

M N Dheeraj, Todd A. Brun

Quantum walks can be defined in two quite distinct ways: discrete-time and continuous-time quantum walks (DTQWs and CTQWs). For classical random walks, there is a natural sense in which continuous-time walks are a limit of discrete-time walks. Quantum mechanically, in the discrete-time case, an additional ``coin space'' must be appended for the walk to have nontrivial time evolution. Continuous-time quantum walks, however, have no such constraints. This means that there is no completely straightforward way to treat a CTQW as a limit of a DTQW, as can be done in the classical case. Various approaches to this problem have been taken in the past. We give a construction for walks on $d$-regular, $d$-colorable graphs when the coin flip operator is Hermitian: from a standard DTQW we construct a family of discrete-time walks with a well-defined continuous-time limit on a related graph. One can think of this limit as a ``coined'' continuous-time walk. We show that these CTQWs share some properties with coined DTQWs. In particular, we look at a spatial search by a DTQW over the two-dimensional (2D) torus (a grid with periodic boundary conditions) of size $\sqrt{N}\ifmmode\times\else\texttimes\fi{}\sqrt{N}$, where it was shown that a coined DTQW can search in time $O(\sqrt{N}logN)$, but a standard CTQW takes $\mathrm{\ensuremath{\Omega}}(N)$ time to search for a marked element. The continuous limit of the DTQW search over the 2D torus exhibits the $O(\sqrt{N}logN)$ scaling, like the coined walk it is derived from. We also look at the effects of graph symmetry on the limiting walk, and show that the properties are similar to those of the DTQW as shown in Krovi and Brun, Phys. Rev. A 75, 062332 (2007).

arXiv:1501.06950•Physical Review A•Jun 5, 2015•17 citations
We make and generalize the observation that summing of probability amplitudes of a discrete-time quantum walk over partitions of the walking graph consistent with the step operator results in a unitary evolution on the reduced graph which is also a quantum walk. Since the effective walking graph of the projected walk is not necessarily simpler than the original, this may bring new insights into the dynamics of some kinds of quantum walks using known results from thoroughly studied cases like Euclidean lattices. We use abstract treatment of the walking space and walker displacements in aim for a generality of the presented statements. Using this approach we also identify some pathological cases in which the projection mapping breaks down. For walks on lattices, the operation typically results in quantum walks with hyper-dimensional coin spaces. Such walks can, conversely, be viewed as projections of walks on inaccessible, larger spaces, and their properties can be inferred from the parental walk. We show that this is is the case for a lazy quantum walk, a walk with large coherent jumps and a walk on a circle with a twisted boundary condition. We also discuss the relation of this theory to the time-multiplexing optical implementations of quantum walks. Moreover, this manifestly irreversible operation can, in some cases and with a minor adjustment, be undone, and a quantum walk can be reconstructed from a set of its projections.
In this work we introduce discrete-time quantum walks in state space, more precisely on Fock-state lattices. Fock-state lattices provide a natural and clean setting for implementing lattice models, particularly in quantum optical systems. Thus, contrary to the common setting where the walker resides in real space or phase space, here the walk takes place in a synthetic space. We present a general formalism based on Lie algebras and their properties. For each Lie algebra one can associate both a phase space and a Fock-state lattice, and by understanding how these spaces are related, together with the action of generalized displacement operators, we construct the discrete unitary operator that generates the walk. In this framework the displacement operators replace the usual nearest-neighbor shifts and lead to state-dependent tunneling on the lattice. By considering several examples we demonstrate ballistic spreading and other characteristic features of discrete-time quantum walks, such as coin-walker entanglement and symmetry-induced interference patterns. We also show that different algebraic structures can give rise to qualitatively different dynamics, including anomalous behavior such as super-ballistic spreading as well as localization effects.
Measurements on a quantum particle unavoidably affect its state, since the otherwise unitary evolution of the system is interrupted by a nonunitary projection operation. To probe measurement-induced effects in the state dynamics using a quantum simulator, the challenge is to implement controlled measurements on a small subspace of the system and continue the evolution from the complementary subspace. A powerful platform for versatile quantum evolution is represented by photonic quantum walks because of their high control over all relevant parameters. However, measurement-induced dynamics in such a platform have not yet been realized. We implement controlled measurements in a discrete-time quantum walk based on time-multiplexing. This is achieved by adding a deterministic outcoupling of the optical signal to include measurements constrained to specific positions resulting in the projection of the walker's state on the remaining ones. With this platform and coherent input light, we experimentally simulate measurement-induced single-particle quantum dynamics. We demonstrate the difference between dynamics with only a single measurement at the final step and those including measurements during the evolution. To this aim, we study recurrence as a figure of merit, that is, the return probability to the walker's starting position, which is measured in the two cases. We track the development of the return probability over 36 time steps and observe the onset of both recurrent and transient evolution as an effect of the different measurement schemes, a signature which only emerges for quantum systems. Our simulation of the observed one-particle conditional quantum dynamics does not require a genuine quantum particle but is demonstrated with coherent light.
In this paper, we present a study of discrete time quantum walks whose underlying graph is a d-dimensional lattice. The dynamical behavior of these systems is of current interest because of their applications in quantum information theory as tools to design quantum algorithms. We assume that, at each step of the walk evolution, the coin transformation is allowed to change so that we can use it as a control variable to drive the evolution in a desired manner. We give an exact description of the possible evolutions and of the set of possible states that can be achieved with such a system. In particular, we show that it is possible to go from a state where there is probability 1 for the walker to be found in a vertex to a state where all the vertices have equal probability. We also prove a number of properties of the set of admissible states in terms of the number of steps needed to obtain them. We provide explicit algorithms for state transfer in low dimensional cases as well as results that allow to reduce algorithms on two-dimensional lattices to algorithms on the one-dimensional lattice, the cycle.
The two major discrete time formulations for quantum walks, coined and scattering, are unitarily equivalent for arbitrary position-dependent transition amplitudes and any topology (Andrade et al 2009 Phys. Rev. A 80 052301). Although the proof explicitly describes the mapping obtention, its high technicality may hinder relevant physical aspects involved in the equivalence. Discussing concrete examples—the most general constructions for the line, square and honeycomb lattices—here we unveil the similarities and differences of these two versions of quantum walks. We moreover show how to derive the dynamics of one from the other by means of proper projections. We perform calculations for different probability amplitudes such as Hadamard, Grover, discrete Fourier transform and the uncommon in the area (but interesting) discrete Hartley transform, comparing the evolutions. Our study illustrates the models' interplay, an important issue for implementations and applications of such systems.
A discrete-time staggered quantum walk was recently introduced as a generalization that allows the unification of other versions, such as the coined and Szegedy's walk. However, it also produces forms of quantum walks not covered by previous versions. To explore their properties, we study here the staggered walk on a hexagonal lattice. Such a walk is defined using a set of overlapping tessellations that cover the graph edges, and each tessellation is a partition of the node set into cliques. The hexagonal lattice requires at least three tessellations. Each tessellation is associated with a local unitary operator and the product of the local operators defines the evolution operator of the staggered walk on the graph. After defining the evolution operator on the hexagonal lattice, we analyze the quantum walk dynamics with the focus on the position standard deviation and localization. We also obtain analytic results for the time complexity of spatial search algorithms with one marked node using cyclic boundary conditions.
Quantum walks can be defined in two quite distinct ways: discrete-time and continuous-time quantum walks (DTQWs and CTQWs). For classical random walks, there is a natural sense in which continuous-time walks are a limit of discrete-time walks. Quantum mechanically, in the discrete-time case, an additional ``coin space'' must be appended for the walk to have nontrivial time evolution. Continuous-time quantum walks, however, have no such constraints. This means that there is no completely straightforward way to treat a CTQW as a limit of a DTQW, as can be done in the classical case. Various approaches to this problem have been taken in the past. We give a construction for walks on ddd-regular, ddd-colorable graphs when the coin flip operator is Hermitian: from a standard DTQW we construct a family of discrete-time walks with a well-defined continuous-time limit on a related graph. One can think of this limit as a ``coined'' continuous-time walk. We show that these CTQWs share some properties with coined DTQWs. In particular, we look at a spatial search by a DTQW over the two-dimensional (2D) torus (a grid with periodic boundary conditions) of size $\sqrt{N}\ifmmode\times\else\texttimes\fi{}\sqrt{N}$, where it was shown that a coined DTQW can search in time O(NlogN)O(\sqrt{N}logN)O(N​logN), but a standard CTQW takes $\mathrm{\ensuremath{\Omega}}(N)$ time to search for a marked element. The continuous limit of the DTQW search over the 2D torus exhibits the O(NlogN)O(\sqrt{N}logN)O(N​logN) scaling, like the coined walk it is derived from. We also look at the effects of graph symmetry on the limiting walk, and show that the properties are similar to those of the DTQW as shown in Krovi and Brun, Phys. Rev. A 75, 062332 (2007).