# 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
Filter by
Sorted by
Tagged with
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),...
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 ...
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 "...
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 ...
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 ...
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.&...
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
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 ...
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 ...
1 vote
132 views

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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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^{"}$....