Experimentally feasible computational advantage from quantum superposition of gate orders

Abstract

In an ordinary quantum algorithm the gates are applied in a fixed order on the systems. The introduction of indefinite causal structures allows 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 (1) for which there is a provable computational advantage of a quantum-controlled ordering of gates in the asymptotic case and (2) that require only qubit gates and are therefore suitable to demonstrate this advantage experimentally. We study their solutions with the quantum-$n$-switch and within the quantum circuit model and find that while the $n$-switch requires to call each gate only once, a causal algorithm has to call at least $2n-1$ gates. Furthermore, the best known solution with a fixed gate ordering calls $O(n{\log }_2(n))$ gates.

arXiv comment5 pages main body, 5 pages appendices and 5 figures

References in corpus (26)

• Quantum correlations with no causal order
• Quantum computations without definite causal structure
• Experimental Superposition of Orders of Quantum Gates
• Computational advantage from quantum-controlled ordering of gates
• Experimental Verification of an Indefinite Causal Order
• Enhanced communication with the assistance of indefinite causal order
• Perfect discrimination of no-signalling channels via quantum superposition of causal structures
• Indefinite Causal Order in a Quantum Switch
• Exponential Communication Complexity Advantage from Quantum Superposition of the Direction of Communication
• Experimental transmission of quantum information using a superposition of causal orders
• Experimental Quantum Switching for Exponentially Superior Quantum Communication Complexity
• Bell's Theorem for Temporal Order
• Indefinite causal order enables perfect quantum communication with zero capacity channels
• Quantum computation with programmable connections between gates
• Experimental Quantum Communication Enhancement by Superposing Trajectories
• Communication through coherent control of quantum channels
• Communicating via ignorance: Increasing communication capacity via superposition of order
• Computational advantage from quantum superposition of multiple temporal orders of photonic gates
• Communication through quantum-controlled noise
• Scalar, spinor, and photon fields under relativistic cavity motion
• Strict hierarchy between parallel, sequential, and indefinite-causal-order strategies for channel discrimination
• Quantum computation with indefinite causal structures
• Experimental entanglement of temporal order
• Computational tameness of classical non-causal models
• Quantum Circuits for the Unitary Permutation Problem
• Reassessing the computational advantage of quantum-controlled ordering of gates

Cited by in corpus (22)

• Experimental Aspects of Indefinite Causal Order in Quantum Mechanics
• Semi-device-independent certification of indefinite causal order in a photonic quantum switch
• Higher-order Process Matrix Tomography of a passively-stable Quantum SWITCH
• Demonstration of a quantum SWITCH in a Sagnac configuration
• Experimental Validation of Enhanced Information Capacity by Quantum Switch in Accordance with Thermodynamic Laws
• Experimentally demonstrating indefinite causal order algorithms to solve the generalized Deutsch's problem
• Memory in quantum processes with indefinite time direction and causal order
• Practical computational advantage from the quantum switch on a generalized family of promise problems
• Activation of thermal states by coherently controlled thermalization processes
• Admissible Causal Structures and Correlations
• Coherent control of the causal order of entanglement distillation
• Quantum Query Complexity of Boolean Functions under Indefinite Causal Order
• Expressibility, entangling power and quantum average causal effect for causally indefinite circuits
• Simulating the quantum switch with quantum circuits is computationally hard
• Quantum switch as a thermodynamic resource in the context of passive states
• Sequential device-independent certification of indefinite causal order
• Enhancement of non-Stabilizerness within Indefinite Causal Order
• Phase-sensitive superposition of quantum states
• Entropic uncertainty under indefinite causal order and input-output direction
• No quantum advantage for violating fixed-order inequalities?
• Knot invariants and indefinite causal order
• Correlations in a quantum switch-based heat engine with measurements: A proof-of-principle demonstration