Quantum computational complexity in the presence of closed timelike curves

Quantum computation with quantum data that can traverse closed timelike curves represents a new physical model of computation. We argue that a model of quantum computation in the presence of closed timelike curves can be formulated which represents a valid quantification of resources given the ability to construct compact regions of closed timelike curves. The notion of self-consistent evolution for quantum computers whose components follow closed timelike curves, as pointed out by Deutsch [Phys. Rev. D 44, 3197 (1991)], implies that the evolution of the chronology respecting components which interact with the closed timelike curve components is nonlinear. We demonstrate that this nonlinearity can be used to efficiently solve computational problems which are generally thought to be intractable. In particular we demonstrate that a quantum computer which has access to closed timelike curve qubits can solve $\mathit{NP}$-complete problems with only a polynomial number of quantum gates.

Figure 1

Pseudospacetime diagram depicting quantum evolution in the presence of qubits which traverse closed timelike curves. The arrows indicate the forward direction of time for each individual qubit. The $n$ qubits on the left are the chronology respecting qubits and the $l$ qubits on the right are the qubits which traverse closed timelike curves. The above diagram is not a real spacetime diagram, but is instead a schematic describing the temporal evolution of the involved qubits. That quantum circuits in general spacetimes can be brought to this schematic form is argued by Deutsch [16].

Figure 2

The temporal origin problem. While there is a notion of the time at which the CTC data first interact with the chronology respecting data, for evolution entirely acting on the CTC qubits before this time, there are multiple ways to choose the temporal origin. Here we show this ambiguity graphically with the dashed line representing the time at which the consistency equation is applied. As shown in the text, this temporal origin ambiguity does not give rise to contradictions in the self consistency condition, Eq. (1).