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.
Questions:
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?
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.
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.
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?
