Pith. sign in

REVIEW 4 cited by

Exponential separation in quantum query complexity of the quantum switch with respect to simulations with standard quantum circuits

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2409.18420 v2 pith:DFAQZGAE submitted 2024-09-27 quant-ph

Exponential separation in quantum query complexity of the quantum switch with respect to simulations with standard quantum circuits

Hl\'er Kristj\'ansson , Tatsuki Odake , Satoshi Yoshida , Philip Taranto , Jessica Bavaresco , Marco T\'ulio Quintino , Mio Murao This is my paper
classification quant-ph
keywords quantumstandardswitchcausalcircuitcircuitscomplexityexponential
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved
0 comments
read the original abstract

Quantum theory is consistent with a computational model permitting black-box operations to be applied in an indefinite causal order, going beyond the standard circuit model of computation. The quantum switch -- the simplest such example -- has been shown to provide numerous information-processing advantages. Here, we prove that the action of the quantum switch on two $n$-qubit quantum channels cannot be simulated deterministically and exactly by any causally ordered quantum circuit that uses $M$ calls to one channel and one call to the other, if $M \leq \max(2, 2^n-1)$. This demonstrates an exponential separation in quantum query complexity of indefinite causal order compared to standard quantum circuits.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 4 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Programming with Quantum-Controlled Quantum Channels

    cs.PL 2026-07 accept novelty 8.0

    A linear type system that aligns measurements in the two branches of quantum branching lets the quantum SWITCH be defined for arbitrary measurement-containing programs.

  2. Higher-Order Programs with Indefinite Causal Orders: a Linear Approach to Coherent Control of Quantum Processes

    cs.LO 2026-07 accept novelty 7.5

    A linear-typed higher-order language realises indefinite causal orders on general quantum channels (including measurements), with soundness in Caus[CPM] and expressivity covering all first-order channels plus a large ...

  3. Quantum Term Rewrite Systems: Applications to Complexity Analysis

    cs.LO 2026-07 conditional novelty 7.0

    Quantum term rewrite systems are introduced, and their polynomial-time terminating fragment characterizes the quantum complexity class FBQP.

  4. Causality in Pure Quantum Computation with Quantum Control

    cs.PL 2026-07 conditional novelty 7.0

    A typed lambda calculus based on intuitionistic BV logic blocks higher-order quantum-control programs that violate causality, and its categorical model excludes the OCB process.