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:0912.0195 · Physical Review A

Quantum computations without definite causal structure

Giulio Chiribella, Giacomo Mauro D’Ariano, Paolo Perinotti, Benoît Valiron

Published Aug 14, 2013• 633 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreva.88.022318

Related papers

Beyond causally ordered quantum computers

Giulio Chiribella, Giacomo Mauro D’Ariano, Paolo Perinotti +1 more

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.

•Jan 1, 2012•2 citations

Quantum Circuits with Classical Versus Quantum Control of Causal Order

Julian Wechs, Hippolyte Dourdent, Alastair A. Abbott +1 more

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.

arXiv:2101.08796•PRX Quantum•Aug 26, 2021•101 citations

Simulating the quantum switch with quantum circuits is impossible

Caisheng Cheng

The quantum switch is a higher-order transformation that combines input quantum channels in an indefinite causal order. Whether quantum circuits can simulate its action, and how many calls to the input channels such a simulation requires, are natural questions about the power of quantum control of causal order. In this work, we prove that no quantum circuit with classically controlled causal order can exactly and deterministically simulate the quantum switch for arbitrary input channels using any finite number of calls. This impossibility holds already for qubit channels and extends to the complete $r$-switch, which coherently controls all permutations of $r$ input channels. These results settle the question of exact deterministic circuit simulation of the quantum switch. They demonstrate that processes with indefinite causal order cannot, in general, be efficiently simulated in this setting even by quantum circuits with classically controlled causal order.

arXiv:2611.10615•Nov 7, 2026•1 citation

Computational Advantage from a Quantum Superposition of Qubit Gate Orders

Martin J. Renner, Časlav Brukner

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.

arXiv:2112.14541•Physical Review Letters•Jun 10, 2022•64 citations

Infinite or indefinite: the query cost of simulating the quantum switch

Dantong Li

The quantum switch applies two operations in a coherent superposition of their causal orders and is a simple example of indefinite causal order. No quantum circuit that uses each operation once in a definite order can even describe it, yet photonic experiments have demonstrated its physical realization. We ask how many calls to the black-box operations a quantum computer in the circuit model needs to reproduce the switch. If one of the black boxes is known to be unitary, three calls suffice. For general channels on a $d$-dimensional system, we prove three results. In all three, circuits may use classical feed-forward and unlimited ancillary quantum memory. First, no finite number of calls suffices for exact simulation in the worst case. Second, approximation to any fixed error below $1/2$, measured in half the diamond norm, requires $Ω(d^{1/4})$ calls, exponential in the number of qubits. Third, an ordinary circuit can require exponentially many calls to obtain a single bit that the switch extracts with a few uses. We consider a device whose actual noise is dephasing in a fixed unknown basis and test it against a theoretical depolarizing model. The two channels have the same entanglement and average gate fidelities, so these figures alone do not distinguish them. At fixed noise strength, the quantum switch tells them apart with a number of device uses independent of $d$, whereas the circuit model requires $Ω(d^{1/16})$ calls. Noise characterization is needed for quantum error correction, and this gives a provable query advantage of the switch in a task relevant to practical quantum computing. We invite future work that extends such advantages to more practical computing tasks.

arXiv:2611.16229•Nov 12, 2026•0 citations

Simulating the quantum switch with quantum circuits is computationally hard

Jessica Bavaresco, Hlér Kristjánsson, Mio Murao +4 more

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.

arXiv:2409.18202•Nature Communications•Nov 20, 2025•23 citations
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.
The quantum switch is a higher-order transformation that combines input quantum channels in an indefinite causal order. Whether quantum circuits can simulate its action, and how many calls to the input channels such a simulation requires, are natural questions about the power of quantum control of causal order. In this work, we prove that no quantum circuit with classically controlled causal order can exactly and deterministically simulate the quantum switch for arbitrary input channels using any finite number of calls. This impossibility holds already for qubit channels and extends to the complete rrr-switch, which coherently controls all permutations of rrr input channels. These results settle the question of exact deterministic circuit simulation of the quantum switch. They demonstrate that processes with indefinite causal order cannot, in general, be efficiently simulated in this setting even by quantum circuits with classically controlled causal order.
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.
The quantum switch applies two operations in a coherent superposition of their causal orders and is a simple example of indefinite causal order. No quantum circuit that uses each operation once in a definite order can even describe it, yet photonic experiments have demonstrated its physical realization. We ask how many calls to the black-box operations a quantum computer in the circuit model needs to reproduce the switch. If one of the black boxes is known to be unitary, three calls suffice. For general channels on a ddd-dimensional system, we prove three results. In all three, circuits may use classical feed-forward and unlimited ancillary quantum memory. First, no finite number of calls suffices for exact simulation in the worst case. Second, approximation to any fixed error below 1/21/21/2, measured in half the diamond norm, requires Ω(d1/4)Ω(d^{1/4})Ω(d1/4) calls, exponential in the number of qubits. Third, an ordinary circuit can require exponentially many calls to obtain a single bit that the switch extracts with a few uses. We consider a device whose actual noise is dephasing in a fixed unknown basis and test it against a theoretical depolarizing model. The two channels have the same entanglement and average gate fidelities, so these figures alone do not distinguish them. At fixed noise strength, the quantum switch tells them apart with a number of device uses independent of ddd, whereas the circuit model requires Ω(d1/16)Ω(d^{1/16})Ω(d1/16) calls. Noise characterization is needed for quantum error correction, and this gives a provable query advantage of the switch in a task relevant to practical quantum computing. We invite future work that extends such advantages to more practical computing tasks.
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.