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:2112.02846 · Physical Review A

Decoherence on staggered quantum walks

Raqueline A. M. Santos, Franklin de Lima Marquezino

Published Mar 30, 2022• 4 citations
arXivHTMLPDF

Abstract

The decoherence phenomenon has been widely studied in different types of quantum walks. In this work we show how to model decoherence inspired by percolation on staggered quantum walks. Two models of unitary noise are described: breaking polygons and breaking vertices. The evolution operators subject to these noises are obtained, and the equivalence to the coined quantum walk model is presented. Further, we numerically analyze the effect of these decoherence models on the two-dimensional grid of 4-cliques. We examine how these perturbations affect the quantum walk based search algorithm in this graph and how expanding the tessellation intersection can make it more robust against decoherence.

DOI
10.1103/physreva.105.032452

Related papers

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

An Algebraic Model for Simulation of Percolation Decoherence on Quantum-Walk-Based Search Algorithms

Gabriel Mauricio Oswald Vieira, Rui Aldé-Lopes, Nelson Maculan +1 more

In this paper, we propose a linear algebra based model for percolation noise simulation in quantum-walk-based searches to analyze the impact on the success probability of the search. The model was built to allow an open and simultaneous simulation of any type of noise that represents an edge-break, which we show to be a well-behaved family of permutation matrices that maintain a particular set theory relation when acting as some system evolution operators. The simulation evolves using only linear algebra operations, opening avenues for easier analyses of unexpected observed convergence behaviour. As a use case, we investigate the simulation of a lackadaisical quantum walk with percolation noise.

•Jul 19, 2024•0 citations

Quantum search on the two-dimensional lattice using the staggered model with Hamiltonians

Renato Portugal, Tharso D. Fernandes

Quantum search on the two-dimensional lattice with one marked vertex and cyclic boundary conditions is an important problem in the context of quantum algorithms with an interesting unfolding. It avails to test the ability of quantum walk models to provide efficient algorithms from the theoretical side and means to implement quantum walks in laboratories from the practical side. In this paper, we rigorously prove that the recent-proposed staggered quantum walk model provides an efficient quantum search on the two-dimensional lattice, if the reflection operators associated with the graph tessellations are used as Hamiltonians, which is an important theoretical result for validating the staggered model with Hamiltonians. Numerical results show that on the two-dimensional lattice staggered models without Hamiltonians are not as efficient as the one described in this paper and are, in fact, as slow as classical random-walk-based algorithms.

arXiv:1701.01468•Physical Review A•Apr 26, 2017•19 citations

Decoherence in two-dimensional quantum walks with two- and four-state coins

Yu‐Guang Yang, Xixi Wang, Jian Li +3 more

Two-dimensional quantum walks using a two-state coin have simpler experimental implementation than two-dimensional quantum walks using a four-state coin. However, decoherence occurs inevitably during the evolution of quantum walks due to the coupling between the quantum systems and their environment. Thus, it is interesting to investigate the robustness against decoherence for two- and four-state two-dimensional quantum walks. Here, we investigate the effects of the decoherence on two- and four-state two-dimensional quantum walks produced by the broken-link-type noise and compare their robustness against the broken-link-type noise. Specifically, we analyze the quantum correlation between the two spatial dimensions x and y by using measurement-induced disturbance for the two-state quantum walks, i.e. the alternate walk and the Pauli walk, and the four-state quantum walks, i.e. the Grover, Hadamard and Fourier walks, respectively. Our analysis shows that the two-state walks are more robust against the broken-link-type noise than the four-state walks.

Modern Physics Letters A•Sep 28, 2021•2 citations

Percolation induced effects in two-dimensional coined quantum walks: analytic asymptotic solutions

Bálint Kollár, Jaroslav Novotný, T. Kiss +1 more

Quantum walks on graphs can model physical processes and serve as efficient tools in quantum information theory. Once we admit random variations in the connectivity of the underlying graph, we arrive at the problem of percolation, where the long-time behaviour appears untreatable with direct numerical methods. We develop novel analytic methods based on the theory of random unitary operations which help us to determine explicitly the asymptotic dynamics of quantum walks on two-dimensional finite integer lattices with percolation. Based on this theory, we find new unexpected features of percolated walks like asymptotic position inhomogeneity or special directional symmetry breaking.

arXiv:1401.5668•New Journal of Physics•Feb 4, 2014•16 citations

Decoherence in two-dimensional quantum walks

Amanda C. Oliveira, Renato Portugal, R. Donangelo

We analyze the decoherence in quantum walks in two-dimensional lattices generated by broken-link-type noise. In this type of decoherence, the links of the lattice are randomly broken with some given constant probability. We obtain the evolution equation for a quantum walker moving on two-dimensional (2D) lattices subject to this noise, and we point out how to generalize for lattices in more dimensions. In the nonsymmetric case, when the probability of breaking links in one direction is different from the probability in the perpendicular direction, we have obtained a nontrivial result. If one fixes the link-breaking probability in one direction, and gradually increases the probability in the other direction from 0 to 1, the decoherence initially increases until it reaches a maximum value, and then it decreases. This means that, in some cases, one can increase the noise level and still obtain more coherence. Physically, this can be explained as a transition from a decoherent 2D walk to a coherent 1D walk.

Physical Review A•Jul 18, 2006•94 citations
The decoherence phenomenon has been widely studied in different types of quantum walks. In this work we show how to model decoherence inspired by percolation on staggered quantum walks. Two models of unitary noise are described: breaking polygons and breaking vertices. The evolution operators subject to these noises are obtained, and the equivalence to the coined quantum walk model is presented. Further, we numerically analyze the effect of these decoherence models on the two-dimensional grid of 4-cliques. We examine how these perturbations affect the quantum walk based search algorithm in this graph and how expanding the tessellation intersection can make it more robust against decoherence.
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.
In this paper, we propose a linear algebra based model for percolation noise simulation in quantum-walk-based searches to analyze the impact on the success probability of the search. The model was built to allow an open and simultaneous simulation of any type of noise that represents an edge-break, which we show to be a well-behaved family of permutation matrices that maintain a particular set theory relation when acting as some system evolution operators. The simulation evolves using only linear algebra operations, opening avenues for easier analyses of unexpected observed convergence behaviour. As a use case, we investigate the simulation of a lackadaisical quantum walk with percolation noise.
Quantum search on the two-dimensional lattice with one marked vertex and cyclic boundary conditions is an important problem in the context of quantum algorithms with an interesting unfolding. It avails to test the ability of quantum walk models to provide efficient algorithms from the theoretical side and means to implement quantum walks in laboratories from the practical side. In this paper, we rigorously prove that the recent-proposed staggered quantum walk model provides an efficient quantum search on the two-dimensional lattice, if the reflection operators associated with the graph tessellations are used as Hamiltonians, which is an important theoretical result for validating the staggered model with Hamiltonians. Numerical results show that on the two-dimensional lattice staggered models without Hamiltonians are not as efficient as the one described in this paper and are, in fact, as slow as classical random-walk-based algorithms.
Two-dimensional quantum walks using a two-state coin have simpler experimental implementation than two-dimensional quantum walks using a four-state coin. However, decoherence occurs inevitably during the evolution of quantum walks due to the coupling between the quantum systems and their environment. Thus, it is interesting to investigate the robustness against decoherence for two- and four-state two-dimensional quantum walks. Here, we investigate the effects of the decoherence on two- and four-state two-dimensional quantum walks produced by the broken-link-type noise and compare their robustness against the broken-link-type noise. Specifically, we analyze the quantum correlation between the two spatial dimensions x and y by using measurement-induced disturbance for the two-state quantum walks, i.e. the alternate walk and the Pauli walk, and the four-state quantum walks, i.e. the Grover, Hadamard and Fourier walks, respectively. Our analysis shows that the two-state walks are more robust against the broken-link-type noise than the four-state walks.
Quantum walks on graphs can model physical processes and serve as efficient tools in quantum information theory. Once we admit random variations in the connectivity of the underlying graph, we arrive at the problem of percolation, where the long-time behaviour appears untreatable with direct numerical methods. We develop novel analytic methods based on the theory of random unitary operations which help us to determine explicitly the asymptotic dynamics of quantum walks on two-dimensional finite integer lattices with percolation. Based on this theory, we find new unexpected features of percolated walks like asymptotic position inhomogeneity or special directional symmetry breaking.
We analyze the decoherence in quantum walks in two-dimensional lattices generated by broken-link-type noise. In this type of decoherence, the links of the lattice are randomly broken with some given constant probability. We obtain the evolution equation for a quantum walker moving on two-dimensional (2D) lattices subject to this noise, and we point out how to generalize for lattices in more dimensions. In the nonsymmetric case, when the probability of breaking links in one direction is different from the probability in the perpendicular direction, we have obtained a nontrivial result. If one fixes the link-breaking probability in one direction, and gradually increases the probability in the other direction from 0 to 1, the decoherence initially increases until it reaches a maximum value, and then it decreases. This means that, in some cases, one can increase the noise level and still obtain more coherence. Physically, this can be explained as a transition from a decoherent 2D walk to a coherent 1D walk.