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:2102.11293 · Physical Review Research

Reassessing the computational advantage of quantum-controlled ordering of gates

Martin J. Renner, Časlav Brukner

Published Oct 6, 2021• 11 citations
arXivHTMLPDF

Abstract

Research on indefinite causal structures is a rapidly evolving field that has a potential not only to make a radical revision of the classical understanding of space-time but also to achieve enhanced functionalities of quantum information processing. For example, it is known that indefinite causal structures provide exponential advantage in communication complexity when compared to causal protocols. In quantum computation, such structures can decide whether two unitary gates commute or anticommute with a single call to each gate, which is impossible with conventional (causal) quantum algorithms. A generalization of this effect to $n$ unitary gates, originally introduced in Ara\'ujo et al. [Phys. Rev. Lett. 113, 250402 (2014)] and often called Fourier promise problem (FPP), can be solved with the quantum-$n$-switch and a single call to each gate, while the best known causal algorithm so far calls $O({n}^{2})$ gates. In this article, we show that this advantage is smaller than expected. In fact, we present a causal algorithm that solves the only known specific FPP with $O(nlog(n))$ queries and a causal algorithm that solves every FPP with $O(n\sqrt{n})$ queries. Besides the interest in such algorithms on their own, our results limit the expected advantage of indefinite causal structures for these problems.

DOI
10.1103/physrevresearch.3.043012

Related papers

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

Indefinite causal order towards continuous-variable quantum systems.

Jorge Escandón-Monardes

Indefinite causal order has attracted a growing attention during the last decade, with the quantum switch being its most prominent instance. The quantum switch has been implemented in several photonic experiments and has also provided computational advantages in several tasks. However, indefinite causal order on continuous-variable (CV) quantum systems has been barely studied. This thesis suggests that applications of indefinite causal order on CV quantum systems may offer broader advantages than using finite-dimensional quantum systems. We follow an exploratory approach comparing the performance of the quantum switch with high-dimensional and CV quantum systems in some applications to quantum computing and quantum metrology. In particular, we use Complex Hadamard matrices to introduce a generalised family of promise problems, which reduces to the known Fourier and Hadamard promise problems as limiting cases. We show that the quantum switch provides query advantage for both the continuous and discrete cases, and prove that a CV system is necessary for implementing the most general promise problem. In addition, we propose an estimation procedure for d-dimensional unitary transformations using the quantum switch. For d > 2, the unitary transformations close to the identity are estimated saturating the quantum Cram´ er-Rao bound. For d = 2, the estimation of all unitary transformations is also optimal with some prior information. We replace the unitary transformation by an arbitrary quantum channel and show that our procedure encodes the χ matrix of the channel in the output state of the control system. Although indefinite causal order does not offer metrological advantage in our proposal, it is worthy to note that an extension to the CV regime would require an infinite-dimensional control system. This inspires the introduction of the quantum switch with continuous control, which leads to new phenomena such as the accelerando/rallentando effect. We conclude that using CV systems enlarges the number of tasks benefited by indefinite causal order and exhibits new phenomena within the field.

•Apr 30, 2025•0 citations

What Can Be Computed with Indefinite Causal Structure?

Omri Shmueli

Can quantum computation become more powerful when operations do not need to follow a definite causal order? We study this question in the process matrix formalism of Oreshkov et al. (Nature Communications, 2012), which allows quantum operations to be connected without a fixed global order. In the computational model, a quantum circuit succinctly describes a process matrix, and the algorithm is given access to its generated channel, with computational cost measured by the size of the generating circuit. We give polynomial-time algorithms in two settings. First, general process matrix computation suffices to solve every problem in $\textbf{NP}$. The valid processes used by our algorithm satisfy the purification postulate of Araújo et al. (Quantum, 2017), and their generated channels are unitary, although their generating circuits are not. Second, requiring the process matrices themselves to be pure, we give a polynomial-time algorithm for unique-sink orientation, a general problem capturing several longstanding computational problems in optimization. Our unitary generators are constructed explicitly and efficiently. Assuming that unique-sink orientation has no quantum polynomial-time algorithm, our result shows that indefinite causal order can provide computational power beyond $\textbf{BQP}$ within the process matrix formalism, even while preserving unitarity.

quant-pharXiv:2610.40573•Oct 30, 2026•0 citations

Computational Advantage from Quantum-Controlled Ordering of Gates

Mateus Araújo, Fabio Costa, Časlav Brukner

It is usually assumed that a quantum computation is performed by applying gates in a specific order. One can relax this assumption by allowing a control quantum system to switch the order in which the gates are applied. This provides a more general kind of quantum computing that allows transformations on blackbox quantum gates that are impossible in a circuit with fixed order. Here we show that this model of quantum computing is physically realizable, by proposing an interferometric setup that can implement such a quantum control of the order between the gates. We show that this new resource provides a reduction in computational complexity: we propose a problem that can be solved by using O(n) blackbox queries, whereas the best known quantum algorithm with fixed order between the gates requires O(n^{2}) queries. Furthermore, we conjecture that solving this problem in a classical computer takes exponential time, which may be of independent interest.

arXiv:1401.8127•Physical Review Letters•Dec 18, 2014•295 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

Practical computational advantage from the quantum switch on a generalized family of promise problems

Jorge Escandón-Monardes, A. Delgado, Stephen Patrick Walborn

The quantum switch is a quantum computational primitive that provides computational advantage by applying operations in a superposition of orders. In particular, it can reduce the number of gate queries required for solving promise problems where the goal is to discriminate between a set of properties of a given set of unitary gates. In this work, we use Complex Hadamard matrices to introduce more general promise problems, which reduce to the known Fourier and Hadamard promise problems as limiting cases. Our generalization loosens the restrictions on the size of the matrices, number of gates and dimension of the quantum systems, providing more parameters to explore. In addition, it leads to the conclusion that a continuous variable system is necessary to implement the most general promise problem. In the finite dimensional case, the family of matrices is restricted to the so-called Butson-Hadamard type, and the complexity of the matrix enters as a constraint. We introduce the “query per gate'' parameter and use it to prove that the quantum switch provides computational advantage for both the continuous and discrete cases. Our results should inspire implementations of promise problems using the quantum switch where parameters and therefore experimental setups can be chosen much more freely.

arXiv:2207.12997•Quantum•Mar 9, 2023•8 citations
Research on indefinite causal structures is a rapidly evolving field that has a potential not only to make a radical revision of the classical understanding of space-time but also to achieve enhanced functionalities of quantum information processing. For example, it is known that indefinite causal structures provide exponential advantage in communication complexity when compared to causal protocols. In quantum computation, such structures can decide whether two unitary gates commute or anticommute with a single call to each gate, which is impossible with conventional (causal) quantum algorithms. A generalization of this effect to nnn unitary gates, originally introduced in Ara'ujo et al. [Phys. Rev. Lett. 113, 250402 (2014)] and often called Fourier promise problem (FPP), can be solved with the quantum-nnn-switch and a single call to each gate, while the best known causal algorithm so far calls O(n2)O({n}^{2})O(n2) gates. In this article, we show that this advantage is smaller than expected. In fact, we present a causal algorithm that solves the only known specific FPP with O(nlog(n))O(nlog(n))O(nlog(n)) queries and a causal algorithm that solves every FPP with O(nn)O(n\sqrt{n})O(nn​) queries. Besides the interest in such algorithms on their own, our results limit the expected advantage of indefinite causal structures for these problems.
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.
Indefinite causal order has attracted a growing attention during the last decade, with the quantum switch being its most prominent instance. The quantum switch has been implemented in several photonic experiments and has also provided computational advantages in several tasks. However, indefinite causal order on continuous-variable (CV) quantum systems has been barely studied. This thesis suggests that applications of indefinite causal order on CV quantum systems may offer broader advantages than using finite-dimensional quantum systems. We follow an exploratory approach comparing the performance of the quantum switch with high-dimensional and CV quantum systems in some applications to quantum computing and quantum metrology. In particular, we use Complex Hadamard matrices to introduce a generalised family of promise problems, which reduces to the known Fourier and Hadamard promise problems as limiting cases. We show that the quantum switch provides query advantage for both the continuous and discrete cases, and prove that a CV system is necessary for implementing the most general promise problem. In addition, we propose an estimation procedure for d-dimensional unitary transformations using the quantum switch. For d > 2, the unitary transformations close to the identity are estimated saturating the quantum Cram´ er-Rao bound. For d = 2, the estimation of all unitary transformations is also optimal with some prior information. We replace the unitary transformation by an arbitrary quantum channel and show that our procedure encodes the χ matrix of the channel in the output state of the control system. Although indefinite causal order does not offer metrological advantage in our proposal, it is worthy to note that an extension to the CV regime would require an infinite-dimensional control system. This inspires the introduction of the quantum switch with continuous control, which leads to new phenomena such as the accelerando/rallentando effect. We conclude that using CV systems enlarges the number of tasks benefited by indefinite causal order and exhibits new phenomena within the field.
Can quantum computation become more powerful when operations do not need to follow a definite causal order? We study this question in the process matrix formalism of Oreshkov et al. (Nature Communications, 2012), which allows quantum operations to be connected without a fixed global order. In the computational model, a quantum circuit succinctly describes a process matrix, and the algorithm is given access to its generated channel, with computational cost measured by the size of the generating circuit. We give polynomial-time algorithms in two settings. First, general process matrix computation suffices to solve every problem in NP\textbf{NP}NP. The valid processes used by our algorithm satisfy the purification postulate of Araújo et al. (Quantum, 2017), and their generated channels are unitary, although their generating circuits are not. Second, requiring the process matrices themselves to be pure, we give a polynomial-time algorithm for unique-sink orientation, a general problem capturing several longstanding computational problems in optimization. Our unitary generators are constructed explicitly and efficiently. Assuming that unique-sink orientation has no quantum polynomial-time algorithm, our result shows that indefinite causal order can provide computational power beyond BQP\textbf{BQP}BQP within the process matrix formalism, even while preserving unitarity.
It is usually assumed that a quantum computation is performed by applying gates in a specific order. One can relax this assumption by allowing a control quantum system to switch the order in which the gates are applied. This provides a more general kind of quantum computing that allows transformations on blackbox quantum gates that are impossible in a circuit with fixed order. Here we show that this model of quantum computing is physically realizable, by proposing an interferometric setup that can implement such a quantum control of the order between the gates. We show that this new resource provides a reduction in computational complexity: we propose a problem that can be solved by using O(n) blackbox queries, whereas the best known quantum algorithm with fixed order between the gates requires O(n^{2}) queries. Furthermore, we conjecture that solving this problem in a classical computer takes exponential time, which may be of independent interest.
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
The quantum switch is a quantum computational primitive that provides computational advantage by applying operations in a superposition of orders. In particular, it can reduce the number of gate queries required for solving promise problems where the goal is to discriminate between a set of properties of a given set of unitary gates. In this work, we use Complex Hadamard matrices to introduce more general promise problems, which reduce to the known Fourier and Hadamard promise problems as limiting cases. Our generalization loosens the restrictions on the size of the matrices, number of gates and dimension of the quantum systems, providing more parameters to explore. In addition, it leads to the conclusion that a continuous variable system is necessary to implement the most general promise problem. In the finite dimensional case, the family of matrices is restricted to the so-called Butson-Hadamard type, and the complexity of the matrix enters as a constraint. We introduce the “query per gate'' parameter and use it to prove that the quantum switch provides computational advantage for both the continuous and discrete cases. Our results should inspire implementations of promise problems using the quantum switch where parameters and therefore experimental setups can be chosen much more freely.