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:2002.07817

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

Márcio M. Taddei, Jaime Cariñe, Daniel Martínez, Tania García, Nayda Guerrero, Alastair A. Abbott, Mateus Araújo, Cyril Branciard, Esteban S. Gómez, Stephen Patrick Walborn, Leandro Aolita, G. Lima

Published Nov 10, 2020• 6 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/prxquantum.2.010320

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

Computational Advantage from the Quantum Superposition of Multiple Temporal Orders of Photonic Gates

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

Playing with causal orders leads to quadratic speed-up: An efficient algorithm is introduced and implemented in a scalable fiber-optic based experiment that achieves, for the first time, a quantum 4-switch gate.

PRX Quantum•Feb 8, 2021•80 citations

Experimental superposition of orders of quantum gates

Lorenzo M. Procopio, Amir Moqanaki, Mateus Araújo +7 more

Quantum computers achieve a speed-up by placing quantum bits (qubits) in superpositions of different states. However, it has recently been appreciated that quantum mechanics also allows one to 'superimpose different operations'. Furthermore, it has been shown that using a qubit to coherently control the gate order allows one to accomplish a task--determining if two gates commute or anti-commute--with fewer gate uses than any known quantum algorithm. Here we experimentally demonstrate this advantage, in a photonic context, using a second qubit to control the order in which two gates are applied to a first qubit. We create the required superposition of gate orders by using additional degrees of freedom of the photons encoding our qubits. The new resource we exploit can be interpreted as a superposition of causal orders, and could allow quantum algorithms to be implemented with an efficiency unlikely to be achieved on a fixed-gate-order quantum computer.

arXiv:1412.4006•Nature Communications•Aug 7, 2015•314 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

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

Decrease in query complexity for quantum computers with superposition of circuits

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 (in particular, linear optical) 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 using $O(n)$ blackbox queries, whereas the best known quantum algorithm with fixed order between the gates requires $O(n^2)$ queries.

•Jan 31, 2014•8 citations
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.
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.
Quantum computers achieve a speed-up by placing quantum bits (qubits) in superpositions of different states. However, it has recently been appreciated that quantum mechanics also allows one to 'superimpose different operations'. Furthermore, it has been shown that using a qubit to coherently control the gate order allows one to accomplish a task--determining if two gates commute or anti-commute--with fewer gate uses than any known quantum algorithm. Here we experimentally demonstrate this advantage, in a photonic context, using a second qubit to control the order in which two gates are applied to a first qubit. We create the required superposition of gate orders by using additional degrees of freedom of the photons encoding our qubits. The new resource we exploit can be interpreted as a superposition of causal orders, and could allow quantum algorithms to be implemented with an efficiency unlikely to be achieved on a fixed-gate-order quantum computer.
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.
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.
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 (in particular, linear optical) 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 using O(n)O(n)O(n) blackbox queries, whereas the best known quantum algorithm with fixed order between the gates requires O(n2)O(n^2)O(n2) queries.