Quantum walks are the quantum mechanical counterpart of classical random walks. This tag should be used for any question related to quantum walk models.
Questions tagged [quantum-walks]
49 questions
20
votes
2 answers
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 the environment-assisted quantum walks in…
agaitaarino
- 3,907
- 2
- 13
- 42
11
votes
1 answer
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 algorithm. This speedup assumes an oracle that…
James Wootton
- 11,700
- 1
- 35
- 74
11
votes
1 answer
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 and mathematical games. It refers to any algorithm…
user820789
- 3,440
- 13
- 43
11
votes
1 answer
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 is five. Would that require a circuit with five…
JavaFXpert
- 183
- 4
11
votes
1 answer
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^{"}$. Why are they needed?
References:
Farhi E.,…
FSic
- 889
- 6
- 18
7
votes
2 answers
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."
But why should this be true? I understand that quantum…
Sergio Escobar
- 811
- 4
- 9
7
votes
1 answer
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 periodicities of the walk/algorithm, but I cannot quite grasp the…
Mark Spinelli
- 15,378
- 3
- 26
- 83
7
votes
1 answer
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 follows:
In direct analogy, one may naively try to define…
Shadow43375
- 197
- 4
6
votes
0 answers
Can a half-classical, half-quantum rat settle on finding the cheese faster than a fully classical or fully quantum one?
TL/DR: With $t$ being the classical mixing time of an connected, non-bipartite, unweighted, undirected graph on $n$ vertices, and $\pi_n=\frac{1}{n}$ being the stationary probability at vertex $v_n$, what strategy, if any, is there to interpolating…
Mark Spinelli
- 15,378
- 3
- 26
- 83
6
votes
0 answers
What happens when we permute the vertices of a (small) graph by unitarily walking along a (larger) graph of the symmetric group?
Let $G$ be an unweighted, undirected graph on $n$ vertices with vertex labels $\{1,2,\cdots,n\}$; let $A$ be its $n\times n$ adjacency matrix. We can prepare a state $|\psi\rangle$ representing $A$ with $n^2$ qubits; for example, with $n=10$ we…
Mark Spinelli
- 15,378
- 3
- 26
- 83
6
votes
1 answer
Do the Towers of Hanoi admit any perfect state transfer?
The Towers of Hanoi is an old puzzle that involves moving $n$ discs of different radii among $k$ pegs, requiring each stack of discs to be monotonically increasing along the stack. Conventionally $n=6$ or so and $k=3$; it's also often studied in…
Mark Spinelli
- 15,378
- 3
- 26
- 83
6
votes
1 answer
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 understand the connection between this algorithm and a…
Andreas132
- 61
- 1
6
votes
1 answer
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 and circuit. I've already wrote the code using…
Rik
- 63
- 4
6
votes
0 answers
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 vertex, for which the required time is the…
usercs
- 481
- 2
- 9
4
votes
0 answers
Is first quantization ever useful to think about for perfect state transfer of a continuous-time quantum walk?
There are a couple of different models for using $n$ qubits to walk along a graph $G=(V,E)$.
For example, we could assign each of the $n$ qubits to each of the $v\in V$ vertices, and have each edge $e\in E$ be a partial SWAP therebetween. Starting…
Mark Spinelli
- 15,378
- 3
- 26
- 83