Quantum mechanical closed timelike curves from indefinite causal orders

Lachlan G. Bishop

Omri Shmueli

Born in the intersection between quantum mechanics and general relativity, indefinite causal structure is the idea that in the continuum of time, some sets of events do not have an inherent causal order between them. Process matrices, introduced by Oreshkov, Costa and Brukner (Nature Communications, 2012), define quantum information processing with indefinite causal structure -- a generalization of the operations allowed in standard quantum information processing, and to date, are the most studied such generalization. Araujo et al. (Physical Review A, 2017) defined the computational complexity of process matrices, and showed that polynomial-time process matrix computation is equivalent to standard polynomial-time quantum computation with access to a weakening of post-selection Closed Timelike Curves (CTCs), that are restricted to be $\textit{linear}$. Araujo et al. accordingly defined the complexity class for efficient process matrix computation as $\mathbf{BQP}_{\ell CTC}$ (which trivially contains $\mathbf{BQP}$), and posed the open question of whether $\mathbf{BQP}_{\ell CTC}$ contains computational tasks that are outside $\mathbf{BQP}$. In this work we solve this open question under a widely believed hardness assumption, by showing that $\mathbf{NP} \subseteq \mathbf{BQP}_{\ell CTC}$. Our solution is captured by an even more restricted subset of process matrices that are purifiable (Araujo et al., Quantum, 2017), which (1) is conjectured more likely to be physical than arbitrary process matrices, and (2) is equivalent to polynomial-time quantum computation with access to $\textit{unitary}$ (which are in particular linear) post-selection CTCs. Conceptually, our work shows that the previously held belief, that non-linearity is what enables CTCs to solve $\mathbf{NP}$, is false, and raises the importance of understanding whether purifiable process matrices are physical or not.

Lee A. Rozema, Teodor Strömberg, Huan Cao +3 more

Anne-Catherine de la Hamette, Viktoria Kabel, Marios Christodoulou +1 more

Classically, the causal order of two timelike separated events A and B is fixed-either A before B or B before A. This is no longer true in quantum theory, where it is possible to encounter superpositions of causal orders. The quantum switch is one of the most prominent processes with indefinite causal order. Optical realizations of the quantum switch have been successfully implemented in experiments, but some argue that this merely simulates a process with indefinite causal order and that a superposition of spacetime metrics is required for a true realization. Here, we provide a relativistic definition of causal order between operationally defined events that defines a meaningful observable in both the general relativistic and quantum mechanical sense. Importantly, this observable does not distinguish between the indefinite causal order implemented on an optical bench and the gravitational quantum switch, a gedanken experiment where the indefinite causal order is achieved by a quantum superposition of gravitational fields. Therefore, our results support the thesis that the optical quantum switch is just as much a realization of indefinite causal order as its gravitational counterpart, which makes use of the quantum mechanical behavior of spacetime.

Časlav Brukner

Mateus Araújo, Philippe Allard Guérin, Ämin Baumeler

One way to study the physical plausibility of closed timelike curves (CTCs) is to examine their computational power. This has been done for Deutschian CTCs (D-CTCs) and postselection CTCs (P-CTCs), with the result that they allow for the efficient solution of problems in PSPACE and PP, respectively. Since these are extremely powerful complexity classes, which are not expected to be solvable in reality, this can be taken as evidence that these models for CTCs are pathological. This problem is closely related to the nonlinearity of this models, which also allows, for example, cloning quantum states, in the case of D-CTCs, or distinguishing nonorthogonal quantum states, in the case of P-CTCs. In contrast, the process matrix formalism allows one to model indefinite causal structures in a linear way, getting rid of these effects and raising the possibility that its computational power is rather tame. In this paper, we show that process matrices correspond to a linear particular case of P-CTCs, and therefore that its computational power is upperbounded by that of PP. We show, furthermore, a family of processes that can violate causal inequalities but nevertheless can be simulated by a causally ordered quantum circuit with only a constant overhead, showing that indefinite causality is not necessarily hard to simulate.