Send to

Choose Destination
Phys Rev Lett. 2014 Dec 19;113(25):250402. Epub 2014 Dec 18.

Computational advantage from quantum-controlled ordering of gates.

Author information

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.


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.

Supplemental Content

Full text links

Icon for American Physical Society
Loading ...
Support Center