© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

Entropy

Continuous-Time Quantum Walk in Glued Trees: Localized State-Mediated Almost Perfect Quantum-State Transfer

Vincent Pouthier, Lucie Pepe, Saad Yalouz

Published Jun 2, 2024• 1 citation

Abstract

In this work, the dynamics of a quantum walker on glued trees is revisited to understand the influence of the architecture of the graph on the efficiency of the transfer between the two roots. Instead of considering regular binary trees, we focus our attention on leafier structures where each parent node could give rise to a larger number of children. Through extensive numerical simulations, we uncover a significant dependence of the transfer on the underlying graph architecture, particularly influenced by the branching rate (M) relative to the root degree (N). Our study reveals that the behavior of the walker is isomorphic to that of a particle moving on a finite-size chain. This chain exhibits defects that originate in the specific nature of both the roots and the leaves. Therefore, the energy spectrum of the chain showcases rich features, which lead to diverse regimes for the quantum-state transfer. Notably, the formation of quasi-degenerate localized states due to significant disparities between M and N triggers a localization process on the roots. Through analytical development, we demonstrate that these states play a crucial role in facilitating almost perfect quantum beats between the roots, thereby enhancing the transfer efficiency. Our findings offer valuable insights into the mechanisms governing quantum-state transfer on trees, with potential applications for the transfer of quantum information.

DOI: 10.3390/e26060490

Related papers

Quantum snake walk on graphs

Ansis Rosmanis

I introduce a continuous-time quantum walk on graphs called the quantum snake walk, the basis states of which are fixed-length paths (snakes) in the underlying graph. First, I analyze the quantum snake walk on the line, and I show that, even though most states stay localized throughout the evolution, there are specific states that most likely move on the line as wave packets with momentum inversely proportional to the length of the snake. Next, I discuss how an algorithm based on the quantum snake walk might potentially be able to solve an extended version of the glued trees problem, which asks to find a path connecting both roots of the glued trees graph. To the best of my knowledge, no efficient quantum algorithm solving this problem is known yet.

arXiv:1004.4054•Physical Review A•Feb 7, 2011•6 citations

State transfer on two-fold Cayley trees via quantum walks*

Xiling Xue, Yue Ruan

Perfect state transfer (PST) has great significance due to its applications in quantum information processing and quantum computation. The main problem we study in this paper is to determine whether the two-fold Cayley tree, an extension of the Cayley tree, admits perfect state transfer between two roots using quantum walks. We show that PST can be achieved by means of the so-called nonrepeating quantum walk [Phys. Rev. A 89 042332 (2014)] within time steps that are the distance between the two roots; while both the continuous-time quantum walk and the typical discrete-time quantum walk with Grover coin approaches fail. Our results suggest that in some cases the dynamics of a discrete-time quantum walk may be much richer than that of the continuous-time quantum walk.

Chinese Physics B•Dec 2, 2020•2 citations

Perfect State Transfer in Quantum Walks on Graphs

Viv M. Kendon, Christino Tamon

We provide a brief survey of perfect state transfer in quantum walks on finite graphs. The ability to transfer a quantum state from one part of a quantum computer to another is a key ingredient of scalable architectures. Transfer through structures that do not require locally varying dynamic control simplifies the design and hence reduces the opportunities for errors to arise. Continuous time walks quantum walks on highly structured graphs exhibit perfect state transfer for the complete graph of size 2, the path of length 3, and the cycle of size 4. From these, larger graphs can be constructed, and the use of edge weights widens this set considerably. Discrete-time quantum walks have more flexibility through exploiting the coin degrees of freedom, but with the disadvantage that local control of the coin is required if the degree of the vertices varies. The closely related property of periodicity (exact return to the starting state) is also mentioned.

Journal of Computational and Theoretical Nanoscience•Mar 1, 2011•109 citations

Two-level quantum walkers on directed graphs. II. Application to quantum random access memory

Ryo Asaka, Kazumitsu Sakai, Ryoko Yahagi

This is the second paper in a series of two. Using a multiparticle continuous-time quantum walk with two internal states, which was formulated in the first paper [R. Asaka et al., preceding paper, Phys. Rev. A 107, 022415 (2023)], we physically implement a quantum random access memory (QRAM). Data with address information are dual-rail encoded into quantum walkers. The walkers pass through perfect binary trees to access the designated memory cells and copy the data stored in the cells. A roundabout gate allocated at each node serves as a router to move the walker from the parent node to one of two child nodes, depending on the internal state of the walker. In this process, the address information is sequentially encoded into the internal states so that the walkers are adequately delivered to the target cells. The present QRAM, which processes ${2}^{n}\phantom{\rule{4pt}{0ex}}m$-qubit data, is implemented in a quantum circuit of depth $O(nlog(n+m))$ and requires $O(n+m)$ qubit resources. This is more efficient than the conventional bucket-brigade QRAM that requires $O({n}^{2}+nm)$ steps and $O({2}^{n}+m)$ qubit resources for processing. Moreover, since the walkers are not entangled with any device on the binary trees, the cost of maintaining coherence can be reduced. Notably, by simply passing quantum walkers through binary trees, data can be automatically extracted in a quantum superposition state. In other words, any time-dependent control is not required.

arXiv:2204.08709•Physical Review A•Feb 13, 2023•8 citations

Glued trees algorithm under phase damping

Joshua Lockhart, Carlo D. Franco, Mauro Paternostro

We study the behaviour of the glued trees algorithm described by Childs et al. in [STOC `03, Proc. 35th ACM Symposium on Theory of Computing (2004) 59] under decoherence. We consider a discrete time reformulation of the continuous time quantum walk protocol and apply a phase damping channel to the coin state, investigating the effect of such a mechanism on the probability of the walker appearing on the target vertex of the graph. We pay particular attention to any potential advantage coming from the use of weak decoherence for the spreading of the walk across the glued trees graph.

arXiv:1303.5319•Physics Letters A•Nov 28, 2013•5 citations

An analytical study of quantum walk through glued-tree graphs

Zhi-Jian Li, J B Wang

In this paper, we analytically investigated the transmission properties of continuous time quantum walks through two types of glued-tree graphs. By mapping the glued-tree graphs onto a non-uniform lattice line, we obtained their bound eigen-energies, which provided a clear and quantitative understanding of the associated resonant transmission behaviours. We also observed interesting zero-mode resonant transmissions, which correspond to zero-energy bound states, for both types of glued-tree graphs with classical Markov transition matrix parameters. By changing the system parameters at the glued nodes, we are able to control the position of the resonant tunnelling peaks.

arXiv:1412.8745•Journal of Physics A Mathematical and Theoretical•Aug 12, 2015•13 citations

In this work, the dynamics of a quantum walker on glued trees is revisited to understand the influence of the architecture of the graph on the efficiency of the transfer between the two roots. Instead of considering regular binary trees, we focus our attention on leafier structures where each parent node could give rise to a larger number of children. Through extensive numerical simulations, we uncover a significant dependence of the transfer on the underlying graph architecture, particularly influenced by the branching rate (M) relative to the root degree (N). Our study reveals that the behavior of the walker is isomorphic to that of a particle moving on a finite-size chain. This chain exhibits defects that originate in the specific nature of both the roots and the leaves. Therefore, the energy spectrum of the chain showcases rich features, which lead to diverse regimes for the quantum-state transfer. Notably, the formation of quasi-degenerate localized states due to significant disparities between M and N triggers a localization process on the roots. Through analytical development, we demonstrate that these states play a crucial role in facilitating almost perfect quantum beats between the roots, thereby enhancing the transfer efficiency. Our findings offer valuable insights into the mechanisms governing quantum-state transfer on trees, with potential applications for the transfer of quantum information.

I introduce a continuous-time quantum walk on graphs called the quantum snake walk, the basis states of which are fixed-length paths (snakes) in the underlying graph. First, I analyze the quantum snake walk on the line, and I show that, even though most states stay localized throughout the evolution, there are specific states that most likely move on the line as wave packets with momentum inversely proportional to the length of the snake. Next, I discuss how an algorithm based on the quantum snake walk might potentially be able to solve an extended version of the glued trees problem, which asks to find a path connecting both roots of the glued trees graph. To the best of my knowledge, no efficient quantum algorithm solving this problem is known yet.

Perfect state transfer (PST) has great significance due to its applications in quantum information processing and quantum computation. The main problem we study in this paper is to determine whether the two-fold Cayley tree, an extension of the Cayley tree, admits perfect state transfer between two roots using quantum walks. We show that PST can be achieved by means of the so-called nonrepeating quantum walk [Phys. Rev. A 89 042332 (2014)] within time steps that are the distance between the two roots; while both the continuous-time quantum walk and the typical discrete-time quantum walk with Grover coin approaches fail. Our results suggest that in some cases the dynamics of a discrete-time quantum walk may be much richer than that of the continuous-time quantum walk.

We provide a brief survey of perfect state transfer in quantum walks on finite graphs. The ability to transfer a quantum state from one part of a quantum computer to another is a key ingredient of scalable architectures. Transfer through structures that do not require locally varying dynamic control simplifies the design and hence reduces the opportunities for errors to arise. Continuous time walks quantum walks on highly structured graphs exhibit perfect state transfer for the complete graph of size 2, the path of length 3, and the cycle of size 4. From these, larger graphs can be constructed, and the use of edge weights widens this set considerably. Discrete-time quantum walks have more flexibility through exploiting the coin degrees of freedom, but with the disadvantage that local control of the coin is required if the degree of the vertices varies. The closely related property of periodicity (exact return to the starting state) is also mentioned.

This is the second paper in a series of two. Using a multiparticle continuous-time quantum walk with two internal states, which was formulated in the first paper [R. Asaka et al., preceding paper, Phys. Rev. A 107, 022415 (2023)], we physically implement a quantum random access memory (QRAM). Data with address information are dual-rail encoded into quantum walkers. The walkers pass through perfect binary trees to access the designated memory cells and copy the data stored in the cells. A roundabout gate allocated at each node serves as a router to move the walker from the parent node to one of two child nodes, depending on the internal state of the walker. In this process, the address information is sequentially encoded into the internal states so that the walkers are adequately delivered to the target cells. The present QRAM, which processes

{2}^{n}\phantom{\rule{4pt}{0ex}}m

-qubit data, is implemented in a quantum circuit of depth

O(nlog(n+m))

and requires

O(n+m)

qubit resources. This is more efficient than the conventional bucket-brigade QRAM that requires

O({n}^{2}+nm)

steps and

O({2}^{n}+m)

qubit resources for processing. Moreover, since the walkers are not entangled with any device on the binary trees, the cost of maintaining coherence can be reduced. Notably, by simply passing quantum walkers through binary trees, data can be automatically extracted in a quantum superposition state. In other words, any time-dependent control is not required.

We study the behaviour of the glued trees algorithm described by Childs et al. in [STOC `03, Proc. 35th ACM Symposium on Theory of Computing (2004) 59] under decoherence. We consider a discrete time reformulation of the continuous time quantum walk protocol and apply a phase damping channel to the coin state, investigating the effect of such a mechanism on the probability of the walker appearing on the target vertex of the graph. We pay particular attention to any potential advantage coming from the use of weak decoherence for the spreading of the walk across the glued trees graph.

In this paper, we analytically investigated the transmission properties of continuous time quantum walks through two types of glued-tree graphs. By mapping the glued-tree graphs onto a non-uniform lattice line, we obtained their bound eigen-energies, which provided a clear and quantitative understanding of the associated resonant transmission behaviours. We also observed interesting zero-mode resonant transmissions, which correspond to zero-energy bound states, for both types of glued-tree graphs with classical Markov transition matrix parameters. By changing the system parameters at the glued nodes, we are able to control the position of the resonant tunnelling peaks.