Information processing in theories with and without definite causal structures

Computer science and physics are intertwined: A physical process can be understood as information processing, and limits on information processing restrict physical theories. In this research track we exploit this synergy in order to better understand the notion of causality.

The main question we ask is what role causality plays in information processing. A model where the standard notion of causality is violated might allow for more efficient information processing or might even allow to solve tasks that are otherwise impossible. In particular, we ask what is the computational power of “process matrices” [1], i.e., what languages can efficiently be decided by “process matrices?” Does the class of efficiently decidable languages coincide with BQP, the class of efficiently decidable languages without violating causality? If no, do “process matrices” lead to efficient computation of NP-hard problems? In case this latter question is answered positively, “process matrices” would contradict an assumption in computer science: NP-hard problems are intractable in the physical world [2]. Towards answering this question, some of us managed to upper bound the computational power of causality violations à la “process matrices” in the classical setting (as opposed to the quantum setting) to UP ⋂ coUP [3]; a class (strictly) contained in NP. In the same vain we ask: What is the role of memory limitations and temporal correlations for computation. Possible cause-effect relations are constrained by memory limitations; how do these limitations carry over to computation?

Not many problems are known be in UP ⋂ coUP and conjectured to be outside of P (the class of efficiently decidable languages with a Turing machine): Factoring, discrete logarithm, simple stochastic games, parity games, … Efficient algorithms for solving the former two are known [4]. This leaves open the question whether all of UP ⋂ coUP can efficiently be decided with quantum algorithms without having to violate causality. This questions tries to connect quantum algorithms with violations of causality.

To explore causality further, we are interested in the interplay between causality and computation for theories generalizing quantum theory, e.g., in general probabilistic theories.

 

[1] O. Oreshkov, F. Costa, and Č. Brukner, “Quantum correlations with no causal order”, Nature Communications 3, 1092 (2012).

[2] S. Aaronson, “NP-complete problems and physical reality”, SIGACT News 36, 30 (2005).

[3] Ä. Baumeler, and S. Wolf, “Computational tameness of classical non-causal models”, Proceedings of the Royal Society A 474, 20170698 (2018).

[4] P. Shor, “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer”, SIAM Journal on Computing 26, 1484 (1997).