Computational advantage from quantum-controlled ordering of gates

Author(s): M. Araújo, F. M. Costa, Č. Brukner

Journal: Phys. Rev. Lett

Volume: 113

Page(s): 250402

Year: 2014

DOI Number: 10.1103/PhysRevLett.113.250402

Link: Link to publication


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(n2) queries. Furthermore, we conjecture that solving this problem in a classical computer takes exponential time, which may be of independent interest.


Brukner Group Brukner Group