arXiv:1610.08421

Indistinguishable quantum walks on graphs relative to a bipartite quantum walker

Phillip R. Dukes

Published Oct 26, 2016• 0 citations

Abstract

A distinguishability operator is defined for the continuous-time quantum walk (CTQW) of a bipartite quantum walker on two simply connected graphs, $W_{G_i,G_j} = U_{G_i}\left(t\right) \otimes U_{G_j}\left(t'\right) - U_{G_j}\left(t'\right) \otimes U_{G_i}\left(t\right)$, where $U_{G_i}\left(t\right)$ is the unitary CTQW operator for a labeled graph $G_i$ over a time interval $t$. The null space of $W_{G_i,G_j}$ defines the vector space of initial bipartite states whose time development is either constant or only dependent on $t + t'$ and is invariant to which quantum walker subsystem goes with each graph. The set of null spaces corresponding with a set of $W_{G_i,G_j}$ have interesting relations as subspaces, intersections between subspaces, and subspaces of intersections. These relations are depicted as Euler diagrams for labeled graphs of three and four vertices.

DOI: 10.48550/arxiv.1610.08421

Related papers

Continuous-time quantum walks over connected graphs, amplitudes and invariants

Phillip Dukes

arXiv:1506.03086Jun 9, 20150 citations

Quantum walk on a chimera graph

Shu Xu, Xiangxiang Sun, Jizhou Wu +3 more

arXiv:1705.11036New Journal of PhysicsMar 15, 20185 citations

Implementation of a continuous-time quantum walk on a sparse graph

Zhaoyang Chen, Guanzhong Li, Lvzhou Li

arXiv:2408.10553Physical Review ANov 15, 20246 citations

A Continuous - Time Quantum Walk for Attributed GraphsMatching

Tewabe Chekole Workneh

Oct 30, 20130 citations

Continuous-time quantum walk of two interacting fermions on a cycle graph

Alexey A. Melnikov, Leonid Evgenevich Fedichkin

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIEDec 30, 20168 citations

A Continuous - Time Quantum Walk for Attributed Graphs Matching

Tewabe Chekole

arXiv:1801.10339Jan 31, 20180 citations

arXiv:1610.08421

Indistinguishable quantum walks on graphs relative to a bipartite quantum walker

Phillip R. Dukes

Published Oct 26, 2016• 0 citations

arXiv HTML PDF

Abstract

A distinguishability operator is defined for the continuous-time quantum walk (CTQW) of a bipartite quantum walker on two simply connected graphs,

W_{G_i,G_j} = U_{G_i}\left(t\right) \otimes U_{G_j}\left(t'\right) - U_{G_j}\left(t'\right) \otimes U_{G_i}\left(t\right)

, where

U_{G_i}\left(t\right)

is the unitary CTQW operator for a labeled graph

G_i

over a time interval

t

. The null space of

W_{G_i,G_j}

defines the vector space of initial bipartite states whose time development is either constant or only dependent on

t + t'

and is invariant to which quantum walker subsystem goes with each graph. The set of null spaces corresponding with a set of

W_{G_i,G_j}

have interesting relations as subspaces, intersections between subspaces, and subspaces of intersections. These relations are depicted as Euler diagrams for labeled graphs of three and four vertices.

DOI: 10.48550/arxiv.1610.08421

Related papers

Continuous-time quantum walks over connected graphs, amplitudes and invariants

Phillip Dukes

We examine the time dependent amplitude $ ϕ_{j}\left( t\right)$ at each vertex $j$ of a continuous-time quantum walk on the cycle $C_{n}$ . In many cases the Lissajous curve of the real vs. imaginary parts of each $ ϕ_{j}\left( t\right)$ reveals interesting shapes of the space of time-accessible amplitudes. We find two invariants of continuous-time quantum walks. First, considering the rate at which each amplitude evolves in time we find the quantity $T = \displaystyle\sum_{j=0}^{n-1} \lvert\dfrac{d ϕ_{j}\left( t\right)}{d t}\rvert^{2}$ is time invariant. The value of $T$ for any initial state can be minimized with respect to a global phase factor $e^{i θt}$ to some value $T_{min}$ . An operator for $T_{min}$ is defined. For any simply connected graph $g$ the highest possible value of $T_{min}$ with respect to the initial state is found to be $T_{min}^{max}=\left( \frac{λ_{max}}{2}\right)^{2}$ where $λ_{max}$ is the maximum eigenvalue in the Laplace spectrum of $g$ . A second invariant is found in the time-dependent probability distribution $P_{j}\left(t\right) = \lvertϕ_{j}\left(t\right)\rvert^{2}$ of any initial state satisfying $T_{min}^{max}$ , with these conditions $\displaystyle\sum_{j=0}^{n-1}\left(P_{j}^{max} - P_{j}^{min}\right)^{2} = \dfrac{4}{n}$ for all simply connected graphs of $n$ vertices.We examine the time dependent amplitude $ ϕ_{j}\left( t\right)$ at each vertex $j$ of a continuous-time quantum walk on the cycle $C_{n}$. In many cases the Lissajous curve of the real vs. imaginary parts of each $ ϕ_{j}\left( t\right)$ reveals interesting shapes of the space of time-accessible amplitudes. We find two invariants of continuous-time quantum walks. First, considering the rate at which each amplitude evolves in time we find the quantity $T = \displaystyle\sum_{j=0}^{n-1} \lvert\dfrac{d ϕ_{j}\left( t\right)}{d t}\rvert^{2}$ is time invariant. The value of $T$ for any initial state can be minimized with respect to a global phase factor $e^{i θt}$ to some value $T_{min}$. An operator for $T_{min}$ is defined. For any simply connected graph $g$ the highest possible value of $T_{min}$ with respect to the initial state is found to be $T_{min}^{max}=\left( \frac{λ_{max}}{2}\right)^{2}$ where $λ_{max}$ is the maximum eigenvalue in the Laplace spectrum of $g$. A second invariant is found in the time-dependent probability distribution $P_{j}\left(t\right) = \lvertϕ_{j}\left(t\right)\rvert^{2}$ of any initial state satisfying $T_{min}^{max}$, with these conditions $\displaystyle\sum_{j=0}^{n-1}\left(P_{j}^{max} - P_{j}^{min}\right)^{2} = \dfrac{4}{n}$ for all simply connected graphs of $n$ vertices.

arXiv:1506.03086Jun 9, 20150 citations

Quantum walk on a chimera graph

Shu Xu, Xiangxiang Sun, Jizhou Wu +3 more

We analyse a continuous-time quantum walk on a chimera graph, which is a graph of choice for designing quantum annealers, and we discover beautiful quantum walk features such as localization that starkly distinguishes classical from quantum behaviour. Motivated by technological thrusts, we study continuous-time quantum walk on enhanced variants of the chimera graph and on diminished chimera graph with a random removal of vertices. We explain the quantum walk by constructing a generating set for a suitable subgroup of graph isomorphisms and corresponding symmetry operators that commute with the quantum walk Hamiltonian; the Hamiltonian and these symmetry operators provide a complete set of labels for the spectrum and the stationary states. Our quantum walk characterization of the chimera graph and its variants yields valuable insights into graphs used for designing quantum-annealers.We analyse a continuous-time quantum walk on a chimera graph, which is a graph of choice for designing quantum annealers, and we discover beautiful quantum walk features such as localization that starkly distinguishes classical from quantum behaviour. Motivated by technological thrusts, we study continuous-time quantum walk on enhanced variants of the chimera graph and on diminished chimera graph with a random removal of vertices. We explain the quantum walk by constructing a generating set for a suitable subgroup of graph isomorphisms and corresponding symmetry operators that commute with the quantum walk Hamiltonian; the Hamiltonian and these symmetry operators provide a complete set of labels for the spectrum and the stationary states. Our quantum walk characterization of the chimera graph and its variants yields valuable insights into graphs used for designing quantum-annealers.

arXiv:1705.11036New Journal of PhysicsMar 15, 20185 citations

Implementation of a continuous-time quantum walk on a sparse graph

Zhaoyang Chen, Guanzhong Li, Lvzhou Li

Continuous-time quantum walks (CTQWs) play a crucial role in quantum computing, especially for designing quantum algorithms. However, how to efficiently implement CTQWs is a challenging issue. In this paper, we study the implementation of CTQWs on sparse graphs, i.e., constructing efficient quantum circuits for implementing the unitary operator ${e}^{\ensuremath{-}iHt}$, where $H=\ensuremath{\gamma}A$ ($\ensuremath{\gamma}$ is a constant and $A$ corresponds to the adjacency matrix of a graph). Our result is, for a $d$ -sparse graph with $N$ vertices and evolution time $t$ , we can approximate ${e}^{\ensuremath{-}iHt}$ by a quantum circuit with gate complexity $({d}^{3}\ensuremath{\parallel}H\ensuremath{\parallel}tN{log}_{2}{(N))}^{1+o(1)}$, compared to the general Pauli decomposition, which scales like $(\ensuremath{\parallel}H\ensuremath{\parallel}t{N}^{4}{log}_{2}{(N))}^{1+o(1)}$. For sparse graphs, for instance, $d=O(1)$ , we obtain a noticeable improvement. Interestingly, our technique is related to graph decomposition. More specifically, we decompose the graph into a union of star graphs, and correspondingly, the Hamiltonian $H$ can be represented as the sum of some Hamiltonians ${H}_{j}$ , where each ${e}^{\ensuremath{-}i{H}_{j}t}$ is a CTQW on a star graph which can be implemented efficiently.Continuous-time quantum walks (CTQWs) play a crucial role in quantum computing, especially for designing quantum algorithms. However, how to efficiently implement CTQWs is a challenging issue. In this paper, we study the implementation of CTQWs on sparse graphs, i.e., constructing efficient quantum circuits for implementing the unitary operator ${e}^{\ensuremath{-}iHt}$, where $H=\ensuremath{\gamma}A$ ($\ensuremath{\gamma}$ is a constant and $A$ corresponds to the adjacency matrix of a graph). Our result is, for a $d$-sparse graph with $N$ vertices and evolution time $t$, we can approximate ${e}^{\ensuremath{-}iHt}$ by a quantum circuit with gate complexity $({d}^{3}\ensuremath{\parallel}H\ensuremath{\parallel}tN{log}_{2}{(N))}^{1+o(1)}$, compared to the general Pauli decomposition, which scales like $(\ensuremath{\parallel}H\ensuremath{\parallel}t{N}^{4}{log}_{2}{(N))}^{1+o(1)}$. For sparse graphs, for instance, $d=O(1)$, we obtain a noticeable improvement. Interestingly, our technique is related to graph decomposition. More specifically, we decompose the graph into a union of star graphs, and correspondingly, the Hamiltonian $H$ can be represented as the sum of some Hamiltonians ${H}_{j}$, where each ${e}^{\ensuremath{-}i{H}_{j}t}$ is a CTQW on a star graph which can be implemented efficiently.

arXiv:2408.10553Physical Review ANov 15, 20246 citations

A Continuous - Time Quantum Walk for Attributed GraphsMatching

Tewabe Chekole Workneh

Diverse facets Of the Theory of Quantum Walks on Graph are reviewed Till now .In specific, Quantum network routing, Quantum Walk Search Algorithm, Element distinctness associated to the eigenvalues of Graphs and the use of these relation /connection in the study of Quantum walks is furthermore described. Different Researchers had contribution and put their benchmark idea Pertaining with this research concept. I furthermore try to investigate recent Application of Quantum walks, In specific the problem pertained with Graph matching i.e Matching nodes(vertices) of the Graphs. In this research paper,I consider how Continuous-time quantum walk (CTQW) can be directed to Graph-matching problems. The matching problem is abstracted using weighted(attributed) Graphs that connects vertices's of one Graph to other and Try to compute the distance b/n those Graphs Node's Beside that finding the matched nodes and the Cost related to Matching. eventually measuring the distance between two Graphs which might have different size then by using k-nearest neighbor (k-NN) method try to classifying those graph based on closest training examples in the feature space.Diverse facets Of the Theory of Quantum Walks on Graph are reviewed Till now .In specific, Quantum network routing, Quantum Walk Search Algorithm, Element distinctness associated to the eigenvalues of Graphs and the use of these relation /connection in the study of Quantum walks is furthermore described. Different Researchers had contribution and put their benchmark idea Pertaining with this research concept. I furthermore try to investigate recent Application of Quantum walks, In specific the problem pertained with Graph matching i.e Matching nodes(vertices) of the Graphs. In this research paper,I consider how Continuous-time quantum walk (CTQW) can be directed to Graph-matching problems. The matching problem is abstracted using weighted(attributed) Graphs that connects vertices's of one Graph to other and Try to compute the distance b/n those Graphs Node's Beside that finding the matched nodes and the Cost related to Matching. eventually measuring the distance between two Graphs which might have different size then by using k-nearest neighbor (k-NN) method try to classifying those graph based on closest training examples in the feature space.

Oct 30, 20130 citations

Continuous-time quantum walk of two interacting fermions on a cycle graph

Alexey A. Melnikov, Leonid Evgenevich Fedichkin

We study a continuous-time quantum walk of interacting fermions on a cycle graph. By finding analytical solutions and simulating the dynamics of two fermions we observe a diverse structure of entangled states of indistinguishable fermions. The relation between entanglement of distinguishable qutrits and indistinguishable electrons is observed. Restrictions imposed by the symmetry of a cycle graph are derived. Possible realization of a quantum walk in an array of semiconductor quantum dots is discussed.We study a continuous-time quantum walk of interacting fermions on a cycle graph. By finding analytical solutions and simulating the dynamics of two fermions we observe a diverse structure of entangled states of indistinguishable fermions. The relation between entanglement of distinguishable qutrits and indistinguishable electrons is observed. Restrictions imposed by the symmetry of a cycle graph are derived. Possible realization of a quantum walk in an array of semiconductor quantum dots is discussed.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIEDec 30, 20168 citations

A Continuous - Time Quantum Walk for Attributed Graphs Matching

Tewabe Chekole

arXiv:1801.10339Jan 31, 20180 citations

A distinguishability operator is defined for the continuous-time quantum walk (CTQW) of a bipartite quantum walker on two simply connected graphs,

W_{G_i,G_j} = U_{G_i}\left(t\right) \otimes U_{G_j}\left(t'\right) - U_{G_j}\left(t'\right) \otimes U_{G_i}\left(t\right)

, where

U_{G_i}\left(t\right)

is the unitary CTQW operator for a labeled graph

G_i

over a time interval

t

. The null space of

W_{G_i,G_j}

defines the vector space of initial bipartite states whose time development is either constant or only dependent on

t + t'

and is invariant to which quantum walker subsystem goes with each graph. The set of null spaces corresponding with a set of

W_{G_i,G_j}

have interesting relations as subspaces, intersections between subspaces, and subspaces of intersections. These relations are depicted as Euler diagrams for labeled graphs of three and four vertices.

We examine the time dependent amplitude $ ϕ_{j}\left( t\right)$ at each vertex

j

of a continuous-time quantum walk on the cycle

C_{n}

. In many cases the Lissajous curve of the real vs. imaginary parts of each $ ϕ_{j}\left( t\right)$ reveals interesting shapes of the space of time-accessible amplitudes. We find two invariants of continuous-time quantum walks. First, considering the rate at which each amplitude evolves in time we find the quantity

T = \displaystyle\sum_{j=0}^{n-1} \lvert\dfrac{d ϕ_{j}\left( t\right)}{d t}\rvert^{2}

is time invariant. The value of

T

for any initial state can be minimized with respect to a global phase factor

e^{i θt}

to some value

T_{min}

. An operator for

T_{min}

is defined. For any simply connected graph

g

the highest possible value of

T_{min}

with respect to the initial state is found to be

T_{min}^{max}=\left( \frac{λ_{max}}{2}\right)^{2}

where

λ_{max}

is the maximum eigenvalue in the Laplace spectrum of

g

. A second invariant is found in the time-dependent probability distribution

P_{j}\left(t\right) = \lvertϕ_{j}\left(t\right)\rvert^{2}

of any initial state satisfying

T_{min}^{max}

, with these conditions

\displaystyle\sum_{j=0}^{n-1}\left(P_{j}^{max} - P_{j}^{min}\right)^{2} = \dfrac{4}{n}

for all simply connected graphs of

n

vertices.

A

corresponds to the adjacency matrix of a graph). Our result is, for a

d

-sparse graph with

N

vertices and evolution time

t

, we can approximate ${e}^{\ensuremath{-}iHt}$ by a quantum circuit with gate complexity $({d}^{3}\ensuremath{\parallel}H\ensuremath{\parallel}tN{log}_{2}{(N))}^{1+o(1)}$, compared to the general Pauli decomposition, which scales like $(\ensuremath{\parallel}H\ensuremath{\parallel}t{N}^{4}{log}_{2}{(N))}^{1+o(1)}$. For sparse graphs, for instance,

d=O(1)

, we obtain a noticeable improvement. Interestingly, our technique is related to graph decomposition. More specifically, we decompose the graph into a union of star graphs, and correspondingly, the Hamiltonian

H

can be represented as the sum of some Hamiltonians

{H}_{j}

, where each ${e}^{\ensuremath{-}i{H}_{j}t}$ is a CTQW on a star graph which can be implemented efficiently.