![The Time Machine Factory [unspeakable, speakable] on Time Travel -TM2019](/event/2767/logo-693158660.png){kind=logo}
Speaker
Description
One says that there is a quantum computational speedup when the computation of the solution of a problem is more efficient quantumly than classically. Let us consider, as an example, the simplest case that Bob, the problem setter, hides a ball in a chest of four drawers. Alice, the problem solver, is to locate in by opening drawers (by querying the oracle: is the ball in that drawer?). While in the classical case Alice may need to open up to three drawers, with the quantum algorithm devised by Grover she only needs to open one.
The usual representation of quantum algorithms is limited to the computation of the solution of the problem. We extend it to the process of setting the problem. Bob, who operates on the quantum register B, randomly selects the problem-setting (the number of the drawer with the ball) by an initial measurement in a (possibly incoherent) superposition of all the possible problem-settings. He could then unitarily change it into a desired setting but for simplicity we omit this operation. Alice, who operates on the quantum register A initially in an arbitrary sharp state (standing for a blank blackboard), unitarily computes the corresponding solution and reads it by the final measurement. With probability one of reading the solution, the process between the initial and final measurement outcomes is reversible – no information is destroyed along it.
We physically represent the fact that the problem-setting selected by Bob must be hidden from Alice (it would tell her the solution of the problem) by relativizing the extended representation to her. In the representation with respect to Alice, the projection of the quantum state associated with the initial measurement is postponed till the end of the unitary part of her problem-solving action. After the initial measurement, the quantum state of register B to Alice remains the quantum superposition of all the possible problem settings. It represents her complete ignorance of the problem setting selected by Bob. Alice unitarily changes the tensor product of this superposition and the sharp state of register A into a superposition of tensor products, each a problem setting in B multiplied by the corresponding solution in A. Then she selects the problem setting already selected by Bob by the final measurement of the solution.
We represent the reversibility of the process between the initial and final measurement outcomes by time-symmetrizing it. In this kind of process, and in the usual way of seeing, the information that specifies the initial measurement outcome and consequently the final one (in the present example, both the number of the drawer with the ball) is all selected by the initial measurement; its outcome (encoding the problem setting selected by Bob in register B) undergoes the time forward unitary transformation until becoming the state before the final measurement (encoding the solution in register A). The latter measurement just reads the solution encoded in A, without selecting anything. However, the thing could be seen in the time-symmetric way. The initial measurement does not select anything, the initial state superposition undergoes the unitary transformation that represents Alice’s problem solving action and the final measurement performs all the selection. The measurement outcome, which encodes the solution in register A, by the Parisian Zigzag propagates backwards in time by the inverse unitary transformation until becoming the outcome of the initial measurement, encoding the problem setting in register B.
However, either way of seeing, introducing a preferred direction of time, is not symmetric in time. According to the tenet of the Two-State-Vector Formalism, we assume that the initial and final measurements evenly contribute to determining the process in between, namely to selecting the information that specifies either measurement outcome. The half information selected by the initial measurement propagates forward in time, that selected by the final measurement backwards in time according to the Parisian Zigzag. Since there are many ways of halving the information, we should take all the corresponding time-symmetrization instances in quantum superposition.
This time-symmetrization procedure leaves the extended representation of the quantum algorithm, which is ordinary in character since no observer is shielded from any measurement outcome, unaltered.
It shows that the representation of the quantum algorithm relativized to Alice is a superposition of (partly overlapping) superpositions, the time-symmetrization instances, each a quantum algorithm by itself. In each instance, Alice remains shielded from the information coming to her from the initial measurement, not from that coming to her from the final measurement. The computational complexity of the problem to be solved by her is correspondingly reduced. All is as if she knew in advance, before performing the unitary part of her problem-solving action, half of the information that specifies the problem-setting and thus the solution of the problem and could use this information to reach the solution with fewer oracle queries. This accounts for the quantum computational speedup. The fact that the final measurement non-locally changes the state of register B to Alice at the beginning of the unitary part of the quantum algorithm, from a superposition of all the problem setting to that of a reduced part thereof, is of course a form of temporal nonlocality. It cannot be seen in the usual representation of quantum algorithm, which, by an application of the principle of locality, replaces the initial measurement by its measurement outcome.
The above accounts for the computational speedup of all the quantum algorithms examined. These comprise the major quantum algorithms and cover both the quadratic and exponential speedups. More generally, given an oracle problem, the number of oracle queries required to solve it in an optimal quantum way is that of a classical algorithm (a Turing machine) endowed with the advanced knowledge of half of the information that specifies the setting and the corresponding solution of the problem.
The fact that, in each time-symmetrization instance, Alice knows in advance half of the solution she will read in the future and uses this information to reach the solution with fewer oracle queries is a half causal loop. Its physical viability is discussed. The fact that there is apparently information going back in time from the final to the initial measurement is compensated for by the fact that one has to take the superposition of all the instances (apparent backward causality is compensated for by the indeterminacy inherent in the very notion of quantum superposition). This superposition – the quantum algorithm to Alice back again – is an ordinary quantum mechanical superposition, where apparently no information is sent back in time.
References
Ekert, A. K. and Jozsa, R.: Quantum Algorithms: Entanglement Enhanced Information Processing arXiv:quant-ph/9803072 (1998)
Dolev, S. and Elitzur, A. C.: Non-sequential behavior of the wave function. arXiv:quant-ph/0102109 v1 (2001)
Castagnoli, G. and Finkelstein, D. R.: Theory of the quantum speedup. Proc. Roy. Soc. A 1799, 457, 1799-1807 (2001)
Castagnoli, G.: The quantum correlation between the selection of the problem and that of the solution sheds light on the mechanism of the quantum speed up. Phys. Rev. A 82, 052334-052342 (2010)
Aharonov, Y., Cohen, E., and Elitzur, A. C.: Can a future choice affect a past measurement outcome? Ann. Phys. 355, 258-268 (2015)
Elitzur, A.C., Cohen, E., Okamoto, R. and Takeuchi, S.: Nonlocal position changes of a photon revealed by quantum routers. Sci. Rep. 8, 7730 (2018)
