Simulating the quantum switch with quantum circuits is computationally hard

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ⁿ. 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.