In the paper Quantum Random Walks Hit Exponentially Faster (arXiv:quant-ph/0205083) Kempe gives a notion of hitting time for quantum walks (in the hypercube) that is not very popular in the quantum walk literature. It is defined as follows:

One-Shot Quantum Hitting Time: A discrete-time quantum walk has a $(T,p)$ one-shot $(|\Psi_0\rangle,|\Psi^f\rangle)$-hitting time if $|\langle\Psi^f|U^T|\Psi_0\rangle|^2 \geq p$ where $|\Psi_0\rangle$ is the initial state, $|\Psi^f\rangle$ is the target state, and $p>0$ is the hitting probability.

Normally you would like to know the minimum $T$ such that $p>0$. It is not possible (correct me if I'm wrong) to define a notion of average hitting time because you will need to make measurements during the walk, and that would collapse it to a classical walk. That's why we have the one-shot notion. In the same piece of work, there is an application to quantum routing (cf. section 5).

In order to know that the walk arrived at the target vertex, you need to make a measurement only at that node. For example, in the $n$-dimensional hypercube with $2^n$ nodes if you start at node $|\Psi_0\rangle=|00\dots00\rangle$ and have as target node $|\Psi^f\rangle=|11\dots11\rangle$, the paper shows that $T=O(n)$ with bounded error probability, i.e. $p\to 1$ as $n$ becomes very large. So in order to detect that the walk arrived at $|11\dots11\rangle$ you make a measurement after $\Omega(n)$ steps. This is an exponential speed-up.


  1. To use this notion of hitting time for search you need to know at least the distance of the target vertex from the origin, because that's how you know when to apply your measurement. Let's say that you have a graph $G$, and set as initial vertex $v_0$ and want to reach $v^f$. Assume also that $T=O(dist(v_0,v^f))$ and $p\geq 1/2$. Well, $T$ is obvious because you need at least that many steps to reach it. Does it make any sense using this hitting time for search? If you know where the node is there is no meaning in searching, but having a piece of information like "distance from the starting vertex" but not knowing exactly where the target is, does this notion of hitting time gives any interesting (worth to study) search algorithm?

  2. Does the application to quantum routing makes any sense? In the paper it says that it can be used for routing packages, but it seems to me that you can only send 1 bit, e.g. does it arrived at destination or not? Can you actually send a quantum state in this framework? In the paper this issue is not being addressed.

  3. This is maybe a silly question to ask, but here it goes. Can you use this notion of hitting time for constructing a "Generalized Mach-Zender Interferometer"?

I'm aware of the other notions of hitting times for quantum walks (like Szegedy's or Ambainis's). I'm particularly interested in this specific hitting time.

Update (9/24/2010): Thanks to Joe Fitzsimons questions 2 and 3 were completely answered. Although question number 1 still remains. First, I will restate question 2 in more specific terms now that I finished reading the paper that Joe recommended me and a couple more (for example see arXiv:0802.1224), and then I'll give a concrete example of what I have in mind for question 1.

2'. If you are sending a concrete message (like a sequence of classical bits), you can use a more complicated unitary that will copy this information during the steps of the walk. To send quantum states you need something more. The spin-chains channel uses a linear array of qubits with a fixed coupling. You can put the state (pure state, I don't know if it works for mixed states) you want to transmit in one end and it goes to the other end with high fidelity according to numerical results. I still have to give it more thought but I have two ideas: i) put a chain on each link of the graph, or ii) make the walk, find the target state, then make the channel between initial state and target and then send the state. Are any of these approaches plaussible? Does it work with mixed states?

1'. Consider a walk on a 2-dimensional grid centered in the origin with $n$ nodes with each side with length $\sqrt{n}$. Set the initial state at $v_0=(0,0)$ and the target state at $v^f=(\sqrt{n}-1,a)$ where $a=0,\dots,\sqrt{n}-1$. Because the walk is symmetric we have that the same hitting time and hitting probabilities hold for any target somewhere on the border of the grid as shown below.

alt text

Therefore the information we have is that $dist(v_0,v^f)=\Omega(\sqrt{n})$. We can use this to know when to make the measurement. Can the one-shot hitting time be used to search this grid? Here you need that information. An open problem in searching a grid is that we know that $\Omega(\sqrt{n})$ is a lower bound for search, and for grids the best upper bound is $O(\sqrt{n\log n})$. Either we are not being able to find a better algorithm, or the techniques for proving lower bounds when you use them on grids are giving a weak lower bound. Can you show that the only way to go below $\sqrt{n\log n}$ is having "a piece of information" as the one in the question? This would imply a way of proving a lower bound for grids. Does it make any sense?


2 Answers 2


I'm not so familiar with this paper, but I will try to give a rough answer to each of your questions after a cursory skim.

  1. Grover's algorithm can indeed viewed with this notion of hitting time. You need to decide when to measure the system, and even though T is constant for all results, it is still important to calculate. Here T is certainly not $O(\mbox{dist}(v_0, v^f))$ (which in this case is 1), but rather $O(\sqrt{n})$, so your assumption that $T=O(\mbox{dist}(v_0, v^f))$ is not valid here.
  2. I assume the author is taking an entire packet to do the random walk. Obviously this requires a somewhat more complicated unitary, but I don't really see an issue. Alternately, Burgarth and Bose have a very nice scheme for encoding information across identical graphs which would work too if you simply replace their 1d chains with the network of choice (quant-ph/0406112).
  3. Well, you don't quite need this notion of hitting time. Hypercubes have perfect state transfer (see for example quant-ph/0309131 and quant-ph/0411020), so you can view transport on a hypercube as an interferometer with the Mach-Zender interferometer corresponding to the 2d case.

UPDATE: (To answer the updated question regarding random walks on a grid or other lattice)

One approach to the measurement issue you highlight with the spatial search problem is to simply make a measurement at each timestep such that it returns 1 iff the the vertex the walker is currently at (say $v_t$) is equal to $v^f$ and the current timestep t is the hitting time for that vertex. This should avoid the issue of collapsing the wave function, as the measurement is only made for each vertex once the hitting time is reached, and it only registers collapses onto a location if that location is the correct result.

  • $\begingroup$ Joe, thanks for your answer. About 1, the problem with the measurement is that you need to know is how far is the target from your starting point in order to use it. E.g., for a d-dimensional grid with $n$ nodes, let's say that you start at the center and the target is somewhere on the border of the grid and we know that. So the distance from the center is $\Omega(n^{1/d})$, and that's also your hitting time if the hitting problability has bounded error. Can we asume that we can have that kind of knowledge? Because for Grover's, you are doing a complete blind search, and that's seems more real $\endgroup$ Sep 18, 2010 at 1:54
  • $\begingroup$ Sure, but you don't necessarily have to consider regular grids. Grover's algorithm would correspond to a central node directly connected to all other nodes so that the distance is always fixed. Additionally, there is another problem, in that the hitting time will not be defined for all nodes. In some cases the probability will simply never reach the threshold value. I could be mistaken, but I believe for a linear chain the maximum overlap at each site falls off as something like $\mid v_0 - v^f \mid^{-\frac{1}{2}}$ for XXZ coupled chains. $\endgroup$ Sep 18, 2010 at 20:33
  • $\begingroup$ The overlap decay depends highly on the coin operation of your walk. If you choose Grover's diffusion operator, when you hit the target node the overlap is high and some steps later it decreases as $O(t^{-1})$ for lines and grid graphs. $\endgroup$ Sep 19, 2010 at 0:50
  • $\begingroup$ Yes, exactly. The figure I gave is just for one specific system. I simply wanted to highlight that it is not always possible to achieve a constant hitting probability independent on the number of vertices. $\endgroup$ Sep 19, 2010 at 0:58
  • $\begingroup$ But coming back to the question on search, I gave the example on grids because I was thinking on "spatial search on grids" (quant-ph/0303041). But still, it seems to me that in order to do a measurement to see if you hit the target you need to do it on the subspace containing the target. As I imagine it, you need a device on that subspace constantly checking if the walk arrived or not. My problem is that it seems that you always need to know more or less where your target is. (continue) $\endgroup$ Sep 19, 2010 at 0:58

With regards to question 1, knowning the distance between the unknown target vertex and some known origin vertex on the hypercube can help the search process. However, the value of the distance itself determines how much helpful this information is.

Typical quantum walk algorithms are usually variations/approximations of Grover search: they involve an approximate rotation of the state vector in a 2-d subspace of the total Hilbert space.

You can use these algorithms to efficently prepare an approximately uniform superposition of all vertices at a given distance from the origin. Then you can search your target vertex inside this superposition using quantum or classical (Monte Carlo) search: For classical search just prepare the superposition and measure it in the vertex basis and repeat until you find the target. For quantum search, the superposition preparation procedure (and its inverse) becomes a subroutine that replaces the Hadamard transform in the Grover iteration.

The usefulness of this depends on the value of the distance: in the $n$-dimensional hypercube the number of vertices at distance $d$ from a given origin is the binomial coefficient $\binom{n}{d}$. Hence the majority of vertices ($\approx \frac{2^n}{\sqrt{\frac{\pi}{2}n}}$) are at $\approx n/2$ distance: while you can efficiently prepare the superposition of these vertices, searching the target inside it still takes exponential time.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.