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

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, Philip Taranto, Jessica Bavaresco, Marco Túlio Quintino, Mio Murao

Published Sep 27, 2024• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2409.18420

Related papers

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

Classical and Quantum Query Complexity of Boolean Functions under Indefinite Causal Order

Alastair A. Abbott, Mehdi Mhalla, Pierre Pocreau

Computational models typically assume that operations are applied in a fixed sequential order.In recent years several works have looked at relaxing this assumption, considering computations without any fixed causal structure and showing that such "causally indefinite" computations can provide advantages in various tasks.Recently, the quantum query complexity of Boolean functions has been used as a tool to probe their computational power in a standard complexity theoretic framework, but no separation in exact query complexity has thus-far been found.In this paper, we investigate this problem starting with the simpler and fully classical notion of deterministic query complexity of Boolean functions, and using classical-deterministic processes -which may exhibit causal indefiniteness -as a generalised computational framework.We first show that the standard polynomial and certificate lower bounds of deterministic query complexity also hold in such generalised models.Then, we formulate a Boolean function for which causal indefiniteness permits a reduction in query complexity and show that this advantage can be amplified into a polynomial separation.Finally, with the insights gained in the classical-deterministic setting, we give a Boolean function whose quantum query complexity is reduced by causally indefinite computations.

arXiv:2506.05187•Electronic Proceedings in Theoretical Computer Science•Aug 19, 2025•0 citations

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•55 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

Comparing the quantum switch and its simulations with energetically constrained operations

Marco Fellous-Asiani, Raphaël Mothe, Léa Bresque +5 more

Quantum mechanics allows processes to be superposed, leading to a genuinely quantum lack of causal structure. For example, the process known as the quantum switch applies two operations $\mathcal{A}$ and $\mathcal{B}$ in a superposition of the two possible orders, $\mathcal{A}$ before $\mathcal{B}$ and $\mathcal{B}$ before $\mathcal{A}$. Experimental implementations of the quantum switch have been challenged by some on the grounds that the operations $\mathcal{A}$ and $\mathcal{B}$ were implemented more than once, thereby simulating indefinite causal order rather than actually implementing it. Motivated by this debate, we consider a situation in which the quantum operations are physically described by a light-matter interaction model. While for our model the two processes are indistinguishable in the infinite-energy regime, restricting the energy available for the implementation of the operations introduces imperfections, which allow one to distinguish processes using different numbers of operations. We consider such an energetically constrained scenario and compare the quantum switch to one of its natural simulations, where each operation is implemented twice. Considering a commuting-versus-anticommuting unitary discrimination task, we find that within our model the quantum switch performs better, for some fixed amount of energy, than its simulation. In addition to the known computational or communication advantages of causal superpositions, our work raises questions about their potential energetic advantages.

arXiv:2208.01952•Physical Review Research•May 19, 2023•13 citations

Experimental Quantum Switching for Exponentially Superior Quantum Communication Complexity

Kejin Wei, Nora Tischler, Si-Ran Zhao +13 more

Finding exponential separation between quantum and classical information tasks is like striking gold in quantum information research. Such an advantage is believed to hold for quantum computing but is proven for quantum communication complexity. Recently, a novel quantum resource called the quantum switch-which creates a coherent superposition of the causal order of events, known as quantum causality-has been harnessed theoretically in a new protocol providing provable exponential separation. We experimentally demonstrate such an advantage by realizing a superposition of communication directions for a two-party distributed computation. Our photonic demonstration employs d-dimensional quantum systems, qudits, up to d=2^{13} dimensions and demonstrates a communication complexity advantage, requiring less than (0.696±0.006) times the communication of any causally ordered protocol. These results elucidate the crucial role of the coherence of communication direction in achieving the exponential separation for the one-way processing task, and open a new path for experimentally exploring the fundamentals and applications of advanced features of indefinite causal structures.

arXiv:1810.10238•Physical Review Letters•Mar 28, 2019•129 citations
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 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
Computational models typically assume that operations are applied in a fixed sequential order.In recent years several works have looked at relaxing this assumption, considering computations without any fixed causal structure and showing that such "causally indefinite" computations can provide advantages in various tasks.Recently, the quantum query complexity of Boolean functions has been used as a tool to probe their computational power in a standard complexity theoretic framework, but no separation in exact query complexity has thus-far been found.In this paper, we investigate this problem starting with the simpler and fully classical notion of deterministic query complexity of Boolean functions, and using classical-deterministic processes -which may exhibit causal indefiniteness -as a generalised computational framework.We first show that the standard polynomial and certificate lower bounds of deterministic query complexity also hold in such generalised models.Then, we formulate a Boolean function for which causal indefiniteness permits a reduction in query complexity and show that this advantage can be amplified into a polynomial separation.Finally, with the insights gained in the classical-deterministic setting, we give a Boolean function whose quantum query complexity is reduced by causally indefinite computations.
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.
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 mechanics allows processes to be superposed, leading to a genuinely quantum lack of causal structure. For example, the process known as the quantum switch applies two operations A\mathcal{A}A and B\mathcal{B}B in a superposition of the two possible orders, A\mathcal{A}A before B\mathcal{B}B and B\mathcal{B}B before A\mathcal{A}A. Experimental implementations of the quantum switch have been challenged by some on the grounds that the operations A\mathcal{A}A and B\mathcal{B}B were implemented more than once, thereby simulating indefinite causal order rather than actually implementing it. Motivated by this debate, we consider a situation in which the quantum operations are physically described by a light-matter interaction model. While for our model the two processes are indistinguishable in the infinite-energy regime, restricting the energy available for the implementation of the operations introduces imperfections, which allow one to distinguish processes using different numbers of operations. We consider such an energetically constrained scenario and compare the quantum switch to one of its natural simulations, where each operation is implemented twice. Considering a commuting-versus-anticommuting unitary discrimination task, we find that within our model the quantum switch performs better, for some fixed amount of energy, than its simulation. In addition to the known computational or communication advantages of causal superpositions, our work raises questions about their potential energetic advantages.
Finding exponential separation between quantum and classical information tasks is like striking gold in quantum information research. Such an advantage is believed to hold for quantum computing but is proven for quantum communication complexity. Recently, a novel quantum resource called the quantum switch-which creates a coherent superposition of the causal order of events, known as quantum causality-has been harnessed theoretically in a new protocol providing provable exponential separation. We experimentally demonstrate such an advantage by realizing a superposition of communication directions for a two-party distributed computation. Our photonic demonstration employs d-dimensional quantum systems, qudits, up to d=2^{13} dimensions and demonstrates a communication complexity advantage, requiring less than (0.696±0.006) times the communication of any causally ordered protocol. These results elucidate the crucial role of the coherence of communication direction in achieving the exponential separation for the one-way processing task, and open a new path for experimentally exploring the fundamentals and applications of advanced features of indefinite causal structures.