Computational advantage from quantum-controlled ordering of gates

Araujo, Mateus, Costa, Fabio and Brukner, Caslav (2014) Computational advantage from quantum-controlled ordering of gates. Physical Review Letters, 113 25: 250402-1-250402-5. doi:10.1103/PhysRevLett.113.250402

Attached Files (Some files may be inaccessible until you login with your UQ eSpace credentials)
Name Description MIMEType Size Downloads
UQ379542_OA.pdf Full text (open access) application/pdf 146.40KB 0

Author Araujo, Mateus
Costa, Fabio
Brukner, Caslav
Title Computational advantage from quantum-controlled ordering of gates
Journal name Physical Review Letters   Check publisher's open access policy
ISSN 1079-7114
Publication date 2014-12-18
Year available 2014
Sub-type Article (original research)
DOI 10.1103/PhysRevLett.113.250402
Open Access Status File (Publisher version)
Volume 113
Issue 25
Start page 250402-1
End page 250402-5
Total pages 5
Place of publication College Park, MD, United States
Publisher American Physical Society
Language eng
Formatted 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.
Keyword Physics, Multidisciplinary
Q-Index Code C1
Q-Index Status Provisional Code
Grant ID W1210
Institutional Status Non-UQ

Document type: Journal Article
Sub-type: Article (original research)
Collection: School of Mathematics and Physics
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 40 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 38 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Fri, 12 Feb 2016, 21:30:57 EST by System User on behalf of Learning and Research Services (UQ Library)