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.
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.
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(n2) queries.
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.
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.