Skip to main content
Share Your Experience: Take the 2024 Developer Survey
8 votes
Accepted

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 ...
Craig Gidney's user avatar
  • 37.6k
7 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 $...
Mark Spinelli's user avatar
7 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 ...
user1271772 No more free time's user avatar
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 ...
Sam Jaques's user avatar
  • 2,066
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 ...
DaftWullie's user avatar
  • 58.7k
4 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 ...
Mark Spinelli's user avatar
4 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 ...
Mark Spinelli's user avatar
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 ...
KAJ226's user avatar
  • 13.9k
3 votes
Accepted

Defining a discrete quantum walk on a 3D hypercube

I can't answer your cirq-specific question, but your general approach is on the right path. For example, beginning on the first column of page 7 of Kempe's article on quantum walks, to walk along a $...
Mark Spinelli's user avatar
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 ...
Medulla Oblongata's user avatar
3 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 ...
Platypus26's user avatar
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 ...
Thomas Mullor's user avatar
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's user avatar
  • 25.4k
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 ...
epelaez's user avatar
  • 2,895
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 ...
DaftWullie's user avatar
  • 58.7k
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 ...
Sideshow Bob's user avatar
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$.
Rammus's user avatar
  • 5,853
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.
bhq's user avatar
  • 238
2 votes

Quantum circuit implementation of shift operator in quantum walk

Once you have some operator form, one method is just to start multiplying it by unitary operators (pre- or post- or both, doesn't matter) until you can make it into identity. For example, maybe you ...
DaftWullie's user avatar
  • 58.7k
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'...
Mark Spinelli's user avatar
2 votes

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

A quantum walk can actually be defined in any graph. For each defined graph, it is only true that the operator must be local (considering the graph edges) and unitary. So we must consider the Grover's ...
Pedro's user avatar
  • 21
2 votes
Accepted

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

According to the definition you gave, $$ W=\left(\begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & 1/\sqrt{2} & 1/\sqrt{2} & 0 \\ 0 & 1/\sqrt{2} & -1/\sqrt{2} & 0 \\ 0 & ...
DaftWullie's user avatar
  • 58.7k
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, ...
rhundt's user avatar
  • 1,018
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, ...
Mark Spinelli's user avatar
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 ...
KAJ226's user avatar
  • 13.9k
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's user avatar
  • 25.4k
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 ...
DaftWullie's user avatar
  • 58.7k
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's user avatar
  • 25.4k
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. ...
Gokul Alex's user avatar
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.), ...
Mark Spinelli's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible