Search

In standard quantum theory, the causal relations between operations are fixed and determined by the spacetime structure. Relaxing this notion of fixed causal order has been studied extensively over the past years. A first departure allows for dynamical arrangements, where operations can influence the causal relations of future operations, as certified by violation of fixed-order inequalities. A second non-causal departure relaxes even these limitations, and is certified by violations of causal inequalities. The quantum switch, which allows a party to coherently control the order in which operations are applied, is known to be incapable of violating causal inequalities. It was therefore believed that a device-independent certification of the causal indefiniteness in the quantum switch requires extended setups incorporating spacelike separation. Here, we show that the quantum switch violates fixed-order inequalities without exploiting its indefinite nature. Concretely, we study the $k$-cycle inequalities and introduce multi-party generalizations of the quantum switch tailored to these fixed-order inequalities. We further show that, when removing the dynamical aspect, $k$-cycle inequalities become novel, facet-defining, causal inequalities. On the one hand, this means that violating $k$-cycle inequalities under this restriction requires non-causal setups. On the other hand, since $k$-cycle inequalities are just one example of fixed-order inequalities, this reopens the possibility for a device-independent certification of the quantum switch in isolation., Comment: 9 pages, 3 figures, 2 pages appendix

An astonishing feature of higher-order quantum theory is that it can accommodate indefinite causal order. In the simplest bipartite setting, there exist signaling correlations for which it is fundamentally impossible to ascribe a definite causal order for the parties' actions. Moreover, the assumptions required to arrive at such a statement (local quantum transformations and well-behaved probabilities) result in a nontrivial set of correlations, whose boundary is, to date, uncharacterized. In this work, we investigate indefinite causal order in boxworld theories. We construct a higher-order theory whose descriptor is the generalized bit (gbit) - the natural successor of the classical bit and quantum qubit. By fixing the local transformations in boxworld and asking about the global causal structure, we find that we trivially recover the full set of two-way signaling correlations. In light of this, we motivate and propose two physical principles in order to limit the set of achievable correlations: nonsignaling preservation and no signaling without system exchange. We find that a higher-order boxworld theory that respects these physical principles leads to (i) a nontrivial set of achievable correlations and (ii) a violation of some causal inequalities that is higher than what can be achieved in higher-order quantum theory. These results lead us to conjecture that the set of correlations of our higher-order boxworld theory is an outer approximation to the set of correlations produced by higher-order quantum theory., Comment: 15 + 27 pages, 9 figures

Causal models capture cause-effect relations both qualitatively - via the graphical causal structure - and quantitatively - via the model parameters. They offer a powerful framework for analyzing and constructing processes. Here, we introduce a tool - the flow of causal structures - to visualize and explore the dynamical aspect of classical-deterministic processes, arguably like those present in general relativity. The flow describes all possible ways in which the causal structure of a process can evolve. We also present an algorithm to construct its supergraph - the superflow - from the causal structure only. Consequently, the superflow of a given process may describe additional unrealizable evolutions of its causal structure. As an application, we show that if all leafs of a flow are trivial, then the corresponding process produces causal correlations only, i.e., correlations where past data influences future events only. This strengthens the result that processes, where the cycles in their causal structure are chordless, establish causal correlations only. We also discuss the main difficulties for the quantum generalization., Comment: 5 pages, 3 figures, 2 algorithms

We present a tight inequality to test the dynamical nature of spacetime. A general-relativistic violation of that inequality certifies change of curvature, in the same sense as a quantum-mechanical violation of a Bell inequality certifies a source of entanglement. The inequality arises from a minimal generalization of the Bell setup. It represents a limit on the winning chance of a collaborative multi-agent game played on the M\"obius graph. A long version of this Letter including other games and how these games certify the dynamical character of the celebrated quantum switch is accessible as arXiv:2309.15752 [gr-qc]., Comment: 5 pages, 4 figures, short version of arXiv:2309.15752 [qr-qc] with new relativistic setup

We derive multiparty games that, if the winning chance exceeds a certain limit, prove the incompatibility of the parties' causal relations with any partial order. This, in turn, means that the parties exert a back-action on the causal relations; the causal relations are dynamical. The games turn out to be representable by directed graphs, for instance by an orientation of the M\"obius ladder. We discuss these games as device-independent tests of spacetime's dynamical nature in general relativity. To do so, we design a relativistic setting where, in the Minkowski spacetime, the winning chance is bound to the limits. In contrast, we find otherwise tame processes with classical control of causal order that win the games deterministically. These suggest a violation of the bounds in gravitational implementations. We obtain these games by uncovering a "pairwise central symmetry" of the correlations in question. This symmetry allows us to recycle the facets of the acyclic subgraph polytope studied by Gr\"otschel, J\"unger, and Reinelt in the mid-80s for combinatorial optimization. In addition, we derive multiparty games in a scenario where the polytope dimension grows only linearly in the number of parties. Here, exceeding the limits not only proves the dynamical nature of the causal relations, but also that the correlations are incompatible with any global causal order., Comment: Comments welcome!

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. For one, 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 supported by numerical calculations. We show that these causal models, in a restricted setting, are indeed consistent. For another, we identify two sets of causal structures that, in the classical-deterministic case, give rise to causal and non-causal correlations respectively., Comment: 11 pages, 6 figures, extended preliminaries, details on numerical calculations, reference to source code, numerical test increased to six nodes. Comments welcome!

We show that the axiom of choice, a basic yet controversial postulate of set theory, leads to revise the standard understanding of one of the pillars of our best physical theories, namely the no-signaling principle. While it is well known that probabilistic no-signaling resources (such as quantum non-locality) are stronger than deterministic ones, we show-by invoking the axiom of choice-the opposite: Functional (deterministic) no-signaling resources can be stronger than probabilistic ones. To prove this, we devise a Bell-like game that shows a systematic advantage of functional no-signaling with respect to any probabilistic no-signaling resource., Comment: 5 pages, 3 figures

We discuss a simple toy model which allows, in a natural way, for deriving central facts from thermodynamics such as its fundamental laws, including Carnot's version of the second principle. Our viewpoint represents thermodynamic systems as binary strings, and it links their temperature to their Hamming weight. From this, we can reproduce the possibility of negative temperatures, the notion of equilibrium as the co\"incidence of two notions of temperature - statistical versus structural -, as well as the zeroth law of thermodynamics (transitivity of the thermal-equilibrium relation), which we find to be redundant, as other authors, yet at the same time not to be universally valid., Comment: 6 pages, 5 figures

Quantum theory admits ensembles of quantum nonlocality without entanglement (QNLWE). These ensembles consist of seemingly classical states (they are perfectly distinguishable and non-entangled) that cannot be perfectly discriminated with local operations and classical communication (LOCC). Here, we analyze QNLWE from a causal perspective, and show how to perfectly discriminate some of these ensembles using local operations and classical communication without definite causal order. Specifically, three parties with access to an instance of indefinite causal order-the AF/BW process-can perfectly discriminate the states in a QNLWE ensemble--the SHIFT ensemble--with local operations. Hence, this type of quantum nonlocality disappears at the expense of definite causal order while retaining classical communication. Our results thereby leverage the fact that LOCC is a conjunction of three constraints: local operations, classical communication, and definite causal order. Moreover, we show how multipartite generalizations of the AF/BW process are transformed into multiqubit ensembles that exhibit QNLWE. Such ensembles are of independent interest for cryptographic protocols and for the study of separable quantum operations unachievable with LOCC., Comment: 8 pages, 4 figures, Accepted in Physical Review Letters

Non-causal correlations certify the lack of a definite causal order among localized space-time regions. In stark contrast to scenarios where a single region influences its own causal past, some processes that distribute non-causal correlations satisfy a series of natural desiderata: logical consistency, linear and reversible dynamics, and computational tameness. Here, we present such processes among arbitrary many regions where each region influences every other but itself, and show that the above desiderata are altogether insufficient to limit the amount of "acausality" of non-causal correlations. This leaves open the identification of a principle that forbids non-causal correlations. Our results exhibit qualitative and quantitative parallels with the non-local correlations due to Ardehali and Svetlichny., Comment: 14 + 4 pages appendix, 6 figures, 1 table, final version

Causal loops, e.g., in time travel, come with two main problems. Most prominently, the grandfather antinomy describes the potentiality to inconsistencies: a problem of logical nature. The other problem is called information antinomy and is lesser known. Yet, it describes a variant of the former: There are not too few consistent solutions -- namely none -- but too many. At a first glance, the information antinomy does not seem as problematic as the grandfather antinomy, because there is no apparent logical contradiction. In this work we show that, however, both problems are equivalent under interventions: If parties can intervene in such a way that the information antinomy arises, then they can also intervene to generate a contradiction, and vice versa., Comment: In Proceedings QPL 2020, arXiv:2109.01534

Some properties of physical systems can be characterized from their correlations. In that framework, subsystems are viewed as abstract devices that receive measurement settings as inputs and produce measurement outcomes as outputs. The labeling convention used to describe these inputs and outputs does not affect the physics; and relabelings are easily implemented by rewiring the input and output ports of the devices. However, a more general class of operations can be achieved by using correlated preprocessing and postprocessing of the inputs and outputs. In contrast to relabelings, some of these operations irreversibly lose information about the underlying device. Other operations are reversible, but modify the number of cardinality of inputs and/or outputs. In this work, we single out the set of deterministic local maps as the one satisfying two equivalent constructions: an operational definition from causality, and an axiomatic definition reminiscent of the definition of quantum completely positive trace-preserving maps. We then study the algebraic properties of that set. Surprisingly, the study of these fundamental properties has deep and practical applications. First, the invariant subspaces of these transformations directly decompose the space of correlations/Bell inequalities into nonsignaling, signaling and normalization components. This impacts the classification of Bell and causal inequalities, and the construction of assemblages/witnesses in steering scenarios. Second, the left and right invertible deterministic local operations provide an operational generalization of the liftings introduced by Pironio [J. Math. Phys., 46(6):062112 (2005)]. Not only Bell-local, but also causal inequalities can be lifted; liftings also apply to correlation boxes in a variety of scenarios., Comment: 46 pages split in three independent parts (8+21+11). Numerous figures

Starting from Landauer's slogan "information is physical," we revise and modify Landauer's principle stating that the erasure of information has a minimal price in the form of a certain quantity of free energy. We establish a direct link between the erasure cost and the work value of a piece of information, and show that the former is essentially the length of the string's best compression by a reversible computation. We generalize the principle by deriving bounds on the free energy to be invested for --- or gained from, for that matter --- a general computation. We then revisit the second law of thermodynamics and compactly rephrase it (assuming the Church/Turing/Deutsch hypothesis that physical reality can be simulated by a universal Turing machine): Time evolutions are logically reversible --- "the future fully remembers the past (but not necessarily vice versa)." We link this view to previous formulations of the second law, and we argue that it has a particular feature that suggests its "logico-informational" nature, namely simulation resilience: If a computation faithfully simulates a physical process violating the law --- then that very computation procedure violates it as well., Comment: 8 pages, 3 figures

Superposition of two or more states is one of the fundamental concepts of quantum mechanics and provides the basis for several advantages quantum information processing offers. In this work, we experimentally demonstrate that quantum superposition permits two-way communication between two distant parties that can exchange only one particle once, an impossible task in classical physics. This is achieved by preparing a single photon in a coherent superposition of the two parties' locations. Furthermore, we show that this concept allows the parties to perform secure quantum communication, where the transmitted bits and even the direction of communication remain private. These important features can lead to the development of new quantum communication schemes, which are simultaneously secure and resource-efficient., Comment: Main Text (5 pages, 5 figures) + Appendix (5 pages, 2 figures); Main text substantially modified; Two authors added; Two new sections and two new figures added in the appendix; One figure moved to supplementaries

Reichenbach's principle states that in a causal structure, correlations of classical information can stem from a common cause in the common past or a direct influence from one of the events in correlation to the other. The difficulty of explaining Bell correlations through a mechanism in that spirit can be read as questioning either the principle or even its basis: causality. In the former case, the principle can be replaced by its quantum version, accepting as a common cause an entangled state, leaving the phenomenon as mysterious as ever on the classical level (on which, after all, it occurs). If, more radically, the causal structure is questioned in principle, closed space-time curves may become possible that, as is argued in the present note, can give rise to non-local correlations if to-be-correlated pieces of classical information meet in the common future --- which they need to if the correlation is to be detected in the first place. The result is a view resembling Brassard and Raymond-Robichaud's parallel-lives variant of Hermann's and Everett's relative-state formalism, avoiding "multiple realities.", Comment: 8 pages, 5 figures

One way to study the physical plausibility of closed timelike curves (CTCs) is to examine their computational power. This has been done for Deutschian CTCs (D-CTCs) and post-selection CTCs (P-CTCs), with the result that they allow for the efficient solution of problems in PSPACE and PP, respectively. Since these are extremely powerful complexity classes, which are not expected to be solvable in reality, this can be taken as evidence that these models for CTCs are pathological. This problem is closely related to the nonlinearity of this models, which also allows for example cloning quantum states, in the case of D-CTCs, or distinguishing non-orthogonal quantum states, in the case of P-CTCs. In contrast, the process matrix formalism allows one to model indefinite causal structures in a linear way, getting rid of these effects, and raising the possibility that its computational power is rather tame. In this paper we show that process matrices correspond to a linear particular case of P-CTCs, and therefore that its computational power is upperbounded by that of PP. We show, furthermore, a family of processes that can violate causal inequalities but nevertheless can be simulated by a causally ordered quantum circuit with only a constant overhead, showing that indefinite causality is not necessarily hard to simulate., Comment: 11 + 5 pages, no figures, 16 circuits. Corrected equations (33)-(36)

General relativity allows for the existence of closed time-like curves, along which a material object could travel back in time and interact with its past self. This possibility raises the question whether certain initial conditions, or more generally local operations, lead to inconsistencies and should thus be forbidden. Here we consider the most general deterministic dynamics connecting classical degrees of freedom defined on a set of bounded space-time regions, requiring that it is compatible with arbitrary operations performed in the local regions. We find that any such dynamics can be realised through reversible interactions. We further find that consistency with local operations is compatible with non-trivial time travel: Three parties can interact in such a way to be all both in the future and in the past of each other, while being free to perform arbitrary local operations., Comment: 11 pages, 3 figures

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~$\operatorname{\mathsf{UP}}\cap\operatorname{\mathsf{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~$\operatorname{\mathsf{NP-complete}}$ problems, unless~$\operatorname{\mathsf{NP}}=\operatorname{\mathsf{UP}}\cap\operatorname{\mathsf{coUP}}=\operatorname{\mathsf{coNP}}$, which lets their existence in nature appear less implausible. This result gives a new characterization of~$\operatorname{\mathsf{UP}}\cap\operatorname{\mathsf{coUP}}$ in terms of fixed points., Comment: 7 pages, 3 figures, 1 algorithm, revised

The difficulty of explaining non-local correlations in a fixed causal structure sheds new light on the old debate on whether space and time are to be seen as fundamental. Refraining from assuming space-time as given a priori has a number of consequences. First, the usual definitions of randomness depend on a causal structure and turn meaningless. So motivated, we propose an intrinsic, physically motivated measure for the randomness of a string of bits: its length minus its normalized work value, a quantity we closely relate to its Kolmogorov complexity (the length of the shortest program making a universal Turing machine output this string). We test this alternative concept of randomness for the example of non-local correlations, and we end up with a reasoning that leads to similar conclusions as in, but is conceptually more direct than, the probabilistic view since only the outcomes of measurements that can actually all be carried out together are put into relation to each other. In the same context-free spirit, we connect the logical reversibility of an evolution to the second law of thermodynamics and the arrow of time. Refining this, we end up with a speculation on the emergence of a space-time structure on bit strings in terms of data-compressibility relations. Finally, we show that logical consistency, by which we replace the abandoned causality, it strictly weaker a constraint than the latter in the multi-party case., Comment: 17 pages, 16 figures, small corrections

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., Comment: 6 pages, 4 figures

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., Comment: 24 pages, 8 figures, 4 tables

Classical correlations without predefined causal order arise from processes where parties manipulate random variables, and where the order of these interactions is not predefined. No assumption on the causal order of the parties is made, but the processes are restricted to be logically consistent under any choice of the parties' operations. It is known that for three parties or more, this set of processes is larger than the set of processes achievable in a predefined ordering of the parties. Here, we model all classical processes without predefined causal order geometrically and find that the set of such processes forms a polytope. Additionally, we model a smaller polytope --- the deterministic-extrema polytope --- where all extremal points represent deterministic processes. This polytope excludes probabilistic processes that must be --- quite unnaturally --- fine-tuned, because any variation of the weights in a decomposition into deterministic processes leads to a logical inconsistency., Comment: 14 pages, 12 figures, 1 table, improved, references updated

Quantum theory in a global space-time gives rise to non-local correlations, which cannot be explained causally in a satisfactory way; this motivates the study of theories with reduced global assumptions. Oreshkov, Costa, and Brukner (2012) proposed a framework in which quantum theory is valid locally but where, at the same time, no global space-time, i.e., predefined causal order, is assumed beyond the absence of logical paradoxes. It was shown for the two-party case, however, that a global causal order always emerges in the classical limit. Quite naturally, it has been conjectured that the same also holds in the multi-party setting. We show that counter to this belief, classical correlations locally compatible with classical probability theory exist that allow for deterministic signaling between three or more parties incompatible with any predefined causal order., Comment: 8 pages, 4 figures, title changed, improved presentation, contains two examples

The paradigmatic view where information is seen as a more fundamental concept than the laws of physics leads to a different understanding of spacetime where the causal order of events emerges from correlations between random variables representing physical quantities. In particular, such an information-theoretic approach does not enforce a global spacetime structure. By following this path, we conclude that perfect signaling correlations among three parties are possible which do not obey the restrictions imposed by global spacetime. We show this using a recent framework based on the sole assumptions that locally, quantum theory is valid and random variables can be described by probability distributions. Our result is of zero-error type and is an analog to a tripartite appearance of quantum non-locality which manifests itself by satisfying a condition with certainty whereas the same is impossible for any local theory., Comment: 5 pages, 3 figures, 2 tables, references added

In Private Information Retrieval (PIR), a client queries an n-bit database in order to retrieve an entry of her choice, while maintaining privacy of her query value. Chor, Goldreich, Kushilevitz, and Sudan showed that, in the information-theoretical setting, a linear amount of communication is required for classical PIR protocols (and thus that the trivial protocol is optimal). This linear lower bound was shown by Nayak to hold also in the quantum setting. Here, we extend Nayak's result by considering approximate privacy, and requiring security only against "specious" adversaries, which are, in analogy to classical honest-but-curious adversaries, the weakest reasonable quantum adversaries. We show that, even in this weakened scenario, Quantum Private Information Retrieval (QPIR) requires n qubits of communication. From this follows that Le Gall's recent QPIR protocol with sublinear communication complexity is not information-theoretically private, against the weakest reasonable cryptographic adversary., Comment: 8 pages, minor typos fixed, affiliation of A. B. changed, acknowledgments extended