Computational advantage from quantum-controlled ordering of gates

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 using $O(n)$ blackbox queries, whereas the best known quantum algorithm with fixed order between the gates requires $O(n^2)$ queries. Furthermore, we conjecture that solving this problem in a classical computer takes exponential time, which may be of independent interest.

4+5 pages, 2 figures. Corrected mistake in Appendix A

References in corpus (1)

• Adding control to arbitrary unknown quantum operations

Cited by in corpus (175)

• Experimental Superposition of Orders of Quantum Gates
• Experimental Verification of an Indefinite Causal Order
• Quantum causal modelling
• Indefinite Causal Order in a Quantum Switch
• Automated Search for new Quantum Experiments
• Exponential Communication Complexity Advantage from Quantum Superposition of the Direction of Communication
• Quantum common causes and quantum causal models
• Witnessing causal nonseparability
• Quantum information processing with space-division multiplexing optical fibres
• Measurement of many-body chaos using a quantum clock
• Quantum Metrology with Indefinite Causal Order
• Causal and causally separable processes
• Experimental Quantum Switching for Exponentially Superior Quantum Communication Complexity
• Quantum superposition of the order of parties as a communication resource
• Bell's Theorem for Temporal Order
• Quantum Refrigeration with Indefinite Causal Order
• Indefinite causal order enables perfect quantum communication with zero capacity channels
• The simplest causal inequalities and their violation
• Quantum Switch for the Quantum Internet: Noiseless Communications through Noisy Channels
• Experimental Quantum Communication Enhancement by Superposing Trajectories
• Communication through coherent control of quantum channels
• Reversing Unknown Quantum Transformations: Universal Quantum Circuit for Inverting General Unitary Operations
• Computational advantage from quantum superposition of multiple temporal orders of photonic gates
• Communication through quantum-controlled noise
• Time-delocalized quantum subsystems and operations: on the existence of processes with indefinite causal structure in quantum mechanics
• Strict hierarchy between parallel, sequential, and indefinite-causal-order strategies for channel discrimination
• Resource theories of communication
• Communication Enhancement Through Quantum Coherent Control of $N$ Channels in an Indefinite Causal-order Scenario
• Sending classical information via three noisy channels in superposition of causal orders
• Quantum circuits with classical versus quantum control of causal order
• A purification postulate for quantum mechanics with indefinite causal order
• Multipartite Causal Correlations: Polytopes and Inequalities
• Optimal quantum networks and one-shot entropies
• Cyclic Quantum Causal Models
• Experimental Test of Nonlocal Causality
• Can a quantum state over time resemble a quantum state at a single time?
• Experimentally feasible computational advantage from quantum superposition of gate orders
• Optimal Strategies of Quantum Metrology with a Strict Hierarchy
• Quantum Temporal Superposition: the case of QFT
• Using adaptiveness and causal superpositions against noise in quantum metrology
• Probabilistic exact universal quantum circuits for transforming unitary operations
• Quantum computation with indefinite causal structures
• Operational quantum theory without predefined time
• Quantum-coherent mixtures of causal relations
• Genuine quantum networks: superposed tasks and addressing
• Experiments on quantum causality
• Witnesses of causal nonseparability: an introduction and a few case studies
• On the definition and characterisation of multipartite causal (non)separability
• Experimental entanglement of temporal order
• Experimental Aspects of Indefinite Causal Order in Quantum Mechanics
• Dynamics of quantum causal structures
• How device-independent approaches change the meaning of physical theory
• Connecting processes with indefinite causal order and multi-time quantum states
• Computation in generalised probabilistic theories
• Unitary channel discrimination beyond group structures: Advantages of sequential and indefinite-causal-order strategies
• Thermal devices powered by generalized measurements with indefinite causal order
• Hierarchy in temporal quantum correlations
• Multi-dimensional entanglement generation with multi-core optical fibers
• Causal Boxes: Quantum Information-Processing Systems Closed under Composition
• Bounding quantum correlations with indefinite causal order
• Superposition of causal order enables perfect quantum teleportation with very noisy singlets
• Beyond Shannon Limits: Quantum Communications through Quantum Paths
• Quantification of quantum dynamics with input-output games
• Observer-dependent locality of quantum events
• Causal structure in the presence of sectorial constraints, with application to the quantum switch
• Indefinite causal order for quantum metrology with quantum thermal noise
• Semi-device-independent certification of indefinite causal order
• Indefinite causal structures for continuous-variable systems
• Complex conjugation supermap of unitary quantum maps and its universal implementation protocol
• Device-independent test of causal order and relations to fixed-points
• Semi-device-independent certification of indefinite causal order in a photonic quantum switch
• Success-or-Draw: A Strategy Allowing Repeat-Until-Success in Quantum Computation
• Bounds on the power of proofs and advice in general physical theories
• Higher-order Process Matrix Tomography of a passively-stable Quantum SWITCH
• Evading noise in multiparameter quantum metrology with indefinite causal order
• Composable security in relativistic quantum cryptography
• Consequences of preserving reversibility in quantum superchannels
• Quantum superpositions of "common-cause" and "direct-cause" causal structures
• Generating multi-partite entanglement from the quantum vacuum with a finite-lifetime mirror
• Demonstration of a quantum SWITCH in a Sagnac configuration
• Enhancing Quantum Computation via Superposition of Quantum Gates
• Computational tameness of classical non-causal models
• Superposed Quantum Error Mitigation
• Deterministic Generation of Multipartite Entanglement via Causal Activation in the Quantum Internet
• Process Products Need Qualification
• Reassessing the advantage of indefinite causal orders for quantum metrology
• Reassessing thermodynamic advantage from indefinite causal order
• Fully-Optimized Quantum Metrology: Framework, Tools, and Applications
• Simulating indefinite causal order with Rindler observers
• Indefinite Causal Orders from Superpositions in Time
• Reassessing the computational advantage of quantum-controlled ordering of gates
• Quantum steering beyond instrumental causal networks
• Experimental demonstration of input-output indefiniteness in a single quantum device
• Quantum superpositions of causal orders as an operational resource
• Quantum communication through devices with indefinite input-output direction
• Existence of processes violating causal inequalities on time-delocalised subsystems
• Self-testing mutually unbiased bases in higher dimensions with space-division multiplexing optical fiber technology
• Comparing the quantum switch and its simulations with energetically-constrained operations
• Non-causal computation
• Activating information backflow with the assistance of quantum SWITCH
• Semi-Device-Independent Certification of Causal Nonseparability with Trusted Quantum Inputs
• Causal games of work extraction with indefinite causal order
• Experimentally demonstrating indefinite causal order algorithms to solve the generalized Deutsch's problem
• Quantum switch in the gravity of Earth
• Classical communication through quantum causal structures
• Quantum switch instabilities with an open control
• Breaking the limits of purification: Postselection enhances heat-bath algorithmic cooling
• Improvement in quantum communication using quantum switch
• Quantum communication using a quantum switch of quantum switches
• Composition rules for quantum processes: a no-go theorem
• Memory in quantum processes with indefinite time direction and causal order
• Quantum networks boosted by entanglement with a control system
• Practical computational advantage from the quantum switch on a generalized family of promise problems
• Activation of thermal states by coherently controlled thermalization processes
• Quantum superposition of causal structures as a universal resource for local implementation of nonlocal quantum operations
• Quantum Metrology with Coherent Superposition of Two Different Coded Channels
• Quantum to classical transitions in causal relations
• Quantum from principles without assuming definite causal structure
• A no-go theorem for superpositions of causal orders
• Using Quantum Switches to Mitigate Noise in Grover's Search Algorithm
• Quantifying Superpositions Between Quantum Evolutions
• Admissible Causal Structures and Correlations
• Quantum Supermaps are Characterized by Locality
• A Diagrammatic Approach to Information Transmission in Generalised Switches
• No-signalling constrains quantum computation with indefinite causal structure
• No-iteration of unknown quantum gates
• The quantum switch is uniquely defined by its action on unitary operations
• The Multi-round Process Matrix
• Experimental implementation of arbitrary entangled operations
• Network-Device-Independent Certification of Causal Nonseparability
• Addressable quantum gates
• Coherent randomized benchmarking
• Coherent control of the causal order of entanglement distillation
• A no-go theorem for theories that decohere to quantum mechanics
• Indefinite causal key distribution
• Revisiting dynamics of quantum causal structures -- when can causal order evolve?
• Tsirelson bounds for quantum correlations with indefinite causal order
• Quantum Query Complexity of Boolean Functions under Indefinite Causal Order
• Topological obstructions to quantum computation with unitary oracles
• Operational interpretation of the vacuum and process matrices for identical particles
• Emergent non-Markovianity and dynamical quantification of the quantum switch
• Mapping indefinite causal order processes to composable quantum protocols in a spacetime
• Universal quantum computation via quantum controlled classical operations
• Toward an Experimental Device-Independent Verification of Indefinite Causal Order
• On quantum superpositions of graphs, no-signalling and covariance
• Quantum networks theory
• Simulating the quantum switch with quantum circuits is computationally hard
• Background Independence and Quantum Causal Structure
• Quantum switch as a thermodynamic resource in the context of passive states
• Expressibility, entangling power and quantum average causal effect for causally indefinite circuits
• Causality in Higher Order Process Theories
• Quantum theory cannot violate a causal inequality
• Breaking absolute separability with quantum switch
• Causal nonseparability and its implications for spatiotemporal relations
• A de Finetti theorem for quantum causal structures
• Resource-efficient universal photonic processor based on time-multiplexed hybrid architectures
• Coherent control and distinguishability of quantum channels via PBS-diagrams
• Sequential device-independent certification of indefinite causal order
• To share and not share a singlet: control qubit and nonclassicality in teleportation
• Remote Creation of Quantum Coherence via Indefinite Causal Order
• No quantum advantage for violating fixed-order inequalities?
• A Profunctorial Semantics for Quantum Supermaps
• Quantum Heat Transformers
• Information Exchange in Causally Nonseparable Processes
• Multi-core fiber integrated multi-port beamsplitters for quantum information processing
• Knot invariants and indefinite causal order
• Causal influence versus signalling for interacting quantum channels
• Estimation of multivariate traces of states given partial classical information
• Classical and Quantum Query Complexity of Boolean Functions under Indefinite Causal Order
• Forward-backward stochastic simulations: Q-based model for measurement and Bell-nonlocality consistent with weak local realistic premises
• Correlations in a quantum switch-based heat engine with measurements: A proof-of-principle demonstration
• Entropic uncertainty under indefinite causal order and input-output direction
• Optimal Thermalization under Indefinite Causal Order with Identical and Asymmetric Baths
• Refrigeration with Indefinite Causal Orders on a Cloud Quantum Computer
• Quantum probabilities for the causal ordering of events