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.

5 pages main body, 5 pages appendices and 5 figures

References in corpus (1)

• Experimental Verification of an Indefinite Causal Order

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