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

3 Spectral Properties of Quantum Walks on Rooted Binary Trees

Alain Joye, Laurent Marin

Published Jan 1, 2014• 6 citations
OpenAlex

Abstract

We define coined Quantum Walks on the infinite rooted binary tree given by unitary operators $U(C)$ on an associated infinite dimensional Hilbert space, depending on a unitary coin matrix $C\in U(3)$, and study their spectral properties. For circulant unitary coin matrices $C$, we derive an equation for the Carathéodory function associated to the spectral measure of a cyclic vector for $U(C)$. This allows us to show that for all circulant unitary coin matrices, the spectrum of the Quantum Walk has no singular continuous component. Furthermore, for coin matrices $C$ which are orthogonal circulant matrices, we show that the spectrum of the Quantum Walk is absolutely continuous, except for four coin matrices for which the spectrum of $U(C)$ is pure point.

Related papers

Spectral analysis of three-state quantum walks with general coin matrices

Chusei Kiumi, Jirô Akahori, Takuya Watanabe +1 more

Mathematical analysis of the spectral properties of the time-evolution operator in quantum walks is essential for understanding key dynamical behaviors such as localization and long-term evolution. The inhomogeneous three-state case, in particular, poses substantial analytical challenges due to its higher internal degrees of freedom and the absence of translational invariance. We develop a general framework for the spectral analysis of three-state quantum walks on the one-dimensional lattice with arbitrary time-evolution operators. Our approach is based on a transfer-matrix formulation that reduces the infinite-dimensional eigenvalue problem to a tractable system of two-dimensional recursions, enabling exact characterization of eigenstates. This framework applies broadly to space-inhomogeneous models, including those with finite defects and two-phase structures. We rigorously derive necessary and sufficient conditions for the existence of point spectrum, along with a complete description of the corresponding eigenvalues and eigenstates, which are known to underlie quantum localization phenomena. Furthermore, we give a complete spectral decomposition—discrete spectrum, flat-band eigenvalues (of infinite multiplicity), and absolutely continuous spectrum—with explicit characterization of each component. Using this method, we perform exact numerical analyses of the Fourier walk with spatial inhomogeneity, revealing the emergence of localization despite its delocalized nature in the homogeneous case. Our results provide mathematical tools and physical insights into the structure of quantum walks, offering a systematic path for identifying and characterizing localized quantum states in complex quantum systems.

arXiv:2311.06468•Physical Review Research•Apr 2, 2026•0 citations

Framework for discrete-time quantum walks and a symmetric walk on a binary tree

Zlatko Dimcovic, Daniel Rockwell, Ian Milligan +3 more

We formulate a framework for discrete-time quantum walks, motivated by classical random walks with memory. We present a specific representation of the classical walk with memory 2, on which this is based. The framework has no need for coin spaces, it imposes no constraints on the evolution operator other than unitarity, and is unifying of other approaches. As an example we construct a symmetric discrete-time quantum walk on the semi-infinite binary tree. The generating function of the amplitude at the root is computed in closed form, as a function of time and the initial level $n$ in the tree, and we find the asymptotic and a full numerical solution for the amplitude. It exhibits a sharp interference peak and a power-law tail, as opposed to the exponentially decaying tail of a broadly peaked distribution of the classical symmetric random walk on a binary tree. The probability peak is orders of magnitude larger than it is for the classical walk (already at small $n$). The quantum walk shows a polynomial algorithmic speedup in $n$ over the classical walk, which we conjecture to be of the order $2/3$, based on strong trends in data.

arXiv:1107.4201•Physical Review A•Sep 8, 2011•13 citations

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•147 citations

Spectral property of magnetic quantum walk on hypercube

Ce Wang

In this paper, we introduce and investigate a model of magnetic quantum walk on a general hypercube. We first construct a set of unitary involutions associated with a magnetic potential ν by using quantum Bernoulli noises. And then, with these unitary involutions as the magnetic shift operators, we define the evolution operator W(ν) for the model, where ν is the magnetic potential. We examine the point-spectrum and approximate-spectrum of the evolution operator W(ν) and obtain their representations in terms of the coin operator system of the model. We show that the point-spectrum and approximate-spectrum of W(ν) are completely independent of the magnetic potential ν although W(ν) itself is dependent of the magnetic potential ν. Our work might suggest that a quantum walk perturbed by a magnetic field can have spectral stability with respect to the magnetic potential.

arXiv:2412.18401•Journal of Mathematical Physics•Jan 1, 2025•1 citation

Spectral mapping theorem of an abstract quantum walk

Yusuke Higuchi, Etsuo Segawa, Akito Suzuki

Given two Hilbert spaces, $\mathcal{H}$ and $\mathcal{K}$, we introduce an abstract unitary operator $U$ on $\mathcal{H}$ and its discriminant $T$ on $\mathcal{K}$ induced by a coisometry from $\mathcal{H}$ to $\mathcal{K}$ and a unitary involution on $\mathcal{H}$. In a particular case, these operators $U$ and $T$ become the evolution operator of the Szegedy walk on a graph, possibly infinite, and the transition probability operator thereon. We show the spectral mapping theorem between $U$ and $T$ via the Joukowsky transform. Using this result, we have completely detemined the spectrum of the Grover walk on the Sierpiński lattice, which is pure point and has a Cantor-like structure.

arXiv:1506.06457•Jun 22, 2015•9 citations

Symmetric Quantum Walks on Hamming Graphs and Their Limit Distributions

Robert Griffiths, Shuhei Mano

We study a class of symmetric coined quantum walks on Hamming graphs, where the distance between vertices specifies the transition probability. A special model is the simple quantum walk on the hypercube, which has been discussed in the literature. Eigenvalues of the unitary operator of the quantum walks are zeros of certain self-reciprocal polynomials. We obtain a spectral representation of the wave vector, where our systematic treatment relies on the coin space isomorphic to the state space and the commutative association scheme. The Grover coin is extended to the reflection about a vector in an invariant subspace of the Terwilliger algebra. The limit distributions of several quantum walks are obtained.

arXiv:2509.26243•Symmetry Integrability and Geometry Methods and Applications•Jul 3, 2026•0 citations
We define coined Quantum Walks on the infinite rooted binary tree given by unitary operators U(C)U(C)U(C) on an associated infinite dimensional Hilbert space, depending on a unitary coin matrix C∈U(3)C\in U(3)C∈U(3), and study their spectral properties. For circulant unitary coin matrices CCC, we derive an equation for the Carathéodory function associated to the spectral measure of a cyclic vector for U(C)U(C)U(C). This allows us to show that for all circulant unitary coin matrices, the spectrum of the Quantum Walk has no singular continuous component. Furthermore, for coin matrices CCC which are orthogonal circulant matrices, we show that the spectrum of the Quantum Walk is absolutely continuous, except for four coin matrices for which the spectrum of U(C)U(C)U(C) is pure point.
Mathematical analysis of the spectral properties of the time-evolution operator in quantum walks is essential for understanding key dynamical behaviors such as localization and long-term evolution. The inhomogeneous three-state case, in particular, poses substantial analytical challenges due to its higher internal degrees of freedom and the absence of translational invariance. We develop a general framework for the spectral analysis of three-state quantum walks on the one-dimensional lattice with arbitrary time-evolution operators. Our approach is based on a transfer-matrix formulation that reduces the infinite-dimensional eigenvalue problem to a tractable system of two-dimensional recursions, enabling exact characterization of eigenstates. This framework applies broadly to space-inhomogeneous models, including those with finite defects and two-phase structures. We rigorously derive necessary and sufficient conditions for the existence of point spectrum, along with a complete description of the corresponding eigenvalues and eigenstates, which are known to underlie quantum localization phenomena. Furthermore, we give a complete spectral decomposition—discrete spectrum, flat-band eigenvalues (of infinite multiplicity), and absolutely continuous spectrum—with explicit characterization of each component. Using this method, we perform exact numerical analyses of the Fourier walk with spatial inhomogeneity, revealing the emergence of localization despite its delocalized nature in the homogeneous case. Our results provide mathematical tools and physical insights into the structure of quantum walks, offering a systematic path for identifying and characterizing localized quantum states in complex quantum systems.
We formulate a framework for discrete-time quantum walks, motivated by classical random walks with memory. We present a specific representation of the classical walk with memory 2, on which this is based. The framework has no need for coin spaces, it imposes no constraints on the evolution operator other than unitarity, and is unifying of other approaches. As an example we construct a symmetric discrete-time quantum walk on the semi-infinite binary tree. The generating function of the amplitude at the root is computed in closed form, as a function of time and the initial level nnn in the tree, and we find the asymptotic and a full numerical solution for the amplitude. It exhibits a sharp interference peak and a power-law tail, as opposed to the exponentially decaying tail of a broadly peaked distribution of the classical symmetric random walk on a binary tree. The probability peak is orders of magnitude larger than it is for the classical walk (already at small nnn). The quantum walk shows a polynomial algorithmic speedup in nnn over the classical walk, which we conjecture to be of the order 2/32/32/3, based on strong trends in data.
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 introduce and investigate a model of magnetic quantum walk on a general hypercube. We first construct a set of unitary involutions associated with a magnetic potential ν by using quantum Bernoulli noises. And then, with these unitary involutions as the magnetic shift operators, we define the evolution operator W(ν) for the model, where ν is the magnetic potential. We examine the point-spectrum and approximate-spectrum of the evolution operator W(ν) and obtain their representations in terms of the coin operator system of the model. We show that the point-spectrum and approximate-spectrum of W(ν) are completely independent of the magnetic potential ν although W(ν) itself is dependent of the magnetic potential ν. Our work might suggest that a quantum walk perturbed by a magnetic field can have spectral stability with respect to the magnetic potential.
Given two Hilbert spaces, H\mathcal{H}H and K\mathcal{K}K, we introduce an abstract unitary operator UUU on H\mathcal{H}H and its discriminant TTT on K\mathcal{K}K induced by a coisometry from H\mathcal{H}H to K\mathcal{K}K and a unitary involution on H\mathcal{H}H. In a particular case, these operators UUU and TTT become the evolution operator of the Szegedy walk on a graph, possibly infinite, and the transition probability operator thereon. We show the spectral mapping theorem between UUU and TTT via the Joukowsky transform. Using this result, we have completely detemined the spectrum of the Grover walk on the Sierpiński lattice, which is pure point and has a Cantor-like structure.
We study a class of symmetric coined quantum walks on Hamming graphs, where the distance between vertices specifies the transition probability. A special model is the simple quantum walk on the hypercube, which has been discussed in the literature. Eigenvalues of the unitary operator of the quantum walks are zeros of certain self-reciprocal polynomials. We obtain a spectral representation of the wave vector, where our systematic treatment relies on the coin space isomorphic to the state space and the commutative association scheme. The Grover coin is extended to the reflection about a vector in an invariant subspace of the Terwilliger algebra. The limit distributions of several quantum walks are obtained.