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

Quantum science and technology

Coined Quantum Walks on Graphs

Renato Portugal

Published Jan 1, 2018• 1 citation
Publisher
DOI
10.1007/978-3-319-97813-0_7

Related papers

Entanglement in coined quantum walks on regular graphs

Ivens Carneiro, Meng Loo, Xibai Xu +3 more

Quantum walks, both discrete (coined) and continuous time, form the basis of several recent quantum algorithms. Here we use numerical simulations to study the properties of discrete, coined quantum walks. We investigate the variation in the entanglement between the coin and the position of the particle by calculating the entropy of the reduced density matrix of the coin. We consider both dynamical evolution and asymptotic limits for coins of dimensions from two to eight on regular graphs. For low coin dimensions, quantum walks which spread faster (as measured by the mean square deviation of their distribution from uniform) also exhibit faster convergence towards the asymptotic value of the entanglement between the coin and particle's position. For high-dimensional coins, the DFT coin operator is more efficient at spreading than the Grover coin. We study the entanglement of the coin on regular finite graphs such as cycles, and also show that on complete bipartite graphs, a quantum walk with a Grover coin is always periodic with period four. We generalize the 'glued trees' graph used by Childs et al (2003 Proc. STOC , pp 59–68) to higher branching rate (fan out) and verify that the scaling with branching rate and with tree depth is polynomial.

arXiv:quant-ph/0504042•New Journal of Physics•Jul 12, 2005•140 citations

Open quantum walks on graphs

Stéphane Attal, Francesco Petruccione, Ilya Sinayskiy

arXiv:1401.3305•Physics Letters A•Mar 21, 2012•72 citations

Graph Matching using Interference of Coined Quantum Walks

David Emms, Edwin R. Hancock, Richard C. Wilson

In this paper we consider how coined quantum walks can be applied to exact graph matching. The matching problem is abstracted using an auxiliary structure that connects pairs of vertices from the graphs to be matched by way of auxiliary vertices. We locate matches using coined quantum walks on this structure. We have tested the algorithm on graphs derived from the NCI molecule database and found it to significantly reduce the space of possible matchings thereby allowing the graphs to be matched directly. We also perform a sensitivity analysis on the algorithm in order to examine its behaviour in the presence of noise

Proceedings - International Conference on Pattern Recognition/Proceedings/International Conference on Pattern Recognition•Jan 1, 2006•1 citation

Quantum Walks on Infinite Graphs

Renato Portugal

Springer eBooks•Jan 1, 2013•0 citations

Connecting Coined Quantum Walks with Szegedy's Model

Renato Portugal, Etsuo Segawa

We analyze the equivalence between discrete-time coined quantum walks and Szegedy's quantum walks. We characterize a class of flip-flop coined models with generalized Grover coin on a graph Γ that can be directly converted into Szegedy's model on the subdivision graph of Γ and we describe a method to convert one model into the other. This method improves previous results in literature that need to use the staggered model and the concept of line graph, which are avoided here.

arXiv:1612.02448•Interdisciplinary Information Sciences•Jan 1, 2017•13 citations

Quantum Walks on Finite Graphs

Renato Portugal

Springer eBooks•Jan 1, 2013•0 citations
Quantum walks, both discrete (coined) and continuous time, form the basis of several recent quantum algorithms. Here we use numerical simulations to study the properties of discrete, coined quantum walks. We investigate the variation in the entanglement between the coin and the position of the particle by calculating the entropy of the reduced density matrix of the coin. We consider both dynamical evolution and asymptotic limits for coins of dimensions from two to eight on regular graphs. For low coin dimensions, quantum walks which spread faster (as measured by the mean square deviation of their distribution from uniform) also exhibit faster convergence towards the asymptotic value of the entanglement between the coin and particle's position. For high-dimensional coins, the DFT coin operator is more efficient at spreading than the Grover coin. We study the entanglement of the coin on regular finite graphs such as cycles, and also show that on complete bipartite graphs, a quantum walk with a Grover coin is always periodic with period four. We generalize the 'glued trees' graph used by Childs et al (2003 Proc. STOC , pp 59–68) to higher branching rate (fan out) and verify that the scaling with branching rate and with tree depth is polynomial.
In this paper we consider how coined quantum walks can be applied to exact graph matching. The matching problem is abstracted using an auxiliary structure that connects pairs of vertices from the graphs to be matched by way of auxiliary vertices. We locate matches using coined quantum walks on this structure. We have tested the algorithm on graphs derived from the NCI molecule database and found it to significantly reduce the space of possible matchings thereby allowing the graphs to be matched directly. We also perform a sensitivity analysis on the algorithm in order to examine its behaviour in the presence of noise