Reassessing the computational advantage of quantum-controlled ordering of gates

Abstract

Research on indefinite causal structures is a rapidly evolving field that has a potential not only to make a radical revision of the classical understanding of space-time but also to achieve enhanced functionalities of quantum information processing. For example, it is known that indefinite causal structures provide exponential advantage in communication complexity when compared to causal protocols. In quantum computation, such structures can decide whether two unitary gates commute or anticommute with a single call to each gate, which is impossible with conventional (causal) quantum algorithms. A generalization of this effect to $n$ unitary gates, originally introduced in M. Araújo et al., Phys. Rev. Lett. 113, 250402 (2014) and often called Fourier promise problem (FPP), can be solved with the quantum-$n$-switch and a single call to each gate, while the best known causal algorithm so far calls $O(n^2)$ gates. In this work, we show that this advantage is smaller than expected. In fact, we present a causal algorithm that solves the only known specific FPP with $O(n\log (n))$ queries and a causal algorithm that solves every FPP with $O(n\sqrt{n})$ queries. Besides the interest in such algorithms on their own, our results limit the expected advantage of indefinite causal structures for these problems.

arXiv comment17 pages main body, 7 pages appendices and 13 figures

References in corpus (21)

• 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
• Adding control to arbitrary unknown quantum operations
• Experimental transmission of quantum information using a superposition of causal orders
• Experimental Quantum Switching for Exponentially Superior Quantum Communication Complexity
• Quantum circuits cannot control unknown operations
• Quantum computation with programmable connections between gates
• Computational advantage from quantum superposition of multiple temporal orders of photonic gates
• Communication through quantum-controlled noise
• Calculating Unknown Eigenvalues with a Quantum Algorithm
• Quantum computation with indefinite causal structures
• Quantum communication in a superposition of causal orders
• Computational tameness of classical non-causal models
• Quantum Circuits for the Unitary Permutation Problem

Cited by in corpus (11)

• Experimentally feasible computational advantage from quantum superposition of gate orders
• Experimental entanglement of temporal order
• Experimental Aspects of Indefinite Causal Order in Quantum Mechanics
• Unlimited non-causal correlations and their relation to non-locality
• Experimentally demonstrating indefinite causal order algorithms to solve the generalized Deutsch's problem
• Practical computational advantage from the quantum switch on a generalized family of promise problems
• Admissible Causal Structures and Correlations
• Quantum Supermaps are Characterized by Locality
• No-signalling constrains quantum computation with indefinite causal structure
• Coherent control of the causal order of entanglement distillation
• Knot invariants and indefinite causal order