Causality
=======
What do we mean by "causality"?
- Cause-effect relations (A is the cause of B etc.)

We model these relations via a "Causal Structure."

A causal structure is a directed graph (V,E) where V is the set of nodes (events) and E the set of edges (cause-effect relations).


Common assumptions on causal structures:
1. The graph is acyclic (no "causal loops," no "time travel")
2. The structure is definite ("stage" on which computation takes places, not a physical quantity)



Motivations to relax these assumptions:
==============================
1. General Relativity (GR)
GR is consistent with closed time-like curves (CTCs), e.g., with time travel!
(see Gödel, "An example of a new type of cosmological solutions to Einstein's field equations of gravitation," Reviews of Modern Physics 21, 447 (1949))

A more accessible form of CTCs has been found by Thorne et al., where wormholes are used.
(see M. Morris, K. Thorne, U. Yurtsever, "Wormholes, Time Machines, and the Weak Energy Condition," Physical Review Letters 61, 1446 (1988))


Problems with CTCs:
A) Grandfather Antinomy
B) Information Antinomy
(see e.g., my PhD thesis: http://cqi.inf.usi.ch/publications/these_amin.pdf)


2. Quantum Theory
With the superposition principle, potentially, a big mass, e.g., a plant, could be placed in superposition of two locations. The back action of the mass on the gravitational field generates an indefinite causal structure.


Different models of CTCs:
====================
1. Deutsch CTC (DCTC): D. Deutsch, "Quantum mechanics near closed timelike curves," Physical Review D 44, 3197 (1991)
[description of the model]
Features: non-linear, cloning of quantum states
[Definition of model of computation with DCTCs]
BQP_DCTC=PSPACE: Time can be reused like space!

2. Postselected CTC (PCTC): see e.g., C. Bennett, B. Schumacher, "Simulated time travel, teleportation without communication" Talk at QUPON, Vienna (2005)
Idea: Teleport quantum state from the future to the past.
Difference to DCTC: It preserves correlations.
[description of the model]
[Definition of model of computation with PCTCs]
BQP_PCTC=PP is included in PSPACE