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

Continuous-time quantum walks on directed bipartite graphs

Beat Tödtli, Monika Laner, Jouri Semenov, Beatrice Paoli, Marcel Blattner, Jérôme Kunegis

Published Nov 30, 2016• 9 citations
arXivHTMLPDF

Abstract

This paper investigates continuous-time quantum walks on directed bipartite graphs based on a graph's adjacency matrix. We prove that on bipartite graphs, probability transport between the two node partitions can be completely suppressed by tuning a model parameter $\ensuremath{\alpha}$. We provide analytic solutions to the quantum walks for the star and circulant graph classes that are valid for an arbitrary value of the number of nodes $N$, time $t$, and the model parameter $\ensuremath{\alpha}$. We discuss quantitative and qualitative aspects of quantum walks based on directed graphs and their undirected counterparts. Numerical simulations of quantum walks on circulant graphs show complex interference phenomena and how complete suppression of transport is achieved near $\ensuremath{\alpha}=\ensuremath{\pi}/2$. By proving two mirror symmetries around $\ensuremath{\alpha}=0$ and $\ensuremath{\pi}/2$ we show that these quantum walks have a period of $\ensuremath{\pi}$ in $\ensuremath{\alpha}$. We show that undirected edges lose their effect on the quantum walk at $\ensuremath{\alpha}=\ensuremath{\pi}/2$ and present non-bipartite graphs that exhibit suppression of transport. Finally, we analytically compute the Hamiltonians of quantum walks on the directed ring graph.

DOI
10.1103/physreva.94.052338

Related papers

The continuous-time quantum walk on some graphs based on the view of quantum probability

Qi Han, Yaxin Kou, Ning Bai +1 more

In this paper, continuous-time quantum walk is discussed based on the view of quantum probability, i.e. the quantum decomposition of the adjacency matrix A of graph. Regard adjacency matrix A as Hamiltonian which is a real symmetric matrix with elements 0 or 1, so we regard [Formula: see text] as an unbiased evolution operator, which is related to the calculation of probability amplitude. Combining the quantum decomposition and spectral distribution [Formula: see text] of adjacency matrix A, we calculate the probability amplitude reaching each stratum in continuous-time quantum walk on complete bipartite graphs, finite two-dimensional lattices, binary tree, [Formula: see text]-ary tree and [Formula: see text]-fold star power [Formula: see text]. Of course, this method is also suitable for studying some other graphs, such as growing graphs, hypercube graphs and so on, in addition, the applicability of this method is also explained.

International Journal of Quantum Information•Apr 29, 2022•6 citations

Quantum Walk on Dimensionality Reduced Complete Bipartite Graphs with k Edges Removed

Chen-Fu Chiang, Aaron Gregory

Due to scalability issue in current quantum technologies, many quantum algorithms can only be implemented for small size problems. Scalability remains a bottleneck for current quantum technologies. For solving real-life size hard problems in the near-term, we explore classes of search graphs that can be efficiently reduced to a implementable scale for many quantum algorithms. The reduced Hamiltonian preserves the dynamics of the original Hamiltonian. One of the quantum algorithms we choose for the reduced Hamiltonian is continuous time quantum walk (CTQW). We further show how to determine the correct value of the coupling factor of the underlying CTQW. With wrong couple factor values, the optimality (quadratic speedup) from CTQW might be lost. In this work, we extend the class of reducible graphs to complete bipartite graphs with random $k$ edges removed. We further demonstrate through mathematical proof and simulation experiment using IBM Qiskit to show that the quadratic speed-up is preserved for the CTQW.

IEEE Globecom Workshops (GC Wkshps)•Dec 1, 2019•1 citation

Controlled transport in chiral quantum walks on graphs

Yi-Cong Yu, Xiaoming Cai

Abstract We investigate novel transport properties of chiral continuous-time quantum walks (CTQWs) on graphs. By employing a gauge transformation, we demonstrate that CTQWs on chiral chains are equivalent to those on non-chiral chains, but with additional momenta from initial wave packets. This explains the novel transport phenomenon numerically studied in (Khalique et al 2021 New J. Phys. 23 083005). Building on this, we delve deeper into the analysis of chiral CTQWs on the Y-junction graph, introducing phases to account for the chirality. The phase plays a key role in controlling both asymmetric transport and directed complete transport among the chains in the Y-junction graph. We systematically analyze these features through a comprehensive examination of the chiral CTQW on a Y-junction graph. Our analysis shows that the CTQW on Y-junction graph can be modeled as a combination of three wave functions, each of which evolves independently on three effective open chains. By constructing a lattice scattering theory, we calculate the phase shift of a wave packet after it interacts with the potential-shifted boundary. Our results demonstrate that the interplay of these phase shifts leads to the observed enhancement and suppression of quantum transport. The explicit condition for directed complete transport or 100 % efficiency is analytically derived. Our theory has applications in building quantum versions of binary tree search algorithms.

arXiv:2308.12516•New Journal of Physics•Aug 1, 2023•1 citation

Quantum walk search on the complete bipartite graph

Mason L. Rhodes, Thomas G. Wong

The coined quantum walk is a discretization of the Dirac equation of relativistic quantum mechanics, and it is the basis of many quantum algorithms. We investigate how it searches the complete bipartite graph of $N$ vertices for one of $k$ marked vertices with different initial states. We prove an intriguing dependence on the number of marked and unmarked vertices in each partite set. For example, when the graph is irregular and the initial state is the typical uniform superposition over the vertices, then the success probability can vary greatly from one time step to the next, even alternating between 0 and 1, so the precise time at which measurement occurs is crucial. When the initial state is a uniform superposition over the edges, however, the success probability evolves smoothly. As another example, if the complete bipartite graph is regular, then the two initial states are equivalent. Then if two marked vertices are in the same partite set, the success probability reaches $1/2$, but if they are in different partite sets, it instead reaches 1. This differs from the complete graph, which is the quantum walk formulation of Grover's algorithm, where the success probability with two marked vertices is $8/9$. This reveals a contrast to the continuous-time quantum walk, whose evolution is governed by Schr\"odinger's equation, which asymptotically searches the regular complete bipartite graph with any arrangement of marked vertices in the same manner as the complete graph.

arXiv:1812.06079•Physical Review A•Mar 1, 2019•31 citations

Floquet engineering of continuous-time quantum walks: Toward the simulation of complex and next-nearest-neighbor couplings

Leonardo Novo, Sofia Ribeiro

The formalism of continuous-time quantum walks on graphs has been widely used in the study of quantum transport of energy and information, as well as in the development of quantum algorithms. In experimental settings, however, there is limited control over the coupling coefficients between the different nodes of the graph (which are usually considered to be real valued), thereby restricting the types of quantum walks that can be implemented. In this paper, we apply the idea of Floquet engineering in the context of continuous-time quantum walks, i.e., we define periodically driven Hamiltonians which can be used to simulate the dynamics of certain target continuous-time quantum walks. We focus on two main applications: (i) simulating quantum walks that break time-reversal symmetry due to complex coupling coefficients and (ii) increasing the connectivity of the graph by simulating the presence of next-nearest-neighbor couplings. Our paper provides explicit simulation protocols that may be used for directing quantum transport, engineering the dispersion relation of one-dimensional quantum walks, or investigating quantum dynamics in highly connected structures.

arXiv:2012.00448•Physical Review A•Apr 26, 2021•9 citations

On the quantum simulation of complex networks

Duarte Magano, João P. Moutinho, Bruno Coelho Coutinho

Quantum walks provide a natural framework to approach graph problems with quantum computers, exhibiting speedups over their classical counterparts for tasks such as the search for marked nodes or the prediction of missing links. Continuous-time quantum walk algorithms assume that we can simulate the dynamics of quantum systems where the Hamiltonian is given by the adjacency matrix of the graph. It is known that such can be simulated efficiently if the underlying graph is row-sparse and efficiently row-computable. While this is sufficient for many applications, it limits the applicability for this class of algorithms to study real world complex networks, which, among other properties, are characterized by the existence of a few densely connected nodes, called hubs. In other words, complex networks are typically not row-sparse, even though the average connectivity over all nodes can be very small. In this work, we extend the state-of-the-art results on quantum simulation to graphs that contain a small number of hubs, but that are otherwise sparse. Hopefully, our results may lead to new applications of quantum computing to network science.

arXiv:2212.06126•SciPost Physics Core•Aug 24, 2023•6 citations
This paper investigates continuous-time quantum walks on directed bipartite graphs based on a graph's adjacency matrix. We prove that on bipartite graphs, probability transport between the two node partitions can be completely suppressed by tuning a model parameter \ensuremathα\ensuremath{\alpha}\ensuremathα. We provide analytic solutions to the quantum walks for the star and circulant graph classes that are valid for an arbitrary value of the number of nodes NNN, time ttt, and the model parameter \ensuremathα\ensuremath{\alpha}\ensuremathα. We discuss quantitative and qualitative aspects of quantum walks based on directed graphs and their undirected counterparts. Numerical simulations of quantum walks on circulant graphs show complex interference phenomena and how complete suppression of transport is achieved near \ensuremathα=\ensuremathπ/2\ensuremath{\alpha}=\ensuremath{\pi}/2\ensuremathα=\ensuremathπ/2. By proving two mirror symmetries around \ensuremathα=0\ensuremath{\alpha}=0\ensuremathα=0 and \ensuremathπ/2\ensuremath{\pi}/2\ensuremathπ/2 we show that these quantum walks have a period of \ensuremathπ\ensuremath{\pi}\ensuremathπ in \ensuremathα\ensuremath{\alpha}\ensuremathα. We show that undirected edges lose their effect on the quantum walk at \ensuremathα=\ensuremathπ/2\ensuremath{\alpha}=\ensuremath{\pi}/2\ensuremathα=\ensuremathπ/2 and present non-bipartite graphs that exhibit suppression of transport. Finally, we analytically compute the Hamiltonians of quantum walks on the directed ring graph.
In this paper, continuous-time quantum walk is discussed based on the view of quantum probability, i.e. the quantum decomposition of the adjacency matrix A of graph. Regard adjacency matrix A as Hamiltonian which is a real symmetric matrix with elements 0 or 1, so we regard [Formula: see text] as an unbiased evolution operator, which is related to the calculation of probability amplitude. Combining the quantum decomposition and spectral distribution [Formula: see text] of adjacency matrix A, we calculate the probability amplitude reaching each stratum in continuous-time quantum walk on complete bipartite graphs, finite two-dimensional lattices, binary tree, [Formula: see text]-ary tree and [Formula: see text]-fold star power [Formula: see text]. Of course, this method is also suitable for studying some other graphs, such as growing graphs, hypercube graphs and so on, in addition, the applicability of this method is also explained.
Due to scalability issue in current quantum technologies, many quantum algorithms can only be implemented for small size problems. Scalability remains a bottleneck for current quantum technologies. For solving real-life size hard problems in the near-term, we explore classes of search graphs that can be efficiently reduced to a implementable scale for many quantum algorithms. The reduced Hamiltonian preserves the dynamics of the original Hamiltonian. One of the quantum algorithms we choose for the reduced Hamiltonian is continuous time quantum walk (CTQW). We further show how to determine the correct value of the coupling factor of the underlying CTQW. With wrong couple factor values, the optimality (quadratic speedup) from CTQW might be lost. In this work, we extend the class of reducible graphs to complete bipartite graphs with random kkk edges removed. We further demonstrate through mathematical proof and simulation experiment using IBM Qiskit to show that the quadratic speed-up is preserved for the CTQW.
Abstract We investigate novel transport properties of chiral continuous-time quantum walks (CTQWs) on graphs. By employing a gauge transformation, we demonstrate that CTQWs on chiral chains are equivalent to those on non-chiral chains, but with additional momenta from initial wave packets. This explains the novel transport phenomenon numerically studied in (Khalique et al 2021 New J. Phys. 23 083005). Building on this, we delve deeper into the analysis of chiral CTQWs on the Y-junction graph, introducing phases to account for the chirality. The phase plays a key role in controlling both asymmetric transport and directed complete transport among the chains in the Y-junction graph. We systematically analyze these features through a comprehensive examination of the chiral CTQW on a Y-junction graph. Our analysis shows that the CTQW on Y-junction graph can be modeled as a combination of three wave functions, each of which evolves independently on three effective open chains. By constructing a lattice scattering theory, we calculate the phase shift of a wave packet after it interacts with the potential-shifted boundary. Our results demonstrate that the interplay of these phase shifts leads to the observed enhancement and suppression of quantum transport. The explicit condition for directed complete transport or 100 % efficiency is analytically derived. Our theory has applications in building quantum versions of binary tree search algorithms.
The coined quantum walk is a discretization of the Dirac equation of relativistic quantum mechanics, and it is the basis of many quantum algorithms. We investigate how it searches the complete bipartite graph of NNN vertices for one of kkk marked vertices with different initial states. We prove an intriguing dependence on the number of marked and unmarked vertices in each partite set. For example, when the graph is irregular and the initial state is the typical uniform superposition over the vertices, then the success probability can vary greatly from one time step to the next, even alternating between 0 and 1, so the precise time at which measurement occurs is crucial. When the initial state is a uniform superposition over the edges, however, the success probability evolves smoothly. As another example, if the complete bipartite graph is regular, then the two initial states are equivalent. Then if two marked vertices are in the same partite set, the success probability reaches 1/21/21/2, but if they are in different partite sets, it instead reaches 1. This differs from the complete graph, which is the quantum walk formulation of Grover's algorithm, where the success probability with two marked vertices is 8/98/98/9. This reveals a contrast to the continuous-time quantum walk, whose evolution is governed by Schr\"odinger's equation, which asymptotically searches the regular complete bipartite graph with any arrangement of marked vertices in the same manner as the complete graph.
The formalism of continuous-time quantum walks on graphs has been widely used in the study of quantum transport of energy and information, as well as in the development of quantum algorithms. In experimental settings, however, there is limited control over the coupling coefficients between the different nodes of the graph (which are usually considered to be real valued), thereby restricting the types of quantum walks that can be implemented. In this paper, we apply the idea of Floquet engineering in the context of continuous-time quantum walks, i.e., we define periodically driven Hamiltonians which can be used to simulate the dynamics of certain target continuous-time quantum walks. We focus on two main applications: (i) simulating quantum walks that break time-reversal symmetry due to complex coupling coefficients and (ii) increasing the connectivity of the graph by simulating the presence of next-nearest-neighbor couplings. Our paper provides explicit simulation protocols that may be used for directing quantum transport, engineering the dispersion relation of one-dimensional quantum walks, or investigating quantum dynamics in highly connected structures.
Quantum walks provide a natural framework to approach graph problems with quantum computers, exhibiting speedups over their classical counterparts for tasks such as the search for marked nodes or the prediction of missing links. Continuous-time quantum walk algorithms assume that we can simulate the dynamics of quantum systems where the Hamiltonian is given by the adjacency matrix of the graph. It is known that such can be simulated efficiently if the underlying graph is row-sparse and efficiently row-computable. While this is sufficient for many applications, it limits the applicability for this class of algorithms to study real world complex networks, which, among other properties, are characterized by the existence of a few densely connected nodes, called hubs. In other words, complex networks are typically not row-sparse, even though the average connectivity over all nodes can be very small. In this work, we extend the state-of-the-art results on quantum simulation to graphs that contain a small number of hubs, but that are otherwise sparse. Hopefully, our results may lead to new applications of quantum computing to network science.