Computational Advantage from Quantum-Controlled Ordering of Gates

TLDR

Quantum computation is usually performed with gates in a fixed order, but allowing a quantum‑controlled ordering enables transformations on blackbox gates that are impossible with fixed‑order circuits. The authors aim to show that quantum‑controlled gate ordering is physically realizable by proposing an interferometric setup. They propose an interferometric setup that uses a control quantum system to switch the order of gates, relaxing the fixed‑order assumption. They show that this control reduces query complexity from O(n²) to O(n) for a proposed problem, and conjecture that the problem is classically exponential.

Abstract

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.