Infinite or indefinite: the query cost of simulating the quantum switch
quant-ph
Submitted: 2026-11-12
Updated: 2026-11-12
Comments: 36 pages, 6 figures. Lean formalization and exact certificates available at https://github.com/dtlics/Indefinite-Causal-Order
Code: https://github.com/dtlics/Indefinite-Causal-Order
License: http://creativecommons.org/licenses/by/4.0/
The gist: The quantum switch applies two operations in a coherent superposition of their causal orders and is a simple example of indefinite causal order.
Abstract
The quantum switch applies two operations in a coherent superposition of their causal orders and is a simple example of indefinite causal order. No quantum circuit that uses each operation once in a definite order can even describe it, yet photonic experiments have demonstrated its physical realization. We ask how many calls to the black-box operations a quantum computer in the circuit model needs to reproduce the switch. If one of the black boxes is known to be unitary, three calls suffice. For general channels on a d-dimensional system, we prove three results. In all three, circuits may use classical feed-forward and unlimited ancillary quantum memory. First, no finite number of calls suffices for exact simulation in the worst case. Second, approximation to any fixed error below 1/2, measured in half the diamond norm, requires Ω(d 1/4) calls, exponential in the number of qubits. Third, an ordinary circuit can require exponentially many calls to obtain a single bit that the switch extracts with a few uses. We consider a device whose actual noise is dephasing in a fixed unknown basis and test it against a theoretical depolarizing model. The two channels have the same entanglement and average gate fidelities, so these figures alone do not distinguish them. At fixed noise strength, the quantum switch tells them apart with a number of device uses independent of d, whereas the circuit model requires Ω(d 1/16) calls. Noise characterization is needed for quantum error correction, and this gives a provable query advantage of the switch in a task relevant to practical quantum computing. We invite future work that extends such advantages to more practical computing tasks.
Sources
- Quantum computations without definite causal structure
- Witnessing causal nonseparability
- Experimental Superposition of Orders of Quantum Gates
- Experimental Aspects of Indefinite Causal Order in Quantum Mechanics
- Perfect discrimination of no-signalling channels via quantum superposition of causal structures
- Computational advantage from quantum-controlled ordering of gates
- Exponential Communication Complexity Advantage from Quantum Superposition of the Direction of Communication
- Enhanced communication with the assistance of indefinite causal order
- Quantum Metrology with Indefinite Causal Order
- Measuring incompatibility and clustering quantum observables with a quantum switch
- Communication through coherent control of quantum channels
- Reassessing the advantage of indefinite causal orders for quantum metrology
- Simulating the quantum switch with quantum circuits is computationally hard
- Reassessing the computational advantage of quantum-controlled ordering of gates
- Experimentally feasible computational advantage from quantum superposition of gate orders
- Quantum Query Complexity of Boolean Functions under Indefinite Causal Order
- Classical and Quantum Query Complexity of Boolean Functions under Indefinite Causal Order
- Strict hierarchy between parallel, sequential, and indefinite-causal-order strategies for channel discrimination
- Quantum circuits with classical versus quantum control of causal order
- All causally separable quantum processes are quantum circuits with classical control of causal order
Related papers
- Computational regimes in matrix-product-state-based quantum trajectory simulations
- Toward chemically accurate quantum simulations on quantum hardware: A quantum-HPC hybrid approach
- Transversal surface-code game with reconfigurable qubits
- Fulqrum: a generalized framework for quantum subspace diagonalization
- Flux-Activated Resonant Control of a Bosonic Quantum Memory
- Machine learning the effects of many quantum measurements