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

The main question we ask is how causality limits 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. We investigate the computational power of process matrices [1], e.g., the class of efficiently decidable languages with process matrices. Does it 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 vein, 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 of how much of UP ⋂ coUP can efficiently be decided with quantum algorithms without having to violate causality. This question connects quantum computation 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).

 

YIRG Group