Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1601.06522 · Entropy

Non-Causal Computation

Ämin Baumeler, Stefan Wolf

Published Jul 2, 2017• 19 citations
arXivHTMLPDF

Abstract

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.

DOI
10.3390/e19070326

Related papers

Device-independent test of causal order and relations to fixed-points

Ämin Baumeler, Stefan Wolf

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.

arXiv:1511.05444•New Journal of Physics•Apr 4, 2016•27 citations

Computational tameness of classical non-causal models

Ämin Baumeler, Stefan Wolf

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.

arXiv:1611.05641•Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences•Jan 1, 2018•18 citations

What Can Be Computed with Indefinite Causal Structure?

Omri Shmueli

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 $\textbf{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 $\textbf{BQP}$ within the process matrix formalism, even while preserving unitarity.

quant-pharXiv:2610.40573•Oct 30, 2026•0 citations

Witnesses of causal nonseparability: an introduction and a few case studies

Cyril Branciard

It was recently realised that quantum theory allows for so-called causally nonseparable processes, which are incompatible with any definite causal order. This was first suggested on a rather abstract level by the formalism of process matrices, an extension of the quantum formalism which only assumes that quantum theory holds locally in some observers' laboratories, but does not impose a global causal structure; it was then shown, on a more practical level, that the quantum switch-a new, already implementable resource for quantum computation that goes beyond causally ordered circuits-provided precisely a physical example of a causally nonseparable process. To demonstrate that a given process is causally nonseparable, the concept of witnesses of causal nonseparability was introduced. Here we present a shorter introduction to this concept, and concentrate on some explicit examples-by considering in particular different noise models for the quantum switch-to show how to construct and use such witnesses in practice.

arXiv:1603.00043•Scientific Reports•May 18, 2016•58 citations

What makes a causal loop consistent?

Hippolyte Dourdent, Andreas Leitherer, Emanuel-Cristian Boghiu +3 more

Causal loops escape paradoxes if they generate valid probabilities under arbitrary independent local interventions. We show that a deterministic classical process is logically consistent if and only if it contains no signaling loops: cyclic signaling is forbidden but cyclic causation is not, allowing indefinite causal order. Logical consistency is then found to hold exactly when the list of events of a process is pairwise exclusive and complete, providing the first event-based, intervention-free, non-recursive characterization of consistent causal loops. Our results repair a previously introduced intervention-free criterion that misses global loops and reveal that what makes deterministic classical communications without causal order consistent is a multipartite form of Specker's principle: if any two of several questions can be answered jointly, so can all of them.

quant-pharXiv:2609.39735•Oct 1, 2026•1 citation

Admissible Causal Structures and Correlations

Eleftherios-Ermis Tselentis, Ämin Baumeler

It is well known that if one assumes quantum theory to hold locally, then processes with indefinite causal order and cyclic causal structures become feasible.Here we study qualitative limitations on causal structures and correlations imposed by local quantum theory.We find a necessary graph-theoretic criterion-the "siblings-on-cycles" property-for a causal structure to be admissible: only such causal structures admit a realization consistent with local quantum theory.We conjecture that this property is moreover sufficient.This conjecture is motivated by an explicit construction of quantum causal models, and is supported by numerical calculations.We show that these causal models, in a restricted setting, are indeed consistent.We identify two sets of causal structures that, in the classical-deterministic case, forbid and give rise to noncausal correlations, respectively.

arXiv:2210.12796•PRX Quantum•Oct 11, 2023•17 citations
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.
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.
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.
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\textbf{NP}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\textbf{BQP}BQP within the process matrix formalism, even while preserving unitarity.
It was recently realised that quantum theory allows for so-called causally nonseparable processes, which are incompatible with any definite causal order. This was first suggested on a rather abstract level by the formalism of process matrices, an extension of the quantum formalism which only assumes that quantum theory holds locally in some observers' laboratories, but does not impose a global causal structure; it was then shown, on a more practical level, that the quantum switch-a new, already implementable resource for quantum computation that goes beyond causally ordered circuits-provided precisely a physical example of a causally nonseparable process. To demonstrate that a given process is causally nonseparable, the concept of witnesses of causal nonseparability was introduced. Here we present a shorter introduction to this concept, and concentrate on some explicit examples-by considering in particular different noise models for the quantum switch-to show how to construct and use such witnesses in practice.
Causal loops escape paradoxes if they generate valid probabilities under arbitrary independent local interventions. We show that a deterministic classical process is logically consistent if and only if it contains no signaling loops: cyclic signaling is forbidden but cyclic causation is not, allowing indefinite causal order. Logical consistency is then found to hold exactly when the list of events of a process is pairwise exclusive and complete, providing the first event-based, intervention-free, non-recursive characterization of consistent causal loops. Our results repair a previously introduced intervention-free criterion that misses global loops and reveal that what makes deterministic classical communications without causal order consistent is a multipartite form of Specker's principle: if any two of several questions can be answered jointly, so can all of them.
It is well known that if one assumes quantum theory to hold locally, then processes with indefinite causal order and cyclic causal structures become feasible.Here we study qualitative limitations on causal structures and correlations imposed by local quantum theory.We find a necessary graph-theoretic criterion-the "siblings-on-cycles" property-for a causal structure to be admissible: only such causal structures admit a realization consistent with local quantum theory.We conjecture that this property is moreover sufficient.This conjecture is motivated by an explicit construction of quantum causal models, and is supported by numerical calculations.We show that these causal models, in a restricted setting, are indeed consistent.We identify two sets of causal structures that, in the classical-deterministic case, forbid and give rise to noncausal correlations, respectively.