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:1405.3681 · Electronic Proceedings in Theoretical Computer Science

Terminality implies non-signalling

Bob Coecke

Published Dec 27, 2014• 55 citations
arXivHTMLPDF

Abstract

A 'process theory' is any theory of systems and processes which admits sequential and parallel composition. `Terminality' unifies normalisation of pure states, trace-preservation of CP-maps, and adding up to identity of positive operators in quantum theory, and generalises this to arbitrary process theories. We show that terminality and non-signalling coincide in any process theory, provided one makes causal structure explicit. In fact, making causal structure explicit is necessary to even make sense of non-signalling in process theories. We conclude that because of its much simpler mathematical form, terminality should be taken to be a more fundamental notion than non-signalling.

DOI
10.4204/eptcs.172.3

Related papers

Equivalence of relativistic causal structure and process terminality

Aleks Kissinger, Matty J. Hoban, Bob Coecke

In general relativity, `causal structure' refers to the partial order on space-time points (or regions) that encodes time-like relationships. Recently, quantum information and quantum foundations saw the emergence of a `causality principle'. In the form used in this paper, which we call `process terminality', it states that when the output of a process is discarded, then the process itself may as well be discarded. While causal structure and process terminality at first seem to be entirely different notions, they become equivalent when making explicit what the partial order actually encodes, that is, that an event in the past can influence one in its future, but not vice-versa. The framework in which we establish this equivalence is that of process theories. We show how several previous results are instances of this result and comment on how this framework could provide an ideal, minimal canvas for crafting theories of quantum gravity.

arXiv:1708.04118•Aug 14, 2017•35 citations

Picturing Indefinite Causal Structure

Aleks Kissinger, Sander Uijlen

Following on from the notion of (first-order) causality, which generalises the notion of being tracepreserving from CP-maps to abstract processes, we give a characterization for the most general kind of map which sends causal processes to causal processes. These new, second-order causal processes enable us to treat the input processes as 'local laboratories' whose causal ordering needs not be fixed in advance. Using this characterization, we give a fully-diagrammatic proof of a non-trivial theorem: namely that being causality-preserving on separable processes implies being 'completely' causality preserving. That is, causality is preserved even when the 'local laboratories' are allowed to have ancilla systems. An immediate consequence is that preserving causality is separable processes is equivalence to preserving causality for strongly non-signalling (a.k.a. localizable) processes.

arXiv:1701.00659•Electronic Proceedings in Theoretical Computer Science•Jan 1, 2017•7 citations

A categorical semantics for causal structure

Aleks Kissinger, Sander Uijlen

We present a categorical construction for modelling both definite and indefinite causal structures within a general class of process theories that include classical probability theory and quantum theory. Unlike prior constructions within categorical quantum mechanics, the objects of this theory encode fine-grained causal relationships between subsystems and give a new method for expressing and deriving consequences for a broad class of causal structures. To illustrate this point, we show that this framework admits processes with definite causal structures, namely one-way signalling processes, non-signalling processes, and quantum n-combs, as well as processes with indefinite causal structure, such as the quantum switch and the process matrices of Oreshkov, Costa, and Brukner. We furthermore give derivations of their operational behaviour using simple, diagrammatic axioms.

ACM/IEEE Symposium on Logic in Computer Science (LICS)•Jun 1, 2017•65 citations

A categorical semantics for causal structure

Aleks Kissinger, Sander Uijlen

We present a categorical construction for modelling causal structures within a general class of process theories that include the theory of classical probabilistic processes as well as quantum theory. Unlike prior constructions within categorical quantum mechanics, the objects of this theory encode fine-grained causal relationships between subsystems and give a new method for expressing and deriving consequences for a broad class of causal structures. We show that this framework enables one to define families of processes which are consistent with arbitrary acyclic causal orderings. In particular, one can define one-way signalling (a.k.a. semi-causal) processes, non-signalling processes, and quantum $n$-combs. Furthermore, our framework is general enough to accommodate recently-proposed generalisations of classical and quantum theory where processes only need to have a fixed causal ordering locally, but globally allow indefinite causal ordering. To illustrate this point, we show that certain processes of this kind, such as the quantum switch, the process matrices of Oreshkov, Costa, and Brukner, and a classical three-party example due to Baumeler, Feix, and Wolf are all instances of a certain family of processes we refer to as $\textrm{SOC}_n$ in the appropriate category of higher-order causal processes. After defining these families of causal structures within our framework, we give derivations of their operational behaviour using simple, diagrammatic axioms. Comment: Extended version of a LICS 2017 paper with the same title

arXiv:1701.04732•Logical Methods in Computer Science•Aug 9, 2019•62 citations

No-signalling constrains quantum computation with indefinite causal structure

Luca Apadula, Alessandro Bisio, Paolo Perinotti

Quantum processes with indefinite causal structure emerge when we wonder which are the most general evolutions, allowed by quantum theory, of a set of local systems which are not assumed to be in any particular causal order. These processes can be described within the framework of higher−order quantum theory which, starting from considering maps from quantum transformations to quantum transformations, recursively constructs a hierarchy of quantum maps of increasingly higher order. In this work, we develop a formalism for quantum computation with indefinite causal structures; namely, we characterize the computational structure of higher order quantum maps. Taking an axiomatic approach, the rules of this computation are identified as the most general compositions of higher order maps which are compatible with the mathematical structure of quantum theory. We provide a mathematical characterization of the admissible composition for arbitrary higher order quantum maps. We prove that these rules, which have a computational and information-theoretic nature, are determined by the more physical notion of the signalling relations between the quantum systems of the higher order quantum maps.

arXiv:2202.10214•Quantum•Feb 5, 2024•20 citations

Achieving Maximal Causal Indefiniteness in a Maximally Nonlocal Theory

Kuntal Sengupta

Quantum theory allows for the superposition of causal orders between operations, i.e., for an indefinite causal order; an implication of the principle of quantum superposition. Since a higher theory might also admit this feature, an understanding of superposition and indefinite causal order in a generalised probabilistic framework is needed. We present a possible notion of superposition for such a framework and show that in maximal theories, respecting non-signalling relations, single system state-spaces do not admit superposition; however, composite systems do. Additionally, we show that superposition does not imply entanglement. Next, we provide a concrete example of a maximally Bell-nonlocal theory, which not only admits the presented notion of superposition, but also allows for post-quantum violations of theory-independent inequalities that certify indefinite causal order; even up to an algebraic bound. These findings might point towards potential connections between a theory's ability to admit indefinite causal order, Bell-nonlocal correlations and the structure of its state spaces.

arXiv:2411.04201•Nov 6, 2024•9 citations
A 'process theory' is any theory of systems and processes which admits sequential and parallel composition. `Terminality' unifies normalisation of pure states, trace-preservation of CP-maps, and adding up to identity of positive operators in quantum theory, and generalises this to arbitrary process theories. We show that terminality and non-signalling coincide in any process theory, provided one makes causal structure explicit. In fact, making causal structure explicit is necessary to even make sense of non-signalling in process theories. We conclude that because of its much simpler mathematical form, terminality should be taken to be a more fundamental notion than non-signalling.
In general relativity, `causal structure' refers to the partial order on space-time points (or regions) that encodes time-like relationships. Recently, quantum information and quantum foundations saw the emergence of a `causality principle'. In the form used in this paper, which we call `process terminality', it states that when the output of a process is discarded, then the process itself may as well be discarded. While causal structure and process terminality at first seem to be entirely different notions, they become equivalent when making explicit what the partial order actually encodes, that is, that an event in the past can influence one in its future, but not vice-versa. The framework in which we establish this equivalence is that of process theories. We show how several previous results are instances of this result and comment on how this framework could provide an ideal, minimal canvas for crafting theories of quantum gravity.
Following on from the notion of (first-order) causality, which generalises the notion of being tracepreserving from CP-maps to abstract processes, we give a characterization for the most general kind of map which sends causal processes to causal processes. These new, second-order causal processes enable us to treat the input processes as 'local laboratories' whose causal ordering needs not be fixed in advance. Using this characterization, we give a fully-diagrammatic proof of a non-trivial theorem: namely that being causality-preserving on separable processes implies being 'completely' causality preserving. That is, causality is preserved even when the 'local laboratories' are allowed to have ancilla systems. An immediate consequence is that preserving causality is separable processes is equivalence to preserving causality for strongly non-signalling (a.k.a. localizable) processes.
We present a categorical construction for modelling both definite and indefinite causal structures within a general class of process theories that include classical probability theory and quantum theory. Unlike prior constructions within categorical quantum mechanics, the objects of this theory encode fine-grained causal relationships between subsystems and give a new method for expressing and deriving consequences for a broad class of causal structures. To illustrate this point, we show that this framework admits processes with definite causal structures, namely one-way signalling processes, non-signalling processes, and quantum n-combs, as well as processes with indefinite causal structure, such as the quantum switch and the process matrices of Oreshkov, Costa, and Brukner. We furthermore give derivations of their operational behaviour using simple, diagrammatic axioms.
We present a categorical construction for modelling causal structures within a general class of process theories that include the theory of classical probabilistic processes as well as quantum theory. Unlike prior constructions within categorical quantum mechanics, the objects of this theory encode fine-grained causal relationships between subsystems and give a new method for expressing and deriving consequences for a broad class of causal structures. We show that this framework enables one to define families of processes which are consistent with arbitrary acyclic causal orderings. In particular, one can define one-way signalling (a.k.a. semi-causal) processes, non-signalling processes, and quantum nnn-combs. Furthermore, our framework is general enough to accommodate recently-proposed generalisations of classical and quantum theory where processes only need to have a fixed causal ordering locally, but globally allow indefinite causal ordering. To illustrate this point, we show that certain processes of this kind, such as the quantum switch, the process matrices of Oreshkov, Costa, and Brukner, and a classical three-party example due to Baumeler, Feix, and Wolf are all instances of a certain family of processes we refer to as SOCn\textrm{SOC}_nSOCn​ in the appropriate category of higher-order causal processes. After defining these families of causal structures within our framework, we give derivations of their operational behaviour using simple, diagrammatic axioms. Comment: Extended version of a LICS 2017 paper with the same title
Quantum processes with indefinite causal structure emerge when we wonder which are the most general evolutions, allowed by quantum theory, of a set of local systems which are not assumed to be in any particular causal order. These processes can be described within the framework of higher−order quantum theory which, starting from considering maps from quantum transformations to quantum transformations, recursively constructs a hierarchy of quantum maps of increasingly higher order. In this work, we develop a formalism for quantum computation with indefinite causal structures; namely, we characterize the computational structure of higher order quantum maps. Taking an axiomatic approach, the rules of this computation are identified as the most general compositions of higher order maps which are compatible with the mathematical structure of quantum theory. We provide a mathematical characterization of the admissible composition for arbitrary higher order quantum maps. We prove that these rules, which have a computational and information-theoretic nature, are determined by the more physical notion of the signalling relations between the quantum systems of the higher order quantum maps.
Quantum theory allows for the superposition of causal orders between operations, i.e., for an indefinite causal order; an implication of the principle of quantum superposition. Since a higher theory might also admit this feature, an understanding of superposition and indefinite causal order in a generalised probabilistic framework is needed. We present a possible notion of superposition for such a framework and show that in maximal theories, respecting non-signalling relations, single system state-spaces do not admit superposition; however, composite systems do. Additionally, we show that superposition does not imply entanglement. Next, we provide a concrete example of a maximally Bell-nonlocal theory, which not only admits the presented notion of superposition, but also allows for post-quantum violations of theory-independent inequalities that certify indefinite causal order; even up to an algebraic bound. These findings might point towards potential connections between a theory's ability to admit indefinite causal order, Bell-nonlocal correlations and the structure of its state spaces.