Can Closed Timelike Curves or Nonlinear Quantum Mechanics Improve Quantum State Discrimination or Help Solve Hard Problems?

We study the power of closed timelike curves (CTCs) and other nonlinear extensions of quantum mechanics for distinguishing nonorthogonal states and speeding up hard computations. If a CTC-assisted computer is presented with a labeled mixture of states to be distinguished—the most natural formulation—we show that the CTC is of no use. The apparent contradiction with recent claims that CTC-assisted computers can perfectly distinguish nonorthogonal states is resolved by noting that CTC-assisted evolution is nonlinear, so the output of such a computer on a mixture of inputs is not a convex combination of its output on the mixture’s pure components. Similarly, it is not clear that CTC assistance or nonlinear evolution help solve hard problems if computation is defined as we recommend, as correctly evaluating a function on a labeled mixture of orthogonal inputs.

Figure 1

Sending half of an EPR pair along a CTC. (a) Single universe picture. An EPR pair, $|\Phi {⟩}_{AB}=\frac{1}{\sqrt{2}}(|0{⟩}_A|0{⟩}_B+|1{⟩}_A|1{⟩}_B)$, is created in the distant past. At time $t_0$, a qubit emerges from the CTC and at time $t_1$, half of the EPR pair is put into the CTC. According to Deutsch’s prescription, the density matrix of the CTC system at $t_0$ is equal to the CTC density matrix at $t_1$. Nevertheless, the joint state at any time after $t_1$ is a product state. (b) Multiple universe picture. In both universes, an EPR pair is created in the distant past. At time $t_0$, a qubit emerges from the CTC in each universe. At time $t_1$ in each universe, half of an EPR pair is put into the CTC and goes back in time to emerge at $t_0$ in the other universe. Each EPR particle originally created is entangled with a partner in the other universe and in a product state with the other particle in its own universe.

Figure 2

The linearity trap. The action of a nonlinear map $\mathcal{N}$ on states ${\rho }_1$ and ${\rho }_2$ does not determine the action on their mixture. An example of such a map is the evolution of states in the CTC model. So, although a CTC allows nonorthogonal pure states to be mapped to orthogonal outputs, this does not suffice to identify the states in an unknown mixture. Similarly, the apparent power of CTC-assisted computations is not enough to allow a user to sample the correct output of the computation over an arbitrary distribution of inputs.

Figure 3

The state discrimination circuit of 10. The circuit on $A$ and CTC is designed to distinguish pure states $|0⟩$ and $|\psi ⟩$. $U$ is chosen with $U|\psi ⟩=|1⟩$ which leads to fixed points $|0⟩⟨0|$ when $|0⟩$ is input and $|1⟩⟨1|$ when $|\psi ⟩$ is input. However, faced with the task of distinguishing an unknown mixture labeled by $R$ as in Eq. (3), the output ${\rho }_{RA}^{\prime }={\rho }_R\otimes {\rho }_A^{\prime }$. The output of the circuit is independent of the identity of the state.