title: Computational advantage from quantum-controlled ordering of gates.
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.
authors.affiliation: Faculty of Physics, University of Vienna, Boltzmanngasse 5, 1090 Vienna, Austria and Institute for Quantum Optics and Quantum Information (IQOQI), Austrian Academy of Sciences, Boltzmanngasse 3, 1090 Vienna, Austria.
authors.forename: Mateus
authors.initials: M
authors.lastname: Araújo
authors.affiliation: Faculty of Physics, University of Vienna, Boltzmanngasse 5, 1090 Vienna, Austria and Institute for Quantum Optics and Quantum Information (IQOQI), Austrian Academy of Sciences, Boltzmanngasse 3, 1090 Vienna, Austria.
authors.forename: Fabio
authors.initials: F
authors.lastname: Costa
authors.affiliation: Faculty of Physics, University of Vienna, Boltzmanngasse 5, 1090 Vienna, Austria and Institute for Quantum Optics and Quantum Information (IQOQI), Austrian Academy of Sciences, Boltzmanngasse 3, 1090 Vienna, Austria.
authors.forename: Časlav
authors.initials: Č
authors.lastname: Brukner