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:2207.12997 · Quantum

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

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

Published Mar 9, 2023• 11 citations
arXivHTMLPDF

Abstract

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.

DOI
10.22331/q-2023-03-09-945

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

Reassessing the computational advantage of quantum-controlled ordering of gates

Martin J. Renner, Časlav Brukner

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.

arXiv:2102.11293•Physical Review Research•Oct 6, 2021•17 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•330 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

Experimental computational advantage from superposition of multiple temporal orders of quantum gates

Márcio M. Taddei, Jaime Cariñe, Daniel Martínez +9 more

Models for quantum computation with circuit connections subject to the quantum superposition principle have been recently proposed. There, a control quantum system can coherently determine the order in which a target quantum system undergoes $N$ gate operations. This process, known as the quantum $N$-switch, is a resource for several information-processing tasks. In particular, it provides a computational advantage -- over fixed-gate-order quantum circuits -- for phase-estimation problems involving $N$ unknown unitary gates. However, the corresponding algorithm requires an experimentally unfeasible target-system dimension (super)exponential in $N$. Here, we introduce a promise problem for which the quantum $N$-switch gives an equivalent computational speed-up with target-system dimension as small as 2 regardless of $N$. We use state-of-the-art multi-core optical-fiber technology to experimentally demonstrate the quantum $N$-switch with $N=4$ gates acting on a photonic-polarization qubit. This is the first observation of a quantum superposition of more than $N=2$ temporal orders, demonstrating its usefulness for efficient phase-estimation.

arXiv:2002.07817•Nov 10, 2020•7 citations
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.
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.
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.
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 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.
Models for quantum computation with circuit connections subject to the quantum superposition principle have been recently proposed. There, a control quantum system can coherently determine the order in which a target quantum system undergoes NNN gate operations. This process, known as the quantum NNN-switch, is a resource for several information-processing tasks. In particular, it provides a computational advantage -- over fixed-gate-order quantum circuits -- for phase-estimation problems involving NNN unknown unitary gates. However, the corresponding algorithm requires an experimentally unfeasible target-system dimension (super)exponential in NNN. Here, we introduce a promise problem for which the quantum NNN-switch gives an equivalent computational speed-up with target-system dimension as small as 2 regardless of NNN. We use state-of-the-art multi-core optical-fiber technology to experimentally demonstrate the quantum NNN-switch with N=4N=4N=4 gates acting on a photonic-polarization qubit. This is the first observation of a quantum superposition of more than N=2N=2N=2 temporal orders, demonstrating its usefulness for efficient phase-estimation.