8
votes
Why can quantum walks not approach a stationary distribution
Suppose for contradiction that there is some limiting state $|f\rangle$ that an initial state $|s_1\rangle \neq |f\rangle$ approaches as a unitary operation $U$ is repeatedly applied. So there is ...
- 28.6k
6
votes
Accepted
Quantum simulation of environment-assisted quantum walks in photosynthetic energy transfer
One major idea there seems to be that the "environment" (quantum
decoherence) assists or optimizes the transport of a signal
The idea that photosynthetic systems are doing a Grover search or ...
- 12.7k
6
votes
Why can quantum walks not approach a stationary distribution
That's an interesting point and I suppose reversibility, interpreted as bijectivity, is not enough.
But unitarity implies a lot more. More specifically, unitary operators preserve distance. So we can ...
- 1,752
6
votes
Accepted
Quantum Algorithm for God's Number
We can think of the Rubik's cube Cayley graph $\Gamma=(V,E)$ with each (colored) edge $E$ being one of the Singmaster moves $\langle U,U^{2},U^{3}=U^{-1},D,D^{2},D^{3},\cdots\rangle$ and each vertex $...
- 8,906
6
votes
Accepted
How to prove that a naive quantum random walk is non-unitary
I'm going to define $|n\rangle$ to be "the walker is at site $n$". Now imagine the walk as specified:
$$
|n\rangle\rightarrow (|n-1\rangle+|n+1\rangle)/\sqrt{2}.
$$
You can put some phases ...
- 51k
4
votes
Accepted
Why, in a discrete-time quantum walk,we first apply the tensor product of the coin operation with the identity?
You started with the state $|\psi \rangle = |0\rangle \otimes |0\rangle $ which belongs to the space $\mathbb{C}^2 \otimes \mathbb{C}^2$. To operate state on this space, your operator must also have ...
- 13.1k
3
votes
Why is the triangle finding problem important?
According to Le Gall and Nakajima's paper Quantum Algorithm for Triangle Finding in Sparse Graphs,
Williams and Williams have shown a surprising reduction from Boolean matrix multiplication to ...
3
votes
Accepted
Confusion about quantum walks and the quantum walk operator
For these problems we're not usually given a matrix that is small enough that we can write down explicitly, as is done in the question. Rather, these oracles $O_H$ and $O_F$ are most useful to ...
- 8,906
2
votes
Accepted
What does the notation $|\psi(0)\rangle = |0\rangle|n=0\rangle$ mean?
This is common shorthand for the tensor product. That is, you should read it as $|0 \rangle \otimes | n=0\rangle$.
- 4,516
2
votes
Quantum Walk Study Resource for Non-regular Graph
Some important references could be the following: Quantum Walks On Graphs,
Quantum walks: a comprehensive review,
Quantum random walks - an introductory overview.
- 228
2
votes
Accepted
Quantum circuit for Szegedy quantum walk on a cyclic graph
It's been a long while since I've looked at my thesis, so a lot of my knowledge is pretty rusty, but here goes.
If you're looking for the circuit representation of $C_8$, here's the Quirk simulation ...
- 36
2
votes
Oracle for welded tree walk
I often wonder if the welded trees considered in the Childs et al. paper have any applicability to questions in algorithmic knot theory such as knot identification/knot canonization. For example, I ...
- 8,906
2
votes
Accepted
Implementing Quantum Walks at IBM
Let's explain what this circuit do :
A coin quantum walk is a process in which a walker will evolve through the differents vertices of a graph. Its steps will be guided by a coin, a quantum register ...
- 470
2
votes
Accepted
How does a Hadamard discrete-time quantum walk result in a skewed distribution?
You get a skewed distribution because you start with a "skewed" coin state (I'm assuming the system you are considering starts with the walker state in a single fixed state).
In fact, you ...
glS♦
- 21.2k
2
votes
How does a Hadamard discrete-time quantum walk result in a skewed distribution?
I did the math for the first three steps when the coin qubit is initialized to $|\uparrow\rangle$ using the link @Mark S commented. We use as the coin flip operator the Hadamard gate, and the ...
- 2,695
2
votes
Accepted
What is meant by "perfect state transfer"?
Perfect state transfer is generally discussed in the context of continuous time evolution. For example, you might be evolving under the influence of a Hamiltonian $H$. Particularly when one is ...
- 51k
2
votes
Relationship of Adiabatic Quantum Computing speedup to Quantum Random Walk hit time
In response to my own question, I'm thinking Aaronson stated somewhere (I can't find the reference) that the quadratic speedup of e.g. Grover search arises from the fact that probability is amplitude ...
- 387
2
votes
How do we compute quantum walks for a graph?
The graph is the Hamiltonian I think.
I'll start off by saying I only understand portions of Childs' paper and I am far from familiar with graph theory, much less spectral graph theory - much of what'...
- 8,906
1
vote
finding subsets which meets conditions
I've put an implementation here. The idea is to construct a Hamiltonian, which would be a diagonal matrix, and then use a variational algorithm to see whether there exists a state with eigenvalue 0, ...
- 823
1
vote
continuous time quantum walk on a cycle - transition matrix
(Not much of an answer yet, just some tentative ideas about how to simulate a continuous-time random walk on a cycle for now. I describe how to take a small quantum walk for a short amount of time, ...
- 8,906
1
vote
Quantum walk with binary tree
Quantum Walk may not perform in optimal ways over a conventional and determinisitc binary tree data structure. In a quantum walk experimental setup, the coin will not follow a binomial distribution. ...
- 867
1
vote
Quantum Walk: Why the need of adding "tail" nodes to the root?
Following up on and inspired by the comments from Rob, I sense that there's a bit of a similarity between, on the one hand, the boolean tree evaluation of Farhi and Gutmann (and of Ambainis et al.), ...
- 8,906
1
vote
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
The operator Fourier Coin is $k$-point Discrete Fourier Transform (DFT) of node $i$.
The matrix representation of a general $N$-point DFT can be found here.
The implementation of DFT on the quantum ...
- 13.1k
1
vote
Use of Position Hilbert Space in Quantum Walk
Now, my question is what is the use of above representation, if all the operation are defined on initial state.
This means very little. Like in any kind of dynamics, you start with an initial state ...
glS♦
- 21.2k
1
vote
Why, in a discrete-time quantum walk,we first apply the tensor product of the coin operation with the identity?
The idea is that by applying Hadamard just to the coin and doing nothing to the position state, this is the equivalent of tossing the coin.
To see this in a very crude way, imagine applying Hadamard ...
- 51k
1
vote
Why, in a discrete-time quantum walk,we first apply the tensor product of the coin operation with the identity?
A (discrete-time) quantum walk can be thought of as the direct "quantization" of a classical random walk.
In a classical random walk, at each iteration, you flip a coin and move the walker ...
glS♦
- 21.2k
Only top scored, non community-wiki answers of a minimum length are eligible