Questions tagged [quantum-walks]

Quantum walks are the quantum mechanical counterpart of classical random walks. This tag should be used for any question related to quantum walk models.

Filter by
Sorted by
Tagged with
2 votes
1 answer
83 views

Quantum circuit implementation of shift operator in quantum walk

I'm considering discrete-time quantum walk on $2\times2$ grid with periodic quantum walk. In particular focus on shift operator which has the form : \begin{equation} S|i,j\rangle \otimes |x,y\...
Young Kindaichi's user avatar
0 votes
0 answers
22 views

Why is the *Absorbing* Quantum Walk (of Belov/ Montanaro) possible?

[Belovs] and [Montanaro1] define quantum walk search in the electric network framework, that share common property: A single step of the quantum walk is defined, such that its the identity on marked ...
Fleeep's user avatar
  • 374
0 votes
0 answers
28 views

Can I simulate a quantum walk in fourier space?

I would like to simulate a simple quantum walk in Fourier space in Python. I am hoping just to run a 1D quantum walk with a simple Hadamard coin in Fourier space. Is this possible? Do I just need to ...
Saz's user avatar
  • 1
2 votes
0 answers
65 views

Why is discrete time quantum walks applicable only for undirected graphs?

I don't understand how this property of discrete-time quantum walk relates to the property that the transition operator SC is unitary. Many papers mention this and continue without explaining. Suppose ...
Adithya Bharath's user avatar
3 votes
1 answer
267 views

Defining a discrete quantum walk on a 3D hypercube

I am trying to implement at a discrete-time quantum walk on a 3D hypercube using cirq. I have three qubits for the position register: the $|x\rangle$ qubit, $|y\rangle$ qubit and $|z\rangle$ qubit, ...
Q.Ask's user avatar
  • 195
6 votes
1 answer
165 views

Why is Grover's Algorithm considered to be a Quantum Walk?

I have heard it said that Grover's algorithm is (can be modeled as?) a Quantum Walk. In fact, one reason for their popularity is that QW are used in certain Quantum algorithms. I am trying to ...
Andreas132's user avatar
4 votes
0 answers
147 views

How does edge-coloring help for quantum walks?

Reviewing Childs, Cleve, Deotto, Farhi, Gutmann, and Spielman's famous 2002 welded-trees problem, a quantum Theseus can find his way out of a labyrinth having an exponential number of rooms (vertices),...
Mark Spinelli's user avatar
2 votes
1 answer
74 views

What are the entries in the 2x2 $W$ gate used for walking along the welded-trees graph of Childs et al.?

As an extension of a famous description of non-local Hamiltonian simulation in section 4.7.3 of Nielsen and Chuang, the welded-trees paper of Childs, et al. provides the following circuit for use in ...
Mark Spinelli's user avatar
0 votes
0 answers
44 views

How to represent 2 Hadamard gates with Universal set of gates?

I was reading through Child's Paper on Universal Computation by Quantum Walks: https://arxiv.org/abs/0806.1972 When he discusses how his universal set of gates contains CNOT and the following 2 "...
Albi Domi's user avatar
0 votes
1 answer
57 views

Circuit to find elements in set which matches condition

I have a set S=[1,2,3,4] from which I need to find out two subsets which has the same sum. For example S0=[1,4] and S1=[2,3]. Assume that we've a solution. One approach is to encode all states in the ...
Van Peer's user avatar
  • 557
0 votes
1 answer
74 views

finding subsets which meets conditions

I have a set S = {a, b, c, d, e, f} from which I need to find out if there exists two subsets S0 and ...
Van Peer's user avatar
  • 557
7 votes
2 answers
170 views

Why can quantum walks not approach a stationary distribution

In Child's notes on quantum walks, he claims (section 16.6) "Since a quantum walk is a unitary process, we should not expect it to approach a limiting quantum state, no matter how long we wait.&...
SescoMath's user avatar
  • 507
3 votes
1 answer
143 views

Why is the triangle finding problem important?

I keep seeing in the literature that the triangle problem can be solved using the quantum walk algorithm. There is plenty of mathematical detail (eg. Magniez et al.'s paper), but I don't get why it's ...
Medulla Oblongata's user avatar
1 vote
0 answers
54 views

Why does the quantum walk operator only have two eigenvectors?

In Child's paper on the relationship between discrete and continuous quantum walks, he makes the following claim. Although he provides a proof after this: I don't understand how the walk operator ...
Loic Stoic's user avatar
3 votes
1 answer
176 views

How do we compute quantum walks for a graph?

I am reading Childs' paper on discrete and continuous quantum walks. I do not really understand why quantum walks are useful--- as implementing the quantum walk operator requires knowing the principal ...
Loic Stoic's user avatar
2 votes
1 answer
177 views

Confusion about quantum walks and the quantum walk operator

I am looking at the Quantum Signal Processing paper by GH Low and IL Chuang here. One step that they used was Child's quantum walks. They constructed a walk operator, $W \left | u_\lambda \right > =...
Loic Stoic's user avatar
2 votes
1 answer
210 views

continuous time quantum walk on a cycle - transition matrix

I am trying to find the transition matrix for a quantum walk on a cycle. The vertices are labelled $\lbrace 0,1,2,\ldots,n-1\rbrace$, where vertex $i$ is a neighbour of vertex $i \pm 1$. Lets say we ...
Root's user avatar
  • 479
2 votes
0 answers
60 views

What are the differences between discrete-time quantum walks between dimensions?

When working with quantum walks in other dimensions (1D – 2D – 3D...) do your results tend to be different from what is proposed in theory with the probability density? The results obtained in the ...
Ikky R's user avatar
  • 79
1 vote
0 answers
35 views

quantum coin walk on a regular 3D grid graph

I am trying to apply the quantum coin walk on a 3D grid, with 3 Hadamard coins. So there would be 6 different directions at each steps and there is 8 possible coin outcomes. I can't seem to get ...
Trieu Jo's user avatar
4 votes
0 answers
59 views

Angular spectral gap in Szegedy's quantum walk

I'm trying to understand how the Szegedy quantum walk operator is useful. I understand that given a reducible ergodic Markov chain with transition matrix $P\in\mathbb{R}^{2^n\times 2^n}$, implemented ...
zjs's user avatar
  • 161
1 vote
1 answer
264 views

Implementing Quantum Walks at IBM

a question about quantum walks, would this circuit be correct to start a quantum walk in a hypercube? I saw something about increment and decrement, but I didn't quite understand how they would work ...
Ikky R's user avatar
  • 79
3 votes
0 answers
129 views

How to simulate a quantum walk with decoherence?

I'm trying to reproduce quantum walk with decoherence as shown in figure 3 in V. M. Kendon, Phil. Trans. R. Soc. A, 364, 2006 (quant-ph/0609035). I am able to reproduce quantum walk without ...
TurbPhys's user avatar
2 votes
2 answers
348 views

How does a Hadamard discrete-time quantum walk result in a skewed distribution?

I was reading this tutorial about discrete random walk and got confused by the following paragraph. After the succession of Hadamard applications ($H$), I wonder how do we get skewed distribution. I ...
John Parker's user avatar
  • 1,061
6 votes
1 answer
262 views

What is meant by "perfect state transfer"?

In discussions on many quantum algorithms especially related to quantum walks, I have seen the term "perfect state transfer" used to describe some property apparently related to the ...
Mark Spinelli's user avatar
3 votes
1 answer
126 views

Relationship of Adiabatic Quantum Computing speedup to Quantum Random Walk hit time

Considering the following two phenomena: Adiabatic quantum computing in general exhibits a quadratic speedup over classical simulated annealing, though for some Hamiltonians it may be faster (while ...
Sideshow Bob's user avatar
6 votes
1 answer
205 views

How to prove that a naive quantum random walk is non-unitary

A 2000 paper by Nayak and Vishwanath provides an analysis of the dynamics of quantum random walks. In this paper, they mention a "naive" approach to defining a walk. I include the quote as ...
Shadow43375's user avatar
4 votes
0 answers
55 views

Is it possible to nest quantum Markov chain Monte Carlo, mean and minimum algorithms?

Montanaro A. 2015 Quantum speedup of Monte Carlo methods makes the following claim of an algorithm to estimate the mean output $\mu$ of an arbitrary algorithm A, with near-quadratic speedup over ...
Sideshow Bob's user avatar
0 votes
1 answer
150 views

What is this equation for coin operator is trying to do in this quantum walk for Non-regular graph? This coin operator is called Fourier coin

I am reading the following paper: Discrete-time quantum walk on complex networks for community detection by Kanae Mukai We define the Coin operator $C$ by: $C=C_1\otimes C_2....C_n$ , We define coin ...
Binshumesh sachan's user avatar
0 votes
0 answers
35 views

How to make a Node dependent coin operator?

In a non-regular graph the degree of each node is different. So, the dimension of the coin operator also needs to be changed (as the number of options the walker has to hop to adjacent nodes will be ...
Binshumesh sachan's user avatar
1 vote
0 answers
90 views

How to encode $|i \rightarrow j \rangle$ using binary string?

We define the quantum state on a complex network in the form, $$\mid\psi(t)\rangle=\sum_{i=1}^{N}\sum_{j=1}^{k_i}\psi_{i,j}(t)\lvert i\to j\rangle, $$ where $N$ is the total number of nodes, the ...
Binshumesh sachan's user avatar
-1 votes
1 answer
115 views

Use of Position Hilbert Space in Quantum Walk

To perform quantum walk first we need to define combine hilbert space for the position and coin, which is represented by: $H=H_p\bigotimes H_c$ Now, my question is what is the use of above ...
Binshumesh sachan's user avatar
2 votes
3 answers
151 views

Why, in a discrete-time quantum walk,we first apply the tensor product of the coin operation with the identity?

When we apply coin step in the quantum walk, for example considering the H gate, we first do it's tensor product with Identity vector of the position Hilbert space. Why is this so? Please see below ...
Binshumesh sachan's user avatar
1 vote
1 answer
99 views

What does the notation $|\psi(0)\rangle = |0\rangle|n=0\rangle$ mean?

Let us take the initial state with the particle located at the origin $|n=0\rangle$ and the coin state with spin up $|0\rangle$. So, $$ |\psi(0)\rangle = |0\rangle|n=0\rangle, $$ where $|\psi(0)\...
Binshumesh sachan's user avatar
2 votes
1 answer
117 views

Quantum Walk Study Resource for Non-regular Graph

Does anyone know any good resource where I can study about how quantum walk is performed on non-regular graph? Most of the papers I read, talks about only quantum walk on regular graphs containing ...
Binshumesh sachan's user avatar
4 votes
0 answers
69 views

Quantum walk for quantum simulated annealing in arXiv: 1512.03806

I'm studying quantum walk and quantum simulated annealing. While reading the paper Quantum algorithms for simulated annealing, I feel a little confused about the quantum walk they gave in Sec 2.1 ...
raycosine's user avatar
  • 860
4 votes
1 answer
483 views

Quantum circuit for Szegedy quantum walk on a cyclic graph

I'm trying to implement an efficient circuit for the Szegedy quantum walk on a cyclic graph with number of nodes N = 8. I found the circuit in this thesis (page 39), the two images below show graph ...
Rik's user avatar
  • 43
6 votes
0 answers
102 views

Speedup for spatial search problem using quantum walks

Given a graph $G$ and a set of marked vertices $M$, spatial search problem is the problem of finding a marked vertex. A classical approach is to perform a random walk on the graph to find out a marked ...
usercs's user avatar
  • 461
10 votes
1 answer
652 views

Oracle for welded tree walk

There is a famous paper by Childs, et al, in which it is shown that a quantum algorithm can find the name of the exit node for a certain graph in a way that is exponentially faster than any classical ...
James Wootton's user avatar
3 votes
0 answers
232 views

What can be some bachelor thesis ideas in quantum random walks? [closed]

Note: Cross-posted on Theoretical Computer Science Stack Exchange. I am an undergraduate, reading about quantum information and quantum technology. For about some time, I have been interested in the ...
Nimish Mishra's user avatar
11 votes
1 answer
908 views

Quantum Algorithm for God's Number

God's number is the worst case of God's algorithm which is a notion originating in discussions of ways to solve the Rubik's Cube puzzle, but which can also be applied to other combinatorial puzzles ...
user820789's user avatar
  • 3,302
11 votes
1 answer
537 views

Quantum walk with binary tree

I’m trying to grok quantum walks, and would like to create an example that walks a perfect binary tree to find the one and only marked leaf node. Is this possible? If so, suppose the depth of the tree ...
JavaFXpert's user avatar
11 votes
1 answer
281 views

Quantum Walk: Why the need of adding "tail" nodes to the root?

As stated in the question, I have found in several papers (e.g. 1, 2) that in order to perform a quantum walk on a given tree it is necessary to add some nodes to the root $r$, say $r^{'}$ and $r^{"}$....
FSic's user avatar
  • 859
19 votes
2 answers
460 views

Quantum simulation of environment-assisted quantum walks in photosynthetic energy transfer

This question is related to Can the theory of quantum computation assist in the miniaturization of transistors? and Is Quantum Biocomputing ahead of us? About 10 years ago, several papers discussed ...
agaitaarino's user avatar
  • 3,807