Quantum computation with indefinite causal structures

Abstract

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.

11 + 5 pages, no figures, 16 circuits. Corrected equation (21)

References in corpus (29)

• Quantum correlations with no causal order
• Quantum computations without definite causal structure
• Theoretical framework for quantum networks
• Experimental Superposition of Orders of Quantum Gates
• Computational advantage from quantum-controlled ordering of gates
• Experimental Verification of an Indefinite Causal Order
• Perfect discrimination of no-signalling channels via quantum superposition of causal structures
• Witnessing causal nonseparability
• Closed timelike curves via post-selection: theory and experimental demonstration
• NP-complete Problems and Physical Reality
• Causal and causally separable processes
• The simplest causal inequalities and their violation
• Maximal incompatibility of locally classical behavior and global causal order in multi-party scenarios
• A purification postulate for quantum mechanics with indefinite causal order
• Multipartite Causal Correlations: Polytopes and Inequalities
• The space of logically consistent classical processes without causal order
• Localized closed timelike curves can perfectly distinguish quantum states
• Operational quantum theory without predefined time
• Effective Quantum Time Travel
• Connecting processes with indefinite causal order and multi-time quantum states
• Quantum state cloning using Deutschian closed timelike curves
• Open timelike curves violate Heisenberg's uncertainty principle
• Quantum state cloning in the presence of a closed timelike curve
• Perfect state distinguishability and computational speedups with postselected closed timelike curves
• Device-independent test of causal order and relations to fixed-points
• Closed timelike curves in measurement-based quantum computation
• Computational tameness of classical non-causal models
• Closed Timelike Curves Make Quantum and Classical Computing Equivalent
• Non-causal computation

Cited by in corpus (44)

• Experimental Quantum Communication Enhancement by Superposing Trajectories
• Computational advantage from quantum superposition of multiple temporal orders of photonic gates
• Time-delocalized quantum subsystems and operations: on the existence of processes with indefinite causal structure in quantum mechanics
• Cyclic Quantum Causal Models
• Experimentally feasible computational advantage from quantum superposition of gate orders
• Experiments on quantum causality
• Experimental Aspects of Indefinite Causal Order in Quantum Mechanics
• Observer-dependent locality of quantum events
• Resource theory of causal connection
• Shallow unitary decompositions of quantum Fredkin and Toffoli gates for connectivity-aware equivalent circuit averaging
• Higher-order Process Matrix Tomography of a passively-stable Quantum SWITCH
• Consequences of preserving reversibility in quantum superchannels
• A general framework for cyclic and fine-tuned causal models and their compatibility with space-time
• Unlimited non-causal correlations and their relation to non-locality
• Reassessing thermodynamic advantage from indefinite causal order
• Reassessing the computational advantage of quantum-controlled ordering of gates
• Genuinely Multipartite Noncausality
• Existence of processes violating causal inequalities on time-delocalised subsystems
• Embedding cyclic information-theoretic structures in acyclic spacetimes: no-go results for indefinite causality
• Experimentally demonstrating indefinite causal order algorithms to solve the generalized Deutsch's problem
• Classical communication through quantum causal structures
• Composition rules for quantum processes: a no-go theorem
• Activation of thermal states by coherently controlled thermalization processes
• Quantum chicken-egg dilemmas: Delayed-choice causal order and the reality of causal non-separability
• Quantum Supermaps are Characterized by Locality
• Trading causal order for locality
• The Multi-round Process Matrix
• Time-travelling billiard-ball clocks: a quantum model
• Relating Wigner's Friend Scenarios to Nonclassical Causal Compatibility, Monogamy Relations, and Fine Tuning
• Holonomic swap and controlled-swap gates of neutral atoms via selective Rydberg pumping
• Quantum Query Complexity of Boolean Functions under Indefinite Causal Order
• Consistent circuits for indefinite causal order
• Billiard-ball paradox for a quantum wave packet
• Quantum Correlations in Space-Time: Foundations and Applications
• Expressibility, entangling power and quantum average causal effect for causally indefinite circuits
• Quantum theory cannot violate a causal inequality
• Causal nonseparability and its implications for spatiotemporal relations
• Whether a quantum computation employs nonlocal resources is operationally undecidable
• Tripartite non-classical correlations without backwards in time signalling
• Forward-backward stochastic simulations: Q-based model for measurement and Bell-nonlocality consistent with weak local realistic premises
• Quantum probabilities for the causal ordering of events
• Flow of dynamical causal structures with an application to correlations
• Classical and Quantum Query Complexity of Boolean Functions under Indefinite Causal Order
• No quantum advantage for violating fixed-order inequalities?