Computation models such as circuits describe sequences of computation steps that are carried out one after the other. In other words, algorithm design is traditionally subject to the restriction imposed by a fixed causal order. We address a novel computing paradigm beyond quantum computing, replacing this assumption by mere logical consistency: We study non-causal circuits, where a fixed time structure within a gate is locally assumed whilst the global causal structure between the gates is dropped. We present examples of logically consistent non-causal circuits outperforming all causal ones; they imply that suppressing loops entirely is more restrictive than just avoiding the contradictions they can give rise to. That fact is already known for correlations as well as for communication, and we here extend it to computation.
Computation models such as circuits describe sequences of computation steps that are carried out one after the other. In other words, algorithm design is traditionally subject to the restriction imposed by a fixed causal order. We address a novel computing paradigm beyond quantum computing, replacing this assumption by mere logical consistency: We study non-causal circuits, where a fixed time structure within a gate is locally assumed whilst the global causal structure between the gates is dropped. We present examples of logically consistent non-causal circuits outperforming all causal ones; they imply that suppressing loops entirely is more restrictive than just avoiding the contradictions they can give rise to. That fact is already known for correlations as well as for communication, and we here extend it to computation.
Computation models such as circuits describe sequences of computation steps that are carried out one after the other. In other words, algorithm design is traditionally subject to the restriction imposed by a fixed causal order. We address a novel computing paradigm beyond quantum computing, replacing this assumption by mere logical consistency: We study non-causal circuits, where a fixed time structure within a gate is locally assumed whilst the global causal structure between the gates is dropped. We present examples of logically consistent non-causal circuits outperforming all causal ones; they imply that suppressing loops entirely is more restrictive than just avoiding the contradictions they can give rise to. That fact is already known for correlations as well as for communication, and we here extend it to computation.
Computation models such as circuits describe sequences of computation steps that are carried out one after the other. In other words, algorithm design is traditionally subject to the restriction imposed by a fixed causal order. We address a novel computing paradigm, replacing this assumption by mere logical consistency: We study non-causal circuits, where a fixed time structure within a gate is locally assumed whilst the global causal structure between the gates is dropped. We present examples of logically consistent non-causal circuits outperforming all causal ones; they imply that suppressing loops entirely is more restrictive than just avoiding the contradictions they can give rise to. That fact is already known for correlations as well as for communication, and we here extend it to computation.
Bell non-local correlations cannot be naturally explained in a fixed causal structure. This serves as a motivation for considering models where no global assumption is made beyond logical consistency. The assumption of a fixed causal order between a set of parties, together with free randomness, implies device-independent inequalities—just as the assumption of locality does. It is known that local validity of quantum theory is consistent with violating such inequalities. Moreover, for three parties or more, even the (stronger) assumption of local classical probability theory plus logical consistency allows for violating causal inequalities. Here, we show that a classical environment (with which the parties interact), possibly containing loops, is logically consistent if and only if whatever the involved parties do, there is exactly one fixed-point, the latter being representable as a mixture of deterministic fixed-points. We further show that the non-causal view allows for a model of computation strictly more powerful than computation in a world of fixed causal orders.
Can quantum computation become more powerful when operations do not need to follow a definite causal order? We study this question in the process matrix formalism of Oreshkov et al. (Nature Communications, 2012), which allows quantum operations to be connected without a fixed global order. In the computational model, a quantum circuit succinctly describes a process matrix, and the algorithm is given access to its generated channel, with computational cost measured by the size of the generating circuit.
We give polynomial-time algorithms in two settings. First, general process matrix computation suffices to solve every problem in NP. The valid processes used by our algorithm satisfy the purification postulate of Araújo et al. (Quantum, 2017), and their generated channels are unitary, although their generating circuits are not. Second, requiring the process matrices themselves to be pure, we give a polynomial-time algorithm for unique-sink orientation, a general problem capturing several longstanding computational problems in optimization. Our unitary generators are constructed explicitly and efficiently. Assuming that unique-sink orientation has no quantum polynomial-time algorithm, our result shows that indefinite causal order can provide computational power beyond BQP within the process matrix formalism, even while preserving unitarity.
The fundamental nature of causality has been challenged by quantum theory. In particular, recent developments have shown that by relaxing the standard assumption that quantum events are embedded in a fixed background causal structure, a new kind of causal relations, indefinite, can emerge. These indefinite causal structures have been interpreted as causal loops allowing for the violation of a form of causality without paradoxes. On the other hand, quantum contextuality shows that any attempt to extend quantum theory such that classical logic holds in the extended domain fails due to the rise of inconsistent logical loops. There has been increasing evidence that it is a key feature in the understanding quantum paradoxes. This thesis aims at improving our understanding of indefinite causal orders and quantum paradoxes in order to address the question: “Could the non-fundamental nature of causality be related to a form of contextuality ?”The process matrix formalism is a mathematical framework which, in analogy withentanglement and the violation of Bell inequalities (nonlocality), offers new tools - witnesses of causal nonseparability and the violation of causal inequalities with noncausalcorrelations - to study and identify indefinite causal orders. In a bottom-up approach, wehave identified a large class of physically implementable processes, the quantum circuitswith quantum control of causal order (QC-QCs), that includes causally nonseparable processes such as the celebrated “quantum switch”. However these circuits cannot be used to violate causal inequalities. Nevertheless, in another work, I have proposed a significant relaxation of assumptions to certify the causal nonseparability of many processes, showing that it can be done in a semi-device-independent scenario with untrusted local operations and trusted quantum inputs. In particular, I have shown that the quantum switch can generate noncausal correlations in this kind of scenario.In order to refine my understanding of quantum contextuality, I have investigated theorigins of the Kochen-Specker theorem and I have analysed how the Hardy paradox entails a form of logical contextuality. I have identified that the two possible intermediatemeasurements involved in a pre-post-selection version of the paradox differ causally fromeach other. This analysis might be useful to study of the Frauchiger-Renner paradox, a“meta-version” of the Hardy paradox. On a more metaphysical aspect, I have argued fora “Gödelian hunch” from quantum theory, the idea that quantum paradoxes emerge froma lack of distinction between theoretical and metatheoretical objects.Finally, in order to establish a link between indefinite causal orders and contextuality,I have proposed a new causal game, in which the grandfather paradox is formalized interms of a logical inequality. Some process matrices can violate the causal inequalitywithout violating the logical one. I suggest that the emergence of logical inconsistenciesfrom the violation of a logical inequality might be interpreted as a form of contextuality.
We show that the computational power of the non-causal circuit model, i.e. the circuit model where the assumption of a global causal order is replaced by the assumption of logical consistency , is completely characterized by the complexity class UP ∩ coUP . An example of a problem in that class is factorization. Our result implies that classical deterministic closed timelike curves (CTCs) cannot efficiently solve problems that lie outside of that class. Thus, in stark contrast to other CTC models, these CTCs cannot efficiently solve NP-complete problems, unless NP = UP ∩ coUP = co NP , which lets their existence in nature appear less implausible . This result gives a new characterization of UP ∩ coUP in terms of fixed points.