Accounting for computation time in Counterfactual Computers

Question

After researching some stuff about Turing Machines and Automaton Theory I stumbled upon the concept of "counterfactual computers". Having little experience with quantum physics (and usually keeping out of it for exactly that reason) I tried doing my own research and - as one would expect - failed (The tensor products got me *wink).

The thing I was wandering is: After at least somewhat understand the Elitzur-Vaidman-Bomb-Experiment, there are supposed to be computers using this effect to produce computation results without ever being run.

At a first glance that seems as sensible as it possibly can; but after thinking about it for a while a slight issue came to mind: In most publications about that topic, it is stated that the computation begins on arrival of the photon (or any other particle) and is either emitted or not-emitted depending on the computation's result.

However, the part of the wave function propagating along the interferometer's other path goes to the detector directly and does not await the computation's solution. How is it possible then, for them to - even in a negative-result where "normal" intereference occurs - result to meet each other at the second beam splitter? The one side of the wave-function should have long passed? Or rather cannot have passed, because then not everything will have had a chance to reach the detector. So my current belief is that the wave-functions propagations is somehow delayed.

My first thought was along the lines of time-dialation, my second thoughts were something about the computation result being intrinsic to probability as well. Both seem far-fetched and the second explenation should at least break down if one introduces some fixed waiting time for the output of the result.

Needless to say, I am somewhat inexperienced in the subject and come from mostly an Information Theorey perspective, so please be kind to my mistakes. Greeting and have a good day.

Answer 1

Bowden's original presentation dealt with this by using a Mach-Zender interferometer and requiring the computation time to be a multiple of the inverse frequency of the light. Specifically, his "computation" was light navigating a maze, and the maze was made of square cells whose side length was the wavelength of the light, so regardless of the unknown length of the solution path, the escaping light would have a known phase. That means, though, that you have to wait for the worst-case computation time (maximum path length) before doing your measurements, so this trick doesn't save any time: in fact it costs time, both because you can't bail out early and because to have a good chance of a counterfactual outcome, you have to repeat it many times.

---

I think this extends to the general case: not doing the computation can't use less of any resource—such as time, or energy (work), or wear and tear on the components of the quantum computer—than doing it, so there is never any advantage to it.

The general setup is that you have a quantum circuit that computes the answer to some decision problem, and is equivalent to a CNOT gate if the answer is yes, or a no-op if the answer is no. You initialize the control bit to $|0\rangle$ and then repeatedly rotate it one $n$th of the way toward $|1\rangle$, do the decision-problem computation, then measure the output bit to see if it's flipped.

If the circuit is equivalent to a no-op, then the control and output bits are uncorrelated, so measuring the output bit does nothing, and after $n$ rotations the control bit is guaranteed to be $|1\rangle$.

If the circuit is equivalent to a CNOT, then measuring an unflipped output bit means the control bit was $0$ (you don't know that, but the universe does), so the system collapses back to its initial state, and after $n$ repetitions where you measure an unflipped output, the control bit's final measured value is its initial value of $0$, meaning the answer must be yes, but the computation never happened.

If you ever measure a flipped output bit, then the computation did happen (the "bomb explodes" case), but the chance of that can be made arbitrarily small by choosing $n$ large.

Note that if the answer is no, the computation must be exactly equivalent to a no-op: it must not use any more time, power, etc. if the control bit is $1$ than if it's $0$, since that would leak information, causing a collapse, and the final state of the control bit would be $|0\rangle$ with high probability.

If the answer is yes, there is no problem with the circuit using more resources when the control bit is $1$, since that only leaks information that we learn anyway when we measure the output bit. But to know that you can safely do that, you have to know that the answer is yes, which means you've already finished the whole computation and there is no longer anything to spend resources on.

So the counterfactual computation can't be made cheaper. In fact, it's more than $n$ times more expensive.

Answer 2

My answer is only going to focus on this part of your question, because I think this probably shows a deeper conceptual misunderstanding (that is very common based on the way quantum mechanics is normally portrayed at a popular and even early undergraduate level):

the part of the wave function propagating along the interferometer's other path goes to the detector directly and does not await the computation's solution.

I think this sentence reveals that your physical picture is that the photon is described by a wavefunction, and we can think of the interferometer as something that "watches" the photon's wavefunction (let me know in the comments if I am misguided here). A typical picture beginners have is that the wavefunction is like a wave -- it is a function of space, it has a value at every point in space.

In fact, the wavefunction is a function of all variables defining the state of the system. For the Elitzur-Vaidman bomb setup, this means that the wavefunction would not just depend on the photon's position, but also on the state of the bomb (exploded or not).

In the case where the bomb is a dud, this means that the whole wavefunction is a superposition: \begin{eqnarray} \Psi &=& \psi_1({\rm photon\ avoided\ bomb\ and\ bomb\ not\ exploded}) \\ && + \psi_2({\rm photon\ hit\ bomb\ and\ bomb\ not\ exploded}) \end{eqnarray} In other words, each of the two logical possibilities -- (1) the photon took a path avoiding the bomb and the bomb didn't explode, and (2) the photon took a path hitting the bomb and the bomb didn't explode -- are associated with a probability amplitude, which I've called $\psi_1$ and $\psi_2$. The crucial point -- that is often counterintuitive for beginners -- that $\psi_1$ and $\psi_2$ are not just functions of the photon's path/position, but also of the state of the bomb.

It may or may not help to think about the many worlds interpretation here -- I like to think of each logically consistent world getting a single probability amplitude; the wavefunction tells you what those probability amplitudes are for each logically possible world. But, regardless of interpretation, the mistake is to think of the wavefunction as being a "classical wave" that exists in space, and that interacts with the bomb in the way a water wave would.

In the case where the bomb is not a dud, the superposition is: \begin{eqnarray} \Phi &=& \phi_1({\rm photon\ avoided\ bomb\ and\ bomb\ not\ exploded})\\ && + \phi_2({\rm photon\ hit\ bomb\ and\ bomb\ exploded}) \end{eqnarray} Given that we detect a photon, the state collapses and becomes $\Phi=\phi_1$. (If the bomb explodes, the state collapses and becomes $\Phi=\phi_2$). Again, the key here is that $\psi_1$ and $\psi_2$ are not just functions of the photon's position, but also of the bomb's state.

Once you accept all of the above, the conclusion that you can (sometimes) detect the presence of a live bomb without it going off, is simply related to the fact that, after measuring a photon, $\psi_1+\psi_2=\Psi \neq \Phi = \phi_1$, so you can (by doing repeated measurements) distinguish these states.