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:1303.5319 · Physics Letters A

Glued trees algorithm under phase damping

Joshua Lockhart, Carlo D. Franco, Mauro Paternostro

Published Nov 28, 2013• 6 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1016/j.physleta.2013.11.034

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

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

Vincent Pouthier, Lucie Pepe, Saad Yalouz

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.

Entropy•Jun 2, 2024•1 citation

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

An analytical study of quantum walk through glued-tree graphs

Zhi-Jian Li, J B Wang

Abstract 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

Quantum Speedup by Quantum Annealing

Rolando D. Somma, Daniel Nagaj, Mária Kieferová

We study the glued-trees problem from A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D. Spielman, in Proceedings of the 35th Annual ACM Symposium on Theory of Computing (ACM, San Diego, CA, 2003), p. 59. in the adiabatic model of quantum computing and provide an annealing schedule to solve an oracular problem exponentially faster than classically possible. The Hamiltonians involved in the quantum annealing do not suffer from the so-called sign problem. Unlike the typical scenario, our schedule is efficient even though the minimum energy gap of the Hamiltonians is exponentially small in the problem size. We discuss generalizations based on initial-state randomization to avoid some slowdowns in adiabatic quantum computing due to small gaps.

arXiv:1202.6257•Physical Review Letters•Jul 31, 2012•177 citations

Quantum fast hitting on glued trees mapped on a photonic chip

Zi-Yu Shi, Hao Long Tang, Zhen Feng +10 more

Quantum walks on graphs play an important role in the field of quantum algorithms. Fast hitting is one of the properties that quantum walk algorithms can utilize to outperform classical random walk algorithms. Fast hitting refers to a particle starting from the entrance node on a graph and trying to hit the exit node quickly. Especially, continuous-time quantum walks on random glued binary trees have been investigated in theories extensively for their exponentially faster hitting speed over classical random walks. Here, using heralded single photons to represent quantum walkers and laser-written waveguide arrays to simulate the theoretical graph, we are able to demonstrate the hitting efficiency of quantum walks with tree depth as high as 16 layers for the first time. Furthermore, we expand the graph’s branching rate from 2 to 5, revealing that quantum walks can exhibit more superiority over classical random walks as the branching rate increases. Our results may shed light on the physical implementation of quantum walk algorithms as well as quantum computation and quantum simulation.

arXiv:1907.12539•Optica•May 5, 2020•20 citations
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.
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 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.
Abstract 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.
We study the glued-trees problem from A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D. Spielman, in Proceedings of the 35th Annual ACM Symposium on Theory of Computing (ACM, San Diego, CA, 2003), p. 59. in the adiabatic model of quantum computing and provide an annealing schedule to solve an oracular problem exponentially faster than classically possible. The Hamiltonians involved in the quantum annealing do not suffer from the so-called sign problem. Unlike the typical scenario, our schedule is efficient even though the minimum energy gap of the Hamiltonians is exponentially small in the problem size. We discuss generalizations based on initial-state randomization to avoid some slowdowns in adiabatic quantum computing due to small gaps.
Quantum walks on graphs play an important role in the field of quantum algorithms. Fast hitting is one of the properties that quantum walk algorithms can utilize to outperform classical random walk algorithms. Fast hitting refers to a particle starting from the entrance node on a graph and trying to hit the exit node quickly. Especially, continuous-time quantum walks on random glued binary trees have been investigated in theories extensively for their exponentially faster hitting speed over classical random walks. Here, using heralded single photons to represent quantum walkers and laser-written waveguide arrays to simulate the theoretical graph, we are able to demonstrate the hitting efficiency of quantum walks with tree depth as high as 16 layers for the first time. Furthermore, we expand the graph’s branching rate from 2 to 5, revealing that quantum walks can exhibit more superiority over classical random walks as the branching rate increases. Our results may shed light on the physical implementation of quantum walk algorithms as well as quantum computation and quantum simulation.