Can I read Computational Advantage from Quantum-controlled Ordering of Gates on EtoBox?

Computational Advantage from Quantum-controlled Ordering of Gates by Araújo, Mateus; Costa, Fabio; Brukner, Časlav is a scholarly article available to read on EtoBox.

What is Computational Advantage from Quantum-controlled Ordering of Gates about?

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 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.

Author

Araújo, Mateus; Costa, Fabio; Brukner, Časlav

Published

2014

Language

EN