Simulating the quantum switch with quantum circuits is computationally hard
arXiv:2409.18202 · doi:10.1038/s41467-025-64996-6
Abstract
Higher-order transformations acting on input quantum channels in an indefinite causal order, such as the quantum switch, cannot be described by quantum circuits using the same number of calls to the input channels. A natural question is whether they can be simulated, i.e., whether their action can be exactly and deterministically reproduced by a quantum circuit with more calls to the input channels. Here, we prove that the quantum switch acting on two -qubit channels cannot be simulated by any quantum circuit using calls to one channel and one to the other, if . This establishes an exponential separation in quantum query complexity between processes with indefinite causal order and quantum circuits. Moreover, even with one extra call to both input channels, such a simulation remains impossible. We further demonstrate the robustness of this separation by extending the result to probabilistic and approximate simulations scenarios.
18 + 29 pages, 4 + 5 figures. Close to published version. Contains the results of v1 and of arXiv:2409.18420 [quant-ph], by the same set of authors, merged in a single paper
References in corpus (39)
- Quantum fingerprinting
- Quantum correlations with no causal order
- Quantum computations without definite causal structure
- Theoretical framework for quantum networks
- Quantum Circuits Architecture
- Transforming quantum operations: quantum supermaps
- Computational advantage from quantum-controlled ordering of gates
- Enhanced communication with the assistance of indefinite causal order
- Perfect discrimination of no-signalling channels via quantum superposition of causal structures
- Witnessing causal nonseparability
- Quantum Metrology with Indefinite Causal Order
- Experimental transmission of quantum information using a superposition of causal orders
- Indefinite causal order enables perfect quantum communication with zero capacity channels
- Quantum Shannon theory with superpositions of trajectories
- Experimental Quantum Communication Enhancement by Superposing Trajectories
- Communicating via ignorance: Increasing communication capacity via superposition of order
- Reversing Unknown Quantum Transformations: Universal Quantum Circuit for Inverting General Unitary Operations
- Computational advantage from quantum superposition of multiple temporal orders of photonic gates
- Semidefinite Programming in Quantum Information Science
- Quantum circuits with classical versus quantum control of causal order
- Optimal quantum networks and one-shot entropies
- Theoretical framework for Higher-Order Quantum Theory
- Experimentally feasible computational advantage from quantum superposition of gate orders
- Optimal Strategies of Quantum Metrology with a Strict Hierarchy
- Probabilistic exact universal quantum circuits for transforming unitary operations
- Experimental Aspects of Indefinite Causal Order in Quantum Mechanics
- Entanglement, non-Markovianity, and causal non-separability
- Unitary channel discrimination beyond group structures: Advantages of sequential and indefinite-causal-order strategies
- Deterministic transformations between unitary operations: Exponential advantage with adaptive quantum circuits and the power of indefinite causality
- Observer-dependent locality of quantum events
- Semi-device-independent certification of indefinite causal order in a photonic quantum switch
- Higher-order Process Matrix Tomography of a passively-stable Quantum SWITCH
- Consequences of preserving reversibility in quantum superchannels
- Reassessing the advantage of indefinite causal orders for quantum metrology
- Universal construction of decoders from encoding black boxes
- The quantum switch is uniquely defined by its action on unitary operations
- Quantum Query Complexity of Boolean Functions under Indefinite Causal Order
- Universal adjointation of isometry operations using conversion of quantum supermaps
- Characterising transformations between quantum objects, 'completeness' of quantum properties, and transformations without a fixed causal order