We show that quantum theory allows for transformations of black boxes that cannot be realized by inserting the input black boxes within a circuit in a predefined causal order. The simplest example of such a transformation is the classical switch of black boxes, where two input black boxes are arranged in two different orders conditionally on the value of a classical bit. The quantum version of this transformation---the quantum switch---produces an output circuit where the order of the connections is controlled by a quantum bit, which becomes entangled with the circuit structure. Simulating these transformations in a circuit with fixed causal structure requires either postselection or an extra query to the input black boxes.
We show that quantum theory allows for transformations of black boxes that cannot be realized by inserting the input black boxes within a circuit in a predefined causal order. The simplest example of such a transformation is the classical switch of black boxes, where two input black boxes are arranged in two different orders conditionally on the value of a classical bit. The quantum version of this transformation---the quantum switch---produces an output circuit where the order of the connections is controlled by a quantum bit, which becomes entangled with the circuit structure. Simulating these transformations in a circuit with fixed causal structure requires either postselection or an extra query to the input black boxes.
We show that quantum theory allows for transformations of black boxes that cannot be realized by inserting the input black boxes within a circuit in a pre-defined causal order. The simplest example of such a transformation is the classical switch of black boxes, where two input black boxes are arranged in two different orders conditionally on the value of a classical bit. The quantum version of this transformation-the quantum switch-produces an output circuit where the order of the connections is controlled by a quantum bit, which becomes entangled with the circuit structure. Simulating these transformations in a circuit with fixed causal structure requires either postselection, or an extra query to the input black boxes.
Quantum supermaps are transformations that map quantum operations to quantum operations.It is known that quantum supermaps which respect a definite, predefined causal order between their input operations correspond to fixed-order quantum circuits, also called quantum combs.A systematic understanding of the physical interpretation of more general types of quantum supermaps-in particular, those incompatible with a definite causal structure-is however lacking.In this paper, we identify two types of circuits that naturally generalize the fixed-order case and that likewise correspond to distinct classes of quantum supermaps, which we fully characterize.We first introduce "quantum circuits with classical control of causal order," in which the order of operations is still well defined, but not necessarily fixed in advance: it can, in particular, be established dynamically, in a classically controlled manner, as the circuit is being used.We then consider "quantum circuits with quantum control of causal order," in which the order of operations is controlled coherently.The supermaps described by these classes of circuits are physically realizable, and the latter encompasses all known examples of physically realizable processes with indefinite causal order, including the celebrated "quantum switch."Interestingly, it also contains other examples arising from the combination of dynamical and coherent control of causal order, and we detail explicitly one such process.Nevertheless, we show that quantum circuits with quantum control of causal order can only generate "causal" correlations, compatible with a well-defined causal order.We furthermore extend our considerations to probabilistic circuits that produce also classical outcomes, and we demonstrate by an example how the characterizations derived in this work allow us to identify advantages for quantum information processing tasks that could be demonstrated in practice.
In an ordinary quantum algorithm the gates are applied in a fixed order on the systems. The introduction of indefinite causal structures allows us to relax this constraint and control the order of the gates with an additional quantum state. It is known that this quantum-controlled ordering of gates can reduce the query complexity in deciding a property of black-box unitaries with respect to the best algorithm in which the gates are applied in a fixed order. However, all tasks explicitly found so far require unitaries that either act on unbounded dimensional quantum systems in the asymptotic limit (the limiting case of a large number of black-box gates) or act on qubits, but then involve only a few unitaries. Here we introduce tasks (i) for which there is a provable computational advantage of a quantum-controlled ordering of gates in the asymptotic case and (ii) that require only qubit gates and are therefore suitable to demonstrate this advantage experimentally. We study their solutions with the quantum n-switch and within the quantum circuit model and find that while the n-switch requires to call each gate only once, a causal algorithm has to call at least 2n-1 gates. Furthermore, the best known solution with a fixed gate ordering calls O[n log_{2}(n)] gates.
Quantum theory is consistent with a computational model permitting black-box operations to be applied in an indefinite causal order, going beyond the standard circuit model of computation. The quantum switch -- the simplest such example -- has been shown to provide numerous information-processing advantages. Here, we prove that the action of the quantum switch on two n-qubit quantum channels cannot be simulated deterministically and exactly by any causally ordered quantum circuit that uses M calls to one channel and one call to the other, if M≤max(2,2n−1). This demonstrates an exponential separation in quantum query complexity of indefinite causal order compared to standard quantum circuits.
Abstract Higher-order transformations acting on input quantum channels in an indefinite causal order—such as the quantum switch—cannot be described by quantum circuits using the same number of calls to the input channels. A natural question is whether they can be simulated, i.e., whether their action can be exactly and deterministically reproduced by a quantum circuit with more calls to the input channels. Here, we prove that the quantum switch acting on two n -qubit channels cannot be simulated by any quantum circuit using k calls to one channel and one to the other, if k < 2 n . This establishes an exponential separation in quantum query complexity between processes with indefinite causal order and quantum circuits. Moreover, even with one extra call to both input channels, such a simulation remains impossible. We further demonstrate the robustness of this separation by extending the result to probabilistic and approximate simulations scenarios.
We study the notion of causal orders for the cases of (classical and quantum) circuits and spacetime events. We show that every circuit can be immersed into a classical spacetime, preserving the compatibility between the two causal structures. Using the process matrix formalism, we analyse the realisations of the quantum switch using 4 and 3 spacetime events in classical spacetimes with fixed causal orders, and the realisation of a gravitational switch with only 2 spacetime events that features superpositions of different gravitational field configurations and their respective causal orders. We show that the current quantum switch experimental implementations do not feature superpositions of causal orders between spacetime events, and that these superpositions can only occur in the context of superposed gravitational fields. We also discuss a recently introduced operational notion of an event, which does allow for superpositions of respective causal orders in flat spacetime quantum switch implementations. We construct two observables that can distinguish between the quantum switch realisations in classical spacetimes, and gravitational switch implementations in superposed spacetimes. Finally, we discuss our results in the light of the modern relational approach to physics.