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

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

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

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•6 citations

The Quantum Fourier Transform for Continuous Variables

Gianfranco Cariolaro, Edi Ruffa, Amir Mohammad Yaghoobianzadeh +1 more

The quantum Fourier transform for discrete variable (dvQFT) is an efficient algorithm for several applications. It is usually considered for the processing of quantum bits (qubits) and its efficient implementation is obtained with two elementary components: the Hadamard gate and the controlled--phase gate. In this paper, the quantum Fourier transform operating with continuous variables (cvQFT) is considered. Thus, the environment becomes the Hilbert space, where the natural definition of the cvQFT will be related to rotation operators, which in the $N$--mode are completely specified by unitary matrices of order $N$. Then the cvQFT is defined as the rotation operator whose rotation matrix is given by the discrete Fourier transform (DFT) matrix. For the implementation of rotation operators with primitive components (single--mode rotations and beam splitters), we follow the well known Murnaghan procedure, with appropriate modifications. Moreover, algorithms related to the fast Fourier transform (FFT) are applied to reduce drastically the implementation complexity. The final part is concerned with the application of the cvQFT to general Gaussian states. In particular, we show that cvQFT has the simple effect of transforming the displacement vector by a one-dimensional DFT, the squeeze matrix by a two-dimensional DFT, and the rotation matrix by a Fourier-like similarity transform.

quant-pharXiv:2512.12771•Dec 16, 2025•0 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.
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.
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.
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.
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.
The quantum Fourier transform for discrete variable (dvQFT) is an efficient algorithm for several applications. It is usually considered for the processing of quantum bits (qubits) and its efficient implementation is obtained with two elementary components: the Hadamard gate and the controlled--phase gate. In this paper, the quantum Fourier transform operating with continuous variables (cvQFT) is considered. Thus, the environment becomes the Hilbert space, where the natural definition of the cvQFT will be related to rotation operators, which in the NNN--mode are completely specified by unitary matrices of order NNN. Then the cvQFT is defined as the rotation operator whose rotation matrix is given by the discrete Fourier transform (DFT) matrix. For the implementation of rotation operators with primitive components (single--mode rotations and beam splitters), we follow the well known Murnaghan procedure, with appropriate modifications. Moreover, algorithms related to the fast Fourier transform (FFT) are applied to reduce drastically the implementation complexity. The final part is concerned with the application of the cvQFT to general Gaussian states. In particular, we show that cvQFT has the simple effect of transforming the displacement vector by a one-dimensional DFT, the squeeze matrix by a two-dimensional DFT, and the rotation matrix by a Fourier-like similarity transform.