Computational Advantage from Quantum-Controlled Ordering of Gates

Author(s)

Mateus Araújo, Fabio Michele Costa, Caslav Brukner

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(n2)

queries. Furthermore, we conjecture that solving this problem in a

classical computer takes exponential time, which may be of independent

interest.

Organisation(s)

Quantum Optics, Quantum Nanophysics and Quantum Information

External organisation(s)

Österreichische Akademie der Wissenschaften (ÖAW)

Journal

Physical Review Letters

Volume

113

No. of pages

ISSN

0031-9007

DOI

https://doi.org/10.1103/PhysRevLett.113.250402

Publication date

12-2014

Peer reviewed

Yes

Austrian Fields of Science 2012

103025 Quantum mechanics, 103036 Theoretical physics

Keywords

ASJC Scopus subject areas

General Physics and Astronomy

Portal url