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

Universal quantum computation via superposed orders of single-qubit gates

Kyrylo Simonov, Marcello Caleffi, Jessica Illiano, Jacquiline Romero, Angela Sara Cacciapuoti

Published Dec 19, 2025• 7 citations
arXivHTMLPDF

Abstract

Superposed orders of quantum channels have already been proved—both theoretically and experimentally—to enable unparalleled opportunities in the quantum communication domain. Superposition of orders can be exploited within the quantum computing domain as well, by relaxing the (traditional) assumption underlying quantum computation about applying gates in a well-defined causal order. In this context, we address a fundamental question arising with quantum computing: Whether superposed orders of single-qubit gates can enable universal quantum computation. As shown in this paper, the answer to this key question is a definitive “yes.” Indeed, we prove that any two-qubit controlled quantum gate can be realized, including the so-called Barenco gate that alone enables universal quantum computation.

DOI
10.1103/6xwr-9b4y

Related papers

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

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 power of single qubit discrete-time quantum walk

Shivani Singh, Prateek Chawla, Anupam Sarkar +1 more

Abstract Quantum walk has been regarded as a primitive to universal quantum computation. By using the operations required to describe the single particle discrete-time quantum walk on a position space we demonstrate the realization of the universal set of gates on two-and three-qubit system. The idea is to reap the effective Hilbert space of the single qubit and the position space on which it evolves in superposition of position space in order to realize multi-qubit states and universal set of quantum gates on them. Realization of many non-trivial gates in the form of engineering arbitrary states is simpler in the proposed quantum walk model when compared to the circuit based model of computation. We will also discuss the scalability of the model and some propositions for using lesser number of qubits in realizing larger qubit systems.

•Feb 23, 2021•3 citations

Practical implementation of arbitrary nonlocal controlled-unitary gate via indefinite causal order

Wen-Qiang Liu, Zi-Han Zheng, Zhang-Qi Yin +1 more

Quantum gate teleportation enables the implementation of nonlocal quantum operations without direct interactions between distant nodes. We propose an efficient protocol for implementing arbitrary controlled-unitary (CU) gates acting on two spatially separated parties via indefinite causal order (ICO). By establishing a maximally entanglement between two remote nodes and coherently superposing orders of single-qubit gates, our protocol circumvents the drawback of complex local two-qubit operations. This ICO-based approach enables full programmability of CU gates by adjusting the inherent single-qubit operations, offering advantages over conventional fixed causal-order methods in terms of reduced circuit complexity and improved experimental flexibility. Furthermore, we develop an optical construction to implement the polarization CU gate using a stable and reciprocal Sagnac interferometer. Our work establishes a practical framework for scalable distributed quantum computation with flexible operations.

quant-pharXiv:2603.08073•New Journal of Physics•Mar 10, 2026•2 citations

Universal quantum computation via quantum controlled classical operations

Sebastian Horvat, Xiaoqin Gao, Borivoje Dakić

Abstract A universal set of gates for (classical or quantum) computation is a set of gates that can be used to approximate any other operation. It is well known that a universal set for classical computation augmented with the Hadamard gate results in universal quantum computing. Motivated by the latter, we pose the following question: can one perform universal quantum computation by supplementing a set of classical gates with a quantum control, and a set of quantum gates operating solely on the latter? In this work we provide an affirmative answer to this question by considering a computational model that consists of 2n target bits together with a set of classical gates controlled by log (2n + 1) ancillary qubits. We show that this model is equivalent to a quantum computer operating on n qubits. Furthermore, we show that even a primitive computer that is capable of implementing only SWAP gates, can be lifted to universal quantum computing, if aided with an appropriate quantum control of logarithmic size. Our results thus exemplify the information processing power brought forth by the quantum control system.

arXiv:2104.06424•Journal of Physics A Mathematical and Theoretical•Dec 15, 2021•3 citations

Decompositions of general quantum gates

Mikko Möttönen, Juha J. Vartiainen

Quantum algorithms may be described by sequences of unitary transformations called quantum gates and measurements applied to the quantum register of n quantum bits, qubits. A collection of quantum gates is called universal if it can be used to construct any n-qubit gate. In 1995, the universality of the set of one-qubit gates and controlled NOT gate was shown by Barenco et al. using QR decomposition of unitary matrices. Almost ten years later the decomposition was improved to include essentially fewer elementary gates. In addition, the cosine-sine matrix decomposition was applied to efficiently implement decompositions of general quantum gates. In this chapter, we review the different types of general gate decompositions and slightly improve the best known gate count for the controlled NOT gates to (23/48)4^n in the leading order. In physical realizations, the interaction strength between the qubits can decrease strongly as a function of their distance. Therefore, we also discuss decompositions with the restriction to nearest-neighbor interactions in a linear chain of qubits.

arXiv:quant-ph/0504100•Apr 14, 2005•86 citations
Superposed orders of quantum channels have already been proved—both theoretically and experimentally—to enable unparalleled opportunities in the quantum communication domain. Superposition of orders can be exploited within the quantum computing domain as well, by relaxing the (traditional) assumption underlying quantum computation about applying gates in a well-defined causal order. In this context, we address a fundamental question arising with quantum computing: Whether superposed orders of single-qubit gates can enable universal quantum computation. As shown in this paper, the answer to this key question is a definitive “yes.” Indeed, we prove that any two-qubit controlled quantum gate can be realized, including the so-called Barenco gate that alone enables universal quantum computation.
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.
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.
Abstract Quantum walk has been regarded as a primitive to universal quantum computation. By using the operations required to describe the single particle discrete-time quantum walk on a position space we demonstrate the realization of the universal set of gates on two-and three-qubit system. The idea is to reap the effective Hilbert space of the single qubit and the position space on which it evolves in superposition of position space in order to realize multi-qubit states and universal set of quantum gates on them. Realization of many non-trivial gates in the form of engineering arbitrary states is simpler in the proposed quantum walk model when compared to the circuit based model of computation. We will also discuss the scalability of the model and some propositions for using lesser number of qubits in realizing larger qubit systems.
Quantum gate teleportation enables the implementation of nonlocal quantum operations without direct interactions between distant nodes. We propose an efficient protocol for implementing arbitrary controlled-unitary (CU) gates acting on two spatially separated parties via indefinite causal order (ICO). By establishing a maximally entanglement between two remote nodes and coherently superposing orders of single-qubit gates, our protocol circumvents the drawback of complex local two-qubit operations. This ICO-based approach enables full programmability of CU gates by adjusting the inherent single-qubit operations, offering advantages over conventional fixed causal-order methods in terms of reduced circuit complexity and improved experimental flexibility. Furthermore, we develop an optical construction to implement the polarization CU gate using a stable and reciprocal Sagnac interferometer. Our work establishes a practical framework for scalable distributed quantum computation with flexible operations.
Abstract A universal set of gates for (classical or quantum) computation is a set of gates that can be used to approximate any other operation. It is well known that a universal set for classical computation augmented with the Hadamard gate results in universal quantum computing. Motivated by the latter, we pose the following question: can one perform universal quantum computation by supplementing a set of classical gates with a quantum control, and a set of quantum gates operating solely on the latter? In this work we provide an affirmative answer to this question by considering a computational model that consists of 2n target bits together with a set of classical gates controlled by log (2n + 1) ancillary qubits. We show that this model is equivalent to a quantum computer operating on n qubits. Furthermore, we show that even a primitive computer that is capable of implementing only SWAP gates, can be lifted to universal quantum computing, if aided with an appropriate quantum control of logarithmic size. Our results thus exemplify the information processing power brought forth by the quantum control system.
Quantum algorithms may be described by sequences of unitary transformations called quantum gates and measurements applied to the quantum register of n quantum bits, qubits. A collection of quantum gates is called universal if it can be used to construct any n-qubit gate. In 1995, the universality of the set of one-qubit gates and controlled NOT gate was shown by Barenco et al. using QR decomposition of unitary matrices. Almost ten years later the decomposition was improved to include essentially fewer elementary gates. In addition, the cosine-sine matrix decomposition was applied to efficiently implement decompositions of general quantum gates. In this chapter, we review the different types of general gate decompositions and slightly improve the best known gate count for the controlled NOT gates to (23/48)4^n in the leading order. In physical realizations, the interaction strength between the qubits can decrease strongly as a function of their distance. Therefore, we also discuss decompositions with the restriction to nearest-neighbor interactions in a linear chain of qubits.