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:2409.18202 · Nature Communications

Simulating the quantum switch with quantum circuits is computationally hard

Jessica Bavaresco, Hlér Kristjánsson, Mio Murao, Tatsuki Odake, Marco Túlio Quintino, Philip Taranto, Satoshi Yoshida

Published Nov 20, 2025• 3 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1038/s41467-025-64996-6

Related papers

Exponential separation in quantum query complexity of the quantum switch with respect to simulations with standard quantum circuits

Hlér Kristjánsson, Tatsuki Odake, Satoshi Yoshida +4 more

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 \leq \max(2, 2^n-1)$. This demonstrates an exponential separation in quantum query complexity of indefinite causal order compared to standard quantum circuits.

arXiv:2409.18420•Sep 27, 2024•0 citations

Probabilistic channel distillation via indefinite causal order

Spiros Kechrimparis, James Moran, Hyukjoon Kwon

The quantum switch has been widely studied as a prototypical example of indefinite causal order in quantum information processing. However, the potential advantages of utilizing more general forms of indefinite causal orders remain largely unexplored. We study higher-order switches, which involve concatenated applications of the quantum switch, and we demonstrate that they provide a strict advantage over the conventional quantum switch in the task of quantum channel distillation. Specifically, we show that higher-order quantum switches enable the probabilistic distillation of any qubit Pauli channel into the identity channel with nonzero probability. This capability contrasts with the conventional quantum switch, which allows only a limited set of Pauli channels to be distilled with nonzero probability. We observe that, counterintuitively, the distillation rate generally increases the noisier the channel is. We fully characterize the asymptotic distillation rates of higher-order superswitches for qubit Pauli channels. Finally, we prove a no-go result for multiqubit generalizations.

arXiv:2501.13696•Physical Review Research•Nov 4, 2025•2 citations

Higher-Order Programs with Indefinite Causal Orders: a Linear Approach to Coherent Control of Quantum Processes

Kathleen Barsse, Romain Péchoux, Simon Perdrix

Processes with indefinite causal orders (ICOs), such as the quantum switch, are higher-order quantum processes that superpose the order in which quantum operations are performed. Such coherent control yields computational advantages but is not faithfully captured by existing quantum programming languages: either they are restricted to the unitary case, and thus cannot combine ICOs with measurement, or they treat coherent control nonlinearly. In both cases, they do not realize the full computational power of ICOs. We introduce a higher-order quantum functional language that supports general quantum computation, not merely the permutation of channels, and whose linear type system allows quantum control to be well-defined beyond the unitary case, on arbitrary quantum channels. We equip this language with a small-step operational semantics that synchronizes measurement outcomes across superposed branches, using device references and a memory function. We also give a denotational semantics by means of completely positive maps. With linearity as the only constraint, some well-typed terms would denote unphysical maps. We therefore impose a typing discipline that goes beyond linearity, and interpret programs in the causal category Caus[CPM], under which every well-typed program is physically meaningful, a property that can be checked statically and efficiently. We prove soundness, and study the language's expressive power: it can express every quantum channel at first order, and at second order a large subclass of the so-called quantum circuits with quantum control (QC-QCs), containing the quantum switch. Last but not least, we show that this language is well-designed enough to be extended to the nonlinear setting with recursion.

cs.LOCross-listedarXiv:2607.09534•Jul 13, 2026•0 citations

Quantum query complexity of Boolean functions under indefinite causal order

Alastair A. Abbott, Mehdi Mhalla, Pierre Pocreau

The standard model of quantum circuits assumes operations are applied in a fixed sequential “causal” order. In recent years, the possibility of relaxing this constraint to obtain causally indefinite computations has received significant attention. The quantum switch, for example, uses a quantum system to coherently control the order of operations. Several computational and information-theoretical advantages have been demonstrated, raising questions as to whether advantages can be obtained in a more unified complexity theoretic framework. In this paper, we approach this problem by studying the query complexity of Boolean functions under general higher-order quantum computations. To this end, we generalize the framework of query complexity from quantum circuits to quantum supermaps to compare different models on an equal footing. We show that the recently introduced class of quantum circuits with quantum control of causal order cannot lead to any reduction in query complexity, and that any potential advantage arising from causally indefinite supermaps can be bounded by the polynomial method, as is the case with quantum circuits. Nevertheless, we find some functions for which the minimum error with which they can be computed using two queries is strictly lower when exploiting causally indefinite supermaps. Published by the American Physical Society 2024

arXiv:2307.10285•Physical Review Research•Jul 26, 2024•4 citations

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 computations without definite causal structure

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

arXiv:0912.0195•Physical Review A•Aug 14, 2013•524 citations
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.
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 nnn-qubit quantum channels cannot be simulated deterministically and exactly by any causally ordered quantum circuit that uses MMM calls to one channel and one call to the other, if M≤max⁡(2,2n−1)M \leq \max(2, 2^n-1)M≤max(2,2n−1). This demonstrates an exponential separation in quantum query complexity of indefinite causal order compared to standard quantum circuits.
The quantum switch has been widely studied as a prototypical example of indefinite causal order in quantum information processing. However, the potential advantages of utilizing more general forms of indefinite causal orders remain largely unexplored. We study higher-order switches, which involve concatenated applications of the quantum switch, and we demonstrate that they provide a strict advantage over the conventional quantum switch in the task of quantum channel distillation. Specifically, we show that higher-order quantum switches enable the probabilistic distillation of any qubit Pauli channel into the identity channel with nonzero probability. This capability contrasts with the conventional quantum switch, which allows only a limited set of Pauli channels to be distilled with nonzero probability. We observe that, counterintuitively, the distillation rate generally increases the noisier the channel is. We fully characterize the asymptotic distillation rates of higher-order superswitches for qubit Pauli channels. Finally, we prove a no-go result for multiqubit generalizations.
Processes with indefinite causal orders (ICOs), such as the quantum switch, are higher-order quantum processes that superpose the order in which quantum operations are performed. Such coherent control yields computational advantages but is not faithfully captured by existing quantum programming languages: either they are restricted to the unitary case, and thus cannot combine ICOs with measurement, or they treat coherent control nonlinearly. In both cases, they do not realize the full computational power of ICOs. We introduce a higher-order quantum functional language that supports general quantum computation, not merely the permutation of channels, and whose linear type system allows quantum control to be well-defined beyond the unitary case, on arbitrary quantum channels. We equip this language with a small-step operational semantics that synchronizes measurement outcomes across superposed branches, using device references and a memory function. We also give a denotational semantics by means of completely positive maps. With linearity as the only constraint, some well-typed terms would denote unphysical maps. We therefore impose a typing discipline that goes beyond linearity, and interpret programs in the causal category Caus[CPM], under which every well-typed program is physically meaningful, a property that can be checked statically and efficiently. We prove soundness, and study the language's expressive power: it can express every quantum channel at first order, and at second order a large subclass of the so-called quantum circuits with quantum control (QC-QCs), containing the quantum switch. Last but not least, we show that this language is well-designed enough to be extended to the nonlinear setting with recursion.
The standard model of quantum circuits assumes operations are applied in a fixed sequential “causal” order. In recent years, the possibility of relaxing this constraint to obtain causally indefinite computations has received significant attention. The quantum switch, for example, uses a quantum system to coherently control the order of operations. Several computational and information-theoretical advantages have been demonstrated, raising questions as to whether advantages can be obtained in a more unified complexity theoretic framework. In this paper, we approach this problem by studying the query complexity of Boolean functions under general higher-order quantum computations. To this end, we generalize the framework of query complexity from quantum circuits to quantum supermaps to compare different models on an equal footing. We show that the recently introduced class of quantum circuits with quantum control of causal order cannot lead to any reduction in query complexity, and that any potential advantage arising from causally indefinite supermaps can be bounded by the polynomial method, as is the case with quantum circuits. Nevertheless, we find some functions for which the minimum error with which they can be computed using two queries is strictly lower when exploiting causally indefinite supermaps. Published by the American Physical Society 2024
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.
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.