Computational Advantage from a Quantum Superposition of Qubit Gate Orders
- 10 June 2022
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review Letters
- Vol. 128 (23) , 230503
Abstract
In an ordinary quantum algorithm the gates are applied in a fixed order on the systems. The introduction of indefinite causal structures allows us to relax this constraint and control the order of the gates with an additional quantum state. It is known that this quantum-controlled ordering of gates can reduce the query complexity in deciding a property of black-box unitaries with respect to the best algorithm in which the gates are applied in a fixed order. However, all tasks explicitly found so far require unitaries that either act on unbounded dimensional quantum systems in the asymptotic limit (the limiting case of a large number of black-box gates) or act on qubits, but then involve only a few unitaries. Here we introduce tasks (i) for which there is a provable computational advantage of a quantum-controlled ordering of gates in the asymptotic case and (ii) that require only qubit gates and are therefore suitable to demonstrate this advantage experimentally. We study their solutions with the quantum -switch and within the quantum circuit model and find that while the -switch requires to call each gate only once, a causal algorithm has to call at least gates. Furthermore, the best known solution with a fixed gate ordering calls gates.
Keywords
All Related Versions
Funding Information
- Austrian Science Fund (I-2906)
- John Templeton Foundation (61466)
- Foundational Questions Institute
This publication has 27 references indexed in Scilit:
- Experimental verification of an indefinite causal orderScience Advances, 2017
- Exponential Communication Complexity Advantage from Quantum Superposition of the Direction of CommunicationPhysical Review Letters, 2016
- Experimental superposition of orders of quantum gatesNature Communications, 2015
- Quantum Circuits for the Unitary Permutation Problem2015
- Computational Advantage from Quantum-Controlled Ordering of GatesPhysical Review Letters, 2014
- Scalar, spinor, and photon fields under relativistic cavity motionPhysical Review D, 2013
- Quantum computations without definite causal structurePhysical Review A, 2013
- Perfect discrimination of no-signalling channels via quantum superposition of causal structuresPhysical Review A, 2012
- Quantum computation with programmable connections between gatesPhysics Letters A, 2012
- Quantum correlations with no causal orderNature Communications, 2012