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.
37
questions
4
votes
0
answers
73
views
How does edge-coloring help for quantum walks?
Reviewing Childs, Cleve, Deotto, Farhi, Gutmann, and Spielman's famous 2002 welded-trees problem, (quantum) Theseus can find his way out of a labyrinth having an exponential number of rooms (vertices),...
- 9,346
2
votes
1
answer
42
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 ...
- 9,346
0
votes
0
answers
35
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 "...
0
votes
1
answer
35
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 ...
- 515
0
votes
1
answer
61
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 ...
- 515
7
votes
2
answers
144
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.&...
- 441
3
votes
1
answer
83
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 ...
1
vote
0
answers
41
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 ...
- 373
3
votes
1
answer
123
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 ...
- 373
1
vote
1
answer
132
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 > =...
- 373
2
votes
1
answer
179
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 ...
- 459
2
votes
0
answers
50
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 ...
- 79
1
vote
0
answers
23
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 ...
- 11
3
votes
0
answers
37
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 ...
- 151
1
vote
1
answer
170
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 ...
- 79
2
votes
0
answers
93
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 ...
- 63
2
votes
2
answers
253
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 ...
- 981
6
votes
1
answer
186
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 ...
- 9,346
3
votes
1
answer
106
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 ...
- 397
6
votes
1
answer
188
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 ...
- 163
3
votes
0
answers
52
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 ...
- 397
0
votes
1
answer
112
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 ...
0
votes
0
answers
33
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 ...
1
vote
0
answers
82
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 ...
-1
votes
1
answer
107
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 ...
2
votes
3
answers
131
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 ...
1
vote
1
answer
74
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)\...
2
votes
1
answer
102
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 ...
3
votes
0
answers
60
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 ...
- 830
3
votes
1
answer
365
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 ...
- 33
6
votes
0
answers
88
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 ...
- 451
8
votes
1
answer
306
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 ...
- 11k
3
votes
0
answers
213
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 ...
- 169
11
votes
1
answer
824
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 ...
- 3,272
11
votes
1
answer
479
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 ...
- 183
11
votes
1
answer
265
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^{"}$....
- 839
19
votes
2
answers
432
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 ...
- 3,747